The AVL algorithm for balancing a Binary Search Tree.

By Nicholas Duchon, Oct 14, 2011

Definitions

Much of this presentation follows the presentation of AVL trees in Data Structures and Algorithms in Java, 3rd edition, pp 421-431, ISBN 0-471-46983-1, 2004.

Let us assume that the BST is defined with:
We will not allow repeats in these trees.

The algorithm uses a balance factor at each node based on the height of that node. So we need to define these terms.

Test Cases

Notation:
Comments
Numbers
Changes in
Height from
Initial BST
Initial BST
Balanced BST - one rotation
Second rotation
Left Rotation
Unbalanced at 1
N > U
N > C
left - right = -2
1 2 3
U = U - 2
Not needed
Right Rotation
Unbalanced at 3
N < U
N < C
left - right = 2
3 2 1
U = U - 2
Not needed
Right-Left Rotation
Unbalanced at 2
N > U
N < C
left - right = -2
2 1 5 4 6 3
U = U - 2
G = G + 1
Left-Right Rotation
Unbalanced at 5
N < U
N > C
left - right = 2
5 2 6 1 4 3
U = U - 2
G = G + 1
For example, I have labelled the following tree with values and the heights of the nodes in parentheses.
You can generate this tree adding nodes in the level order, the first is the original tree, and the second adds the unbalanced node 87.
I have used space delimiters since that is the default for Scanner, and using Scanner.nextInt becomes simple.

44 24 64 16 32 51 88 14 17 28 42 50 54 81 94 12 48 62 78 85 92 96 73 83 86 95
All the nodes in the tree above are balanced.
We will now add 87 to the tree, and from that node up, we recompute the heights and balance factors.

In this case, we see that node 64 is not balanced since the heights of its children are 3 and 5 respectively.
Here, we have labelled those nodes:
  • N (87) - the node just inserted
  • U (64) - the node where the unbalance was detected
  • C (88) - that node's child, which we tracked during the upward path from the inserted node (87)
  • G (81) - the unbalanced node's grandchild, also tracked during the upward path from (87)
  • P (44) - the parent of the unbalanced node.
In this case, we have :
  • N > U and N < C
  • So we should do a Right-Left rotation:
    • Right on C (88), then Left on U (64)
Right on C (88):
  • U right new= C left old (81)
  • C left new = G right old (85)
  • G right new = C (88)
Now left on U (64):
  • P right new = G = U right current (81)
  • U right new = G left = U right left current (78)
  • G left = U (64)


Algorithm:

T = U
U.height = U.height - 2
if N > U
  if N < U.right
    U.right = Right Rotation on U.right (U.right.left++)
  T = Left Rotation on U
else
  if N > U.left
    U.left = Left Rotation on U.left (U.left.right++)
  T = Right Rotation on U
return T