Data Structures and Algorithms Lecture Notes

6 April 2011 • Balancing Trees


More precisely, a binary tree is height balanced if the heights of any two sibling subtrees in the tree differ by at most one.

There are other measures of binary-tree balance. The simplest is to require a tree of n nodes to have height ⌈log (n + 1)⌉, which guarantees searching has logarithmic worst-case behavior. Unfortunately, it also means that inserting and deleting may have linear worst-case behavior because they have to completely reconstruct an unbalanced tree.

Weight balance is another, more useful, balance definition. A binary tree’s weight is the number of nil child pointers (usually referred to as external nodes). Weight balance is specified in terms of the ratio of a tree’s weight to the weight of one of its children and is required to fall in some closed interval (e.g. [α, 1 - α] for some fixed α > 0).


This page last modified on 2006 January 24.