net.datastructures
Class AVLTree

java.lang.Object
  net.datastructures.LinkedBinaryTree
      net.datastructures.BinarySearchTree
          net.datastructures.AVLTree

All Implemented Interfaces:

BinaryTree, Dictionary, Tree

public class AVLTree

extends BinarySearchTree

implements Dictionary

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 Nested class for the nodes of an AVL tree.

Nested classes inherited from class net.datastructures.BinarySearchTree

BinarySearchTree.BSTEntry

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

Method Summary

protected BTPosition	createNode(Object element, BTPosition parent, BTPosition left, BTPosition right) Creates a new binary search tree node (overrides super's version).
protected int	height(Position p) Returns the height of a node (call back to an AVLNode).
Entry	insert(Object k, Object v) Inserts an item into the dictionary and returns the newly created entry.
protected boolean	isBalanced(Position p) Returns whether a node has balance factor between -1 and 1.
protected void	rebalance(Position zPos) Rebalance method called by insert and remove.
Entry	remove(Entry ent) Removes and returns an entry from the dictionary.
protected void	setHeight(Position p) Sets the height of an internal node (call back to an AVLNode).
protected Position	tallerChild(Position 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, elements, expandExternal, hasLeft, hasRight, inorderPositions, insertLeft, insertRight, isExternal, isInternal, isRoot, left, parent, positions, 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 c)

AVLTree

public AVLTree()

Method Detail

createNode

protected BTPosition createNode(Object element,
                                BTPosition parent,
                                BTPosition left,
                                BTPosition right)

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

Overrides:

createNode in class LinkedBinaryTree

height

protected int height(Position p)

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

setHeight

protected void setHeight(Position p)

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

isBalanced

protected boolean isBalanced(Position p)

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

tallerChild

protected Position tallerChild(Position p)

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

rebalance

protected void rebalance(Position 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 insert(Object k,
                    Object v)
             throws InvalidKeyException

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

Specified by:

insert in interface Dictionary

Overrides:

insert in class BinarySearchTree

Throws:

InvalidKeyException

remove

public Entry remove(Entry ent)
             throws InvalidEntryException

Removes and returns an entry from the dictionary.

Specified by:

remove in interface Dictionary

Overrides:

remove in class BinarySearchTree

Throws:

InvalidEntryException