aud.AVLTree.AVLNode Class Reference

Node in an AVLTree. More...

Inheritance diagram for aud.AVLTree.AVLNode:

Collaboration diagram for aud.AVLTree.AVLNode:

Public Member Functions
int	computeHeight ()
	compute height of subtree recursively (for testing only) More...
int	getHeight (AVLNode node)
	get height of subtree More...
int	getBalance ()
	get height difference between left and right subtree More...
boolean	isBalanced ()
	|getBalance()|<=1 ? More...

Protected Member Functions
String	textLabel ()

Detailed Description

Node in an AVLTree.

The node stores the height of its subtree for balancing. Note that it is sufficient to store the balance (in only 2 bits). Referring to height instead of balance simplifies this implementation.

Definition at line 24 of file AVLTree.java.

Member Function Documentation

computeHeight()

int aud.AVLTree.AVLNode.computeHeight

(

)

compute height of subtree recursively (for testing only)

Definition at line 32 of file AVLTree.java.

                               {
      int hl=getLeft() !=null ? ((AVLNode) getLeft()) .computeHeight() : 0;
      int hr=getRight()!=null ? ((AVLNode) getRight()).computeHeight() : 0;
      return 1+(hl>hr ? hl : hr);
    }

References aud.AVLTree.AVLNode.computeHeight().

Referenced by aud.AVLTree.AVLNode.computeHeight().

Here is the call graph for this function:

Here is the caller graph for this function:

getBalance()

int aud.AVLTree.AVLNode.getBalance

(

)

get height difference between left and right subtree

Definition at line 53 of file AVLTree.java.

                            {
      return getHeight((AVLNode) getLeft())-getHeight((AVLNode) getRight());
    }

References aud.AVLTree.AVLNode.getHeight().

Referenced by aud.AVLTree.AVLNode.isBalanced().

Here is the call graph for this function:

Here is the caller graph for this function:

getHeight()

int aud.AVLTree.AVLNode.getHeight

(

AVLNode

node

)

get height of subtree

Returns

height >=1 or 0 for node==null

Definition at line 43 of file AVLTree.java.

{ return node==null ? 0 : node.height_; }

Referenced by aud.AVLTree.AVLNode.getBalance().

Here is the caller graph for this function:

isBalanced()

boolean aud.AVLTree.AVLNode.isBalanced

(

)

|getBalance()|<=1 ?

Definition at line 57 of file AVLTree.java.

                                {
      int b=getBalance();
      return -1<=b && b <=+1;
    }

References aud.AVLTree.AVLNode.getBalance().

Here is the call graph for this function:

textLabel()

String aud.AVLTree.AVLNode.textLabel ( )

protected

Definition at line 62 of file AVLTree.java.

                                           {
      return getData().toString()+" ("+height_+")";
    }

---

The documentation for this class was generated from the following file:

• AVLTree.java