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

root

parentOfA
A

New node contains element e

F IGURE 26.9

The nodes along the path from the new leaf node may become unbalanced.

26.8

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

26.9

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

26.10

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

26.5 Implementing Rotations
An unbalanced tree becomes balanced by performing an appropriate rotation operation.

Key
Point

Section 26.2, Rebalancing Trees, illustrated how to perform rotations at a node. Listing 26.2
gives the algorithm for the LL rotation, as illustrated in Figure 26.2.

L ISTING 26.2

LL Rotation Algorithm
1 balanceLL(TreeNode A, TreeNode parentOfA) {
2 Let B be the left child of A.
3
4 if (A is the root)
5 Let B be the new root
6 else {
7 if (A is a left child of parentOfA)
8 Let B be a left child of parentOfA;
9 else
10 Let B be a right child of parentOfA;
11 }
12
13 Make T2 the left subtree of A by assigning B.right to A.left;
14 Make A the right child of B by assigning A to B.right;
15 Update the height of node A and node B;
16 } // End of method

left child of A

reconnect B's parent

move subtrees

adjust height

Note that the height of nodes A and B can be changed, but the heights of other nodes in the
tree are not changed. You can implement the RR, LR, and RL rotations in a similar manner.