Package aud

Class AVLTree<Key extends Comparable<Key>,Value>

java.lang.Object

aud.BinarySearchTree<Key,Value>

aud.AVLTree<Key,Value>

All Implemented Interfaces:

Graphvizable, GraphvizDecorable, Iterable<BinarySearchTree<Key,Value>.Cursor>

public class AVLTree<Key extends Comparable<Key>,Value>
extends BinarySearchTree<Key,Value>

Simple implementation of an AVL tree.

This implementation is based on BinarySearchTree and in particular BinarySearchTree.restructure(aud.BinarySearchTree.Node) for rebalancing. This implementation does not implement removal of nodes! remove(Key) always throws UnsupportedOperationException!

See Also:

• AVLTreeExample

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	AVLTree.AVLNode	Node in an AVLTree.

Nested classes/interfaces inherited from class aud.BinarySearchTree

BinarySearchTree.Cursor, BinarySearchTree.Decorator, BinarySearchTree.Entry, BinarySearchTree.Iterator, BinarySearchTree.LowerBound, BinarySearchTree.Node, BinarySearchTree.Range, BinarySearchTree.RangeIterator, BinarySearchTree.Visitor

Field Summary

Fields inherited from class aud.BinarySearchTree

head_

Constructor Summary

Constructors

Constructor	Description
AVLTree()	create empty tree

Method Summary

Modifier and Type	Method	Description
protected void	checkConsistency(BinarySearchTree<Key,Value>.Node node)	additionally check heights and balancing
protected BinarySearchTree<Key,Value>.Node	createNode(Key key, Value value)	override: create new AVLNode
int	getHeight()	get height of tree
static void	main(String[] args)	example and test
protected void	onInsert(BinarySearchTree<Key,Value>.Node _node)	Called whenever a new node is inserted.
protected void	rebalance(AVLTree<Key,Value>.AVLNode x, AVLTree<Key,Value>.AVLNode y, AVLTree<Key,Value>.AVLNode z)
Value	remove(Key key)	not implemented!

Methods inherited from class aud.BinarySearchTree

checkConsistency, compareKeys, find, findEntry, findLowerBound, getDecorator, getMaximum, getMinimum, insert, isEmpty, iterator, onRemove, range, removeNode, restructure, restructure, rotateLeft, rotateLeftRight, rotateRight, rotateRightLeft, setupBalancedSubtree, toDot, toString, toText, toTikZ, visitPreorder

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

AVLTree

public AVLTree()

create empty tree

Method Details

createNode

protected BinarySearchTree<Key,Value>.Node createNode(Key key,
 Value value)

override: create new AVLNode

Overrides:

createNode in class BinarySearchTree<Key extends Comparable<Key>,Value>

getHeight

public int getHeight()

get height of tree

onInsert

protected void onInsert(BinarySearchTree<Key,Value>.Node _node)

Description copied from class: BinarySearchTree

Called whenever a new node is inserted.

Called by BinarySearchTree.insert(Key, Value) to notify a class derived from BinarySearchTree that a new node has been inserted. Using this sort of callback mechanism avoids a reimplementation of BinarySearchTree.insert(Key, Value).

The standard implementation is empty. The idea is to use the callback for visualization or have a subclass rebalancing the tree after node insertion.

Overrides:

onInsert in class BinarySearchTree<Key extends Comparable<Key>,Value>

Parameters:

_node - the newly inserted node

rebalance

protected void rebalance(AVLTree<Key,Value>.AVLNode x,
 AVLTree<Key,Value>.AVLNode y,
 AVLTree<Key,Value>.AVLNode z)

remove

public Value remove(Key key)

not implemented!

Overrides:

remove in class BinarySearchTree<Key extends Comparable<Key>,Value>

Returns:

value of removed node or null if there was no such node

Throws:

UnsupportedOperationException - always!

checkConsistency

protected void checkConsistency(BinarySearchTree<Key,Value>.Node node)

additionally check heights and balancing

Overrides:

checkConsistency in class BinarySearchTree<Key extends Comparable<Key>,Value>

main

public static void main(String[] args)

example and test