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

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

Type Parameters:

K - Type of the keys.

D - Type of the data.

All Implemented Interfaces:

Map<K,D>

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

An AVL-tree is an always balanced tree. To be more precise, for each node in the tree the heights of the two subtrees differ by at most 1. Thus, the height of an AVL-tree containing n elements is always about log(n). Thus, all default operations like insertion (insert(Comparable, Object)), removal (delete(Comparable)), lookup (Searchtree.find(Comparable)), ... have at most logarithmic costs.

Author:

Rossmanith

See Also:

Map

Constructor Summary

AVLtree()

Method Summary

void	delete(K k) Removes the entry which stores the data for the key k.
void	insert(K k, D d) 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

AVLtree

public AVLtree()

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.

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.