Opus5
Class AVLTree

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractTree
                    |
                    +--Opus5.BinaryTree
                          |
                          +--Opus5.BinarySearchTree
                                |
                                +--Opus5.AVLTree

All Implemented Interfaces:

Comparable, Container, SearchableContainer, SearchTree, Tree

public class AVLTree

extends BinarySearchTree

A node in an AVL tree.

Version:

$Id: AVLTree.java,v 3.4 1998/07/29 14:24:26 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Inner classes inherited from class Opus5.AbstractTree

AbstractTree.TreeEnumeration

Field Summary

protected int

height The height of this node.

Fields inherited from class Opus5.BinaryTree

key, left, right

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.SearchTree

copyright

Constructor Summary

AVLTree()
Constructs an empty AVLTree

Method Summary

protected void	adjustHeight() Recomputes the height of this node from the heights of the subtrees of this node.
void	attachKey(java.lang.Object object) Attaches the specified object as the key of this node.
protected void	balance() AVL balances this node.
java.lang.Object	detachKey() Detaches the key from this node; making it the empty node.
protected void	doLLRotation() Performs an LL (single) rotation.
protected void	doLRRotation() Performs an LR (double) rotation.
protected void	doRLRotation() Performs an RL (double) rotation.
protected void	doRRRotation() Performs an RR (single) rotation.
protected int	getBalanceFactor() Returns the balance factor for this node.
int	getHeight() Returns the height of this AVL tree node.

Methods inherited from class Opus5.BinarySearchTree

find, findMax, findMin, insert, isMember, withdraw

Methods inherited from class Opus5.BinaryTree

attachLeft, attachRight, compareTo, depthFirstTraversal, detachLeft, detachRight, getDegree, getKey, getLeft, getRight, getSubtree, isEmpty, isLeaf, purge

Methods inherited from class Opus5.AbstractTree

accept, breadthFirstTraversal, getCount, getEnumeration

Methods inherited from class Opus5.AbstractContainer

hashCode, isFull, toString

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Tree

breadthFirstTraversal, depthFirstTraversal, getDegree, getKey, getSubtree, isEmpty, isLeaf

Methods inherited from interface Opus5.Container

accept, getCount, getEnumeration, isFull, purge

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

height

protected int height

The height of this node.

Constructor Detail

AVLTree

public AVLTree()

Constructs an empty AVLTree

Method Detail

getHeight

public int getHeight()

Returns the height of this AVL tree node.

Overrides:

getHeight in class AbstractTree

Returns:

the height of this AVL tree node.

adjustHeight

protected void adjustHeight()

Recomputes the height of this node from the heights of the subtrees of this node.

getBalanceFactor

protected int getBalanceFactor()

Returns the balance factor for this node.

Returns:

The difference between the heights of the left and right subtrees of this node if this node is not empty; zero if this node is empty.

doLLRotation

protected void doLLRotation()

Performs an LL (single) rotation.

Throws:

InvalidOperationException - If this node is empty.

doRRRotation

protected void doRRRotation()

Performs an RR (single) rotation.

Throws:

InvalidOperationException - If this node is empty.

doLRRotation

protected void doLRRotation()

Performs an LR (double) rotation.

Throws:

InvalidOperationException - If this node is empty.

doRLRotation

protected void doRLRotation()

Performs an RL (double) rotation.

Throws:

InvalidOperationException - If this node is empty.

balance

protected void balance()

AVL balances this node.

Overrides:

balance in class BinarySearchTree

attachKey

public void attachKey(java.lang.Object object)

Attaches the specified object as the key of this node. The node must be initially empty.

Overrides:

attachKey in class BinarySearchTree

Parameters:

object - The key to attach.

Throws:

InvalidOperationException - If this node is not empty.

detachKey

public java.lang.Object detachKey()

Detaches the key from this node; making it the empty node.

Overrides:

detachKey in class BinaryTree

Throws:

InvalidOperationException - If this is not a leaf node.