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

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

Type Parameters:

K - The type of the keys.

D - The type of the data.

All Implemented Interfaces:

Map<K,D>

Direct Known Subclasses:

AVLtree, Splaytree, Treap

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

A Searchtree is a Map-implementation as (not necessarily balanced) binary tree. Standard access methods like insertion, deletion, and lookup are linear in the depth of the tree, and thus, logarithmic in the nr of entries, if the tree is balanced.

Author:

Rossmanith

Constructor Summary

Searchtree()

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.
Iterator<K,D>	iterator() Creates a new iterator over all associations between keys and data.
void	opt_searchtree(int n, Array<K> keys, Array<java.lang.Double> p, Array<java.lang.Double> q) Constructs an optimal search tree in the general case with n given keys where the propabilities to access each key are stored in p and the propabilities to access values between two keys are stored in q.
void	print() Prints the map to stdout
int	size() Linear time implementation of Map.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

Searchtree

public Searchtree()

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>

Specified by:

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

Parameters:

k - The key to store.

d - The data associated to the key k.

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. (linear time in depth of tree)

Specified by:

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

Specified by:

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

Parameters:

k - The key to delete with its associated data.

find

public D find(K k)

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 Dictionary<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)

iselement

public boolean iselement(K k)

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 Dictionary<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.

size

public int size()

Description copied from class: Dictionary

Linear time implementation of Map.size()

Specified by:

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

Overrides:

size in class Dictionary<K extends java.lang.Comparable<K>,D>

iterator

public Iterator<K,D> iterator()

Description copied from interface: Map

Creates a new iterator over all associations between keys and data.

Specified by:

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

Specified by:

iterator in class Dictionary<K extends java.lang.Comparable<K>,D>

Returns:

The Iterator over all keys with associated data.

print

public void print()

Description copied from interface: Map

Prints the map to stdout

Specified by:

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

Overrides:

print in class Dictionary<K extends java.lang.Comparable<K>,D>

opt_searchtree

public void opt_searchtree(int n,
                           Array<K> keys,
                           Array<java.lang.Double> p,
                           Array<java.lang.Double> q)

Constructs an optimal search tree in the general case with n given keys where the propabilities to access each key are stored in p and the propabilities to access values between two keys are stored in q. The sum of all values in p and q must be 1. (Implemented with dynamic programming, O(n³) complexity)

Parameters:

n - The number of keys.

keys - The keys to store.

p - The propabilities to access a key. More precisely, p[i] is the propability to access keys[i] for all 0 ≤ i < n.

q - The propabilities to access values between two keys. More precisely, q[0] is the propability to ask for values smaller than keys[0]. q[n] is the propability to ask for values larger than keys[n-1]. And q[i] is the propability to ask for values between keys[i-1] and keys[i] for all 1 ≤ i < n.