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

In the BST class, the createNewNode() method creates a TreeNode object. This method
is overridden in the AVLTree class to create an AVLTreeNode . Note that the return type
of the createNewNode() method in the BST class is TreeNode , but the return type of
the createNewNode() method in the AVLTree class is AVLTreeNode . This is fine, since
AVLTreeNode is a subclass of TreeNode .
Searching for an element in an AVLTree is the same as searching in a regular binary tree,
so the search method defined in the BST class also works for AVLTree .
The insert and delete methods are overridden to insert and delete an element and per-
form rebalancing operations if necessary to ensure that the tree is balanced.

createNewNode()

26.4

✓ ✓

What are the data fields in the AVLTreeNode class?

Check

26.5

Point

True or false: AVLTreeNode is a subclass of TreeNode ?

26.6

True or false: AVLTree is a subclass of BST .

26.4 Overriding the insert Method
Inserting an element into an AVL tree is the same as inserting it to a BST, except that
the tree may need to be rebalanced.

Key
Point

A new element is always inserted as a leaf node. As a result of adding a new node, the heights
of the new leaf node's ancestors may increase. After inserting a new node, check the nodes
along the path from the new leaf node up to the root. If an unbalanced node is found, perform
an appropriate rotation using the algorithm in Listing 26.1.

L ISTING 26.1

Balancing Nodes on a Path
1 balancePath(E e) {
2 Get the path from the node that contains element e to the root,
3 as illustrated in Figure 26.9;
4 for each node A in the path leading to the root {
5 Update the height of A;
6 Let parentOfA denote the parent of A,
7 which is the next node in the path, or null if A is the root;
8
9 switch (balanceFactor(A)) {
10 case -2 : if balanceFactor(A.left) == -1 or 0
11 Perform LL rotation; // See Figure 26.2
12 else
13 Perform LR rotation; // See Figure 26.4
14 break ;
15 case +2 : if balanceFactor(A.right) == +1 or 0
16 Perform RR rotation; // See Figure 26.3
17 else
18 Perform RL rotation; // See Figure 26.5
19 } // End of switch
20 } // End of for
21 } // End of method

get the path

update node height
get parent node

is balanced?

LL rotation

LR rotation

RR rotation

RL rotation

The algorithm considers each node in the path from the new leaf node to the root. Update
the height of the node on the path. If a node is balanced, no action is needed. If a node is not
balanced, perform an appropriate rotation.

26.7

✓ ✓

For the AVL tree in Figure 26.6a, show the new AVL tree after adding element 40 .
What rotation do you perform in order to rebalance the tree? Which node was
unbalanced?

Check

Point