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

Nested Class Summary

protected static class

AVLTree.AVLNode<K,V> Nested class for the nodes of an AVL tree.

Nested classes/interfaces inherited from class net.datastructures.BinarySearchTree

BinarySearchTree.BSTEntry<K,V>

Field Summary

Fields inherited from class net.datastructures.BinarySearchTree

actionPos, C, numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

AVLTree()

AVLTree(Comparator<K> c)

Method Summary

protected BTPosition<Entry<K,V>>	createNode(Entry<K,V> element, BTPosition<Entry<K,V>> parent, BTPosition<Entry<K,V>> left, BTPosition<Entry<K,V>> right) Creates a new binary search tree node (overrides super's version).
protected int	height(Position<Entry<K,V>> p) Returns the height of a node (call back to an AVLNode).
Entry<K,V>	insert(K k, V v) Inserts an item into the dictionary and returns the newly created entry.
protected boolean	isBalanced(Position<Entry<K,V>> p) Returns whether a node has balance factor between -1 and 1.
protected void	rebalance(Position<Entry<K,V>> zPos) Rebalance method called by insert and remove.
Entry<K,V>	remove(Entry<K,V> ent) Removes and returns an entry from the dictionary.
protected void	setHeight(Position<Entry<K,V>> p) Sets the height of an internal node (call back to an AVLNode).
protected Position<Entry<K,V>>	tallerChild(Position<Entry<K,V>> p) Return a child of p with height no smaller than that of the other child.

Methods inherited from class net.datastructures.BinarySearchTree

addAll, checkEntry, checkKey, entries, entry, find, findAll, insertAtExternal, isEmpty, key, removeExternal, replaceEntry, restructure, size, treeSearch, value

Methods inherited from class net.datastructures.LinkedBinaryTree

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

Methods inherited from class java.lang.Object

clone, equals, finalize, 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(Comparator<K> c)

AVLTree

public AVLTree()

Method Detail

createNode

protected BTPosition<Entry<K,V>> createNode(Entry<K,V> element,
                                            BTPosition<Entry<K,V>> parent,
                                            BTPosition<Entry<K,V>> left,
                                            BTPosition<Entry<K,V>> right)

Creates a new binary search tree node (overrides super's version).

Overrides:

createNode in class LinkedBinaryTree<Entry<K,V>>

height

protected int height(Position<Entry<K,V>> p)

Returns the height of a node (call back to an AVLNode).

setHeight

protected void setHeight(Position<Entry<K,V>> p)

Sets the height of an internal node (call back to an AVLNode).

isBalanced

protected boolean isBalanced(Position<Entry<K,V>> p)

Returns whether a node has balance factor between -1 and 1.

tallerChild

protected Position<Entry<K,V>> tallerChild(Position<Entry<K,V>> p)

Return a child of p with height no smaller than that of the other child.

rebalance

protected void rebalance(Position<Entry<K,V>> zPos)

Rebalance method called by insert and remove. Traverses the path from zPos to the root. For each node encountered, we recompute its height and perform a trinode restructuring if it's unbalanced.

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