Balancing Binary Search Trees¶

We can make the search, insert, and remove operations to work in time \( \Oh{\Lg n} \), where \( n \) is the number of the keys in the tree, by balancing the trees. Balancing ensures that the height of the BST is \( \Oh{\Lg n} \). Many variants of balanced BSTs have been proposed, see, for instance, this wikipedia link. In the following sections, we’ll see

AVL trees, which were the first balanced BSTs, and
red-black trees, which are commonly used in many standard libraries.

However, we first show the key technique used in balancing both of these BST classes: rotations.

Rotations¶

A common operation used when balancing BSTs is rotation.

In left rotation of a node \( x \) with a right child \( y \), we transform the sub-tree rooted at \( x \) so that
- \( y \) becomes the root of the sub-tree,
- \( x \) becomes the left child of \( y \), and
- the left child of \( y \) becomes the right child of \( x \).
The right rotation is the dual operation for a node with a left child.

The figure below shows the rotattions graphically. The shaded triangles denote sub-trees and can be empty.

A key fact is that the left and right rotations preserve the BST property: If the BST property holds before a rotation, then it holds after the rotation. We can see this from the figure above for left rotation as follows:

Traversing the nodes in the subtree in inorder before the left rotation gives the keys in subtree 1, that of \( x \), those in subtree 2, that of \( y \) and those in subtree 3.
Traversing the nodes in the subtree in inorder after the left rotation gives the keys in subtree 1, that of \( x \), those in subtree 2, that of \( y \) and those in subtree 3.

A similar analysis can be performed for the right rotation.