The AVL algorithm for balancing a Binary Search Tree.

By Nicholas Duchon, Oct 14, 2011

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.
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.

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.

We begin with the node just inserted and go up the tree looking for a node that is not balanced:
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:

Algorithm:

Removing the links:


Ordering {A, B, C}:


Connection P to middle, then middle to left and right of {A, B, C}:


Moving the T's around a little:


Connecting the T's:


Recomputing the heights