net.datastructures
Class AVLTreeMap<K,V>

java.lang.Object
  net.datastructures.LinkedBinaryTree<Entry<K,V>>
      net.datastructures.BinarySearchTreeMap<K,V>
          net.datastructures.AVLTreeMap<K,V>

All Implemented Interfaces:

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

public class AVLTreeMap<K,V>
extends BinarySearchTreeMap<K,V>
implements Map<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

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

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

BinarySearchTreeMap.BSTEntry<K,V>

Field Summary

Fields inherited from class net.datastructures.BinarySearchTreeMap

actionPos, C, numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

AVLTreeMap()

AVLTreeMap(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).
protected boolean	isBalanced(Position<Entry<K,V>> p) Returns whether a node has balance factor between -1 and 1.
V	put(K k, V v) If there is an entry with the specified key, replaces the value of this entry with the specified value and returns the old value.
protected void	rebalance(Position<Entry<K,V>> zPos) Rebalance method called by insert and remove.
V	remove(K k) If there is an entry with the specified key, removes this entry and returns its value.
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.BinarySearchTreeMap

checkEntry, checkKey, entry, entrySet, get, insertAtExternal, isEmpty, key, keySet, removeExternal, replaceEntry, restructure, size, treeSearch, value, values

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

entrySet, get, isEmpty, keySet, size, values

Constructor Detail

AVLTreeMap

public AVLTreeMap(Comparator<K> c)

AVLTreeMap

public AVLTreeMap()

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.

put

public V put(K k,
             V v)
      throws InvalidKeyException

If there is an entry with the specified key, replaces the value of this entry with the specified value and returns the old value. Else, adds a new entry with the specified key and value and returns null.

Specified by:

put in interface Map<K,V>

Overrides:

put in class BinarySearchTreeMap<K,V>

Throws:

InvalidKeyException

remove

public V remove(K k)
         throws InvalidKeyException

If there is an entry with the specified key, removes this entry and returns its value. Else, returns null.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class BinarySearchTreeMap<K,V>

Throws:

InvalidKeyException