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

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

Type Parameters:

K - The type of the keys.

D - The type of the data.

All Implemented Interfaces:

Map<K,D>

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

An implementation of a Splaytree.

Author:

Rossmanith

Constructor Summary

Splaytree()

Method Summary

void	delete(K k) Removes the entry which stores the data for the key k.
D	find(K k) Looks up the data for the given key k.
void	insert(K k, D d) Associates the data d to the key k in this map.
boolean	iselement(K k) Checks whether the given key k is present in this searchtree.

Methods inherited from class Searchtree

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

Splaytree

public Splaytree()

Method Detail

insert

public void insert(K k,
                   D d)

Description copied from interface: Map

Associates the data d to the key k in this map. A possible old entry for k will be deleted.

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 associated to the key k.

iselement

public boolean iselement(K k)

Description copied from class: Searchtree

Checks whether the given key k is present in this searchtree. (linear time in depth of the tree)

Specified by:

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

Overrides:

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

Parameters:

k - The key to look for, must be non-null.

Returns:

true, iff k is contained in this tree.

find

public D find(K k)

Description copied from class: Searchtree

Looks up the data for the given key k. (linear time in depth of the tree)

Specified by:

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

Overrides:

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

Parameters:

k - The key to look for, must be non-null.

Returns:

The data stored under k, or null, if there is no data for k.

See Also:

Map.find(Object)

delete

public void delete(K k)

Description copied from class: Searchtree

Removes the entry which stores the data for the key k. Idle operations if there is no data stored for k. (linear time in depth of tree)

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.