AVL TREES - Introduction to Java Programming: Comprehensive Version - page 969

26.3 Designing Classes for AVL Trees
Since an AVL tree is a binary search tree, AVLTree is designed as a subclass of BST .

Key
Point

An AVL tree is a binary tree, so you can define the AVLTree class to extend the BST class, as
shown in Figure 26.7. The BST and TreeNode classes were defined in Section 25.2.5.

TreeNode<E> BST<E extends Comparable<E>>

m 0

AVLTreeNode<E> AVLTree<E extends Comparable<E>>

#height: int +AVLTree()

+AVLTree(objects: E[])
#createNewNode(): AVLTreeNode<E>
+insert(e: E): boolean
+delete(e: E): boolean

Creates an empty AVL tree.
Creates an AVL tree from an array of objects.
Overrides this method to create an AVLTreeNode .
Returns true if the element is added successfully.

1

Returns true if the element is removed from the
tree successfully.
Resets the height of the specified node.

Link

-updateHeight(node:
AVLTreeNode<E>): void

-balancePath(e: E): void Balances the nodes in the path from the node for

the element to the root if needed.

-balanceFactor(node:
AVLTreeNode<E>): int

Returns the balance factor of the node.

-balanceLL(A: TreeNode,
parentOfA: TreeNode<E>): void

Performs LL balance.

-balanceLR(A: TreeNode<E>,
parentOfA: TreeNode<E>): void

Performs LR balance.

-balanceRR(A: TreeNode<E>,
parentOfA: TreeNode<E>): void

Performs RR balance.

-balanceRL(A: TreeNode<E>,
parentOfA: TreeNode<E>): void

Performs RL balance.

F IGURE 26.7

The AVLTree class extends BST with new implementations for the insert and delete methods.

In order to balance the tree, you need to know each node's height. For convenience, store
the height of each node in AVLTreeNode and define AVLTreeNode to be a subclass of
BST.TreeNode . Note that TreeNode is defined as a static inner class in BST . AVLTreeNode
will be defined as a static inner class in AVLTree . TreeNode contains the data fields element ,
left , and right , which are inherited by AVLTreeNode . Thus, AVLTreeNode contains four
data fields, as shown in Figure 26.8.

AVLTreeNode

node: AVLTreeNode<E>

#element: E
#height: int
#left: TreeNode<E>
#right: TreeNode<E>

F IGURE 26.8

An AVLTreeNode contains the protected data fields element , height ,
left , and right .