Class Treap<K extends java.lang.Comparable<K>,D>

java.lang.Object
  Dictionary<K,D>
      Searchtree<K,D>
          Treap<K,D>

Type Parameters:

K - The type of keys to store.

D - The type of data to store.

All Implemented Interfaces:

Map<K,D>

public class Treap<K extends java.lang.Comparable<K>,D>
extends Searchtree<K,D>

A treap is like a search-tree where the nodes are annotated with weights/priorities. Then it is assured that the nodes are a heap w.r.t. to the weights and a search-tree w.r.t. the keys, i.e., for every node its weight is smaller than that of all nodes below it. Insertion, deletion, etc. are performed in logarithmic time in average.

Author:

Rossmanith

Constructor Summary

Treap()
Constructs a new, empty Treap

Treap(int seed)
Constructs a new, empty Treap with given random seed.

Method Summary

void	delete(K k) Removes the entry which stores the data for the key k.
int	getpriority(K k) Returns the priority(weight) for the node stored under key k.
void	insert(K k, D d) Associates the data d to the key k in this map.
void	insert(K k, D d, int weight) Associates the data d to the key k in this map.

Methods inherited from class Searchtree

find, iselement, iterator, opt_searchtree, print, size

Methods inherited from class Dictionary

array, isempty, simpleiterator

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Treap

public Treap()

Constructs a new, empty Treap

Treap

public Treap(int seed)

Constructs a new, empty Treap with given random seed.

Parameters:

seed - The random seed to initialize the random number generator.

Method Detail

insert

public void insert(K k,
                   D d)

Associates the data d to the key k in this map. (Internally, a random weight is taken for the new node)

Specified by:

insert in interface Map<K extends java.lang.Comparable<K>,D>

Overrides:

insert in class Searchtree<K extends java.lang.Comparable<K>,D>

Parameters:

k - The key to store.

d - The data to store.

See Also:

Map.insert(Object, Object)

insert

public void insert(K k,
                   D d,
                   int weight)

Associates the data d to the key k in this map. Moreover, not a random weight is taken but the user provided weight w.

Parameters:

k - The key to store.

d - The data to store.

weight - The weight for the newly inserted node.

See Also:

Map.insert(Object, Object)

delete

public void delete(K k)

Removes the entry which stores the data for the key k. Idle operations if there is no data stored for k. (logarithmic time in average)

Specified by:

delete in interface Map<K extends java.lang.Comparable<K>,D>

Overrides:

delete in class Searchtree<K extends java.lang.Comparable<K>,D>

Parameters:

k - The key to delete with its associated data.

getpriority

public int getpriority(K k)

Returns the priority(weight) for the node stored under key k.

Parameters:

k - A key which must be present in this treap.

Returns:

The priority of the node containing k.