Welcome to Programming and Data Structures

Before we can implement self-balancing trees, we need to understand what it means for a tree to be balanced. When we say “balance”, are we referring to the relative size of the left and right subtrees? Or are we talking about their heights?

Consider the two figures below. In which situation is the 10 node more balanced?

The reason we want to keep a tree balanced is to ensure that we can perform operations like insertion, deletion, and lookup in logarithmic time. The time it takes to perform these operations is proportional to the height of the tree. Therefore, what we really care about is keeping the height of the tree as small as possible. Balance is just a tool to help us achieve that goal.

From the perspective of tree height, the second figure shows a more balanced tree. In it, from the 10 node, the longest path in either direction is 3. It is also instructive to consider how balanced the subtrees themselves are. In the first figure, while there are 7 nodes on each side, if we descend one step to the left, we reach a node that has 6 nodes to the left and none to the right. Because a tree is a recursive structure, we want the balance to be maintained at all levels, not just at the root.

Given this, our definition of balance will focus on the heights of the left and right subtrees. For any node in the tree, we will say that it is balanced if the heights of its left and right subtrees are equal to each other. Because it is often impossible to maintain perfect balance during insertions and deletions, we will have to allow for some leeway. Different self-balancing tree algorithms use different definitions of balance, but they all revolve around the idea of keeping the heights of the left and right subtrees within some acceptable range.