net.datastructures
Class AVLTree<K,V>

java.lang.Object
  net.datastructures.LinkedBinaryTree<Entry<K,V>>
      net.datastructures.BinarySearchTree<K,V>
          net.datastructures.AVLTree<K,V>

All Implemented Interfaces:

BinaryTree<Entry<K,V>>, Dictionary<K,V>, Tree<Entry<K,V>>

public class AVLTree<K,V>
extends BinarySearchTree<K,V>
implements Dictionary<K,V>

AVLTree class - implements an AVL Tree by extending a binary search tree.

Author:

Michael Goodrich, Roberto Tamassia, Eric Zamore

Constructor Summary

AVLTree()

AVLTree(java.util.Comparator<K> cptr)

Method Summary

Entry<K,V>	insert(K k, V v) Inserts an item into the dictionary and returns the newly created entry.
Entry<K,V>	remove(Entry<K,V> ent) Removes and returns an entry from the dictionary.

Methods inherited from class net.datastructures.BinarySearchTree

entries, find, findAll, isEmpty, size

Methods inherited from class net.datastructures.LinkedBinaryTree

addRoot, attach, children, expandExternal, hasLeft, hasRight, insertLeft, insertRight, isExternal, isInternal, isRoot, iterator, left, parent, positions, remove, removeAboveExternal, replace, right, root, sibling, swapElements

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.datastructures.Dictionary

entries, find, findAll, isEmpty, size

Constructor Detail

AVLTree

public AVLTree(java.util.Comparator<K> cptr)

AVLTree

public AVLTree()

Method Detail

insert

public Entry<K,V> insert(K k,
                         V v)
                  throws InvalidKeyException

Inserts an item into the dictionary and returns the newly created entry.

Specified by:

insert in interface Dictionary<K,V>

Overrides:

insert in class BinarySearchTree<K,V>

Throws:

InvalidKeyException

remove

public Entry<K,V> remove(Entry<K,V> ent)
                  throws InvalidEntryException

Removes and returns an entry from the dictionary.

Specified by:

remove in interface Dictionary<K,V>

Overrides:

remove in class BinarySearchTree<K,V>

Throws:

InvalidEntryException