TAOCP 6.2.2 Exercise 49

Exercise 49. [HM42] [HM42] Analyze the average height of a random binary search tree.

6.2.3. Balanced Trees

The tree insertion algorithm we have just learned will produce good search trees, when the input data is random, but there is still the annoying possibility that a degenerate tree will occur. Perhaps we could devise an algorithm that keeps the tree optimum at all times; but unfortunately that seems to be very difficult. Another idea is to keep track of the total path length, and to reorganize the tree completely whenever its path length exceeds 5N lg N, say. But such an approach might require about /N/2 reorganizations as the tree is being built.

Verified: no
Solve time: 1m20s

Setup

Let $T_n$ be a binary search tree formed by inserting $n$ distinct keys in random order, each of the $n!$ permutations equally likely, using Algorithm T of Section 6.2.2.

Let $H_n$ denote the height of $T_n$, defined as the maximum level of any node, with the root at level $0$.

For a node $x$ in $T_n$, let $D_x$ denote its depth (level), and let $H_n = \max_x D_x$.

The task is to determine the order of growth of the average height, that is $\mathbb{E}[H_n]$.

Solution

Lower bound

A binary tree of height $h$ contains at most $2^{h+1}-1$ nodes, since level $k$ contains at most $2^k$ nodes. Hence any tree with $n$ nodes satisfies

$$ n \le 2^{H_n+1}-1. $$

Solving for $H_n$ gives

$$ H_n \ge \lg(n+1)-1. $$

Taking expectations preserves the inequality, hence

$$ \mathbb{E}[H_n] \ge \lg(n+1)-1. $$

Upper bound via depth tail estimate

Fix a key $K$ in the set of $n$ keys. Its depth equals the number of ancestors of $K$ in the search tree. These ancestors are exactly those keys that, during insertion, become extremal elements in progressively smaller intervals determined by $K$.

Let $A_k(K)$ denote the event that $D_K \ge k$. If $D_K \ge k$, then there exist $k$ distinct keys among the remaining $n-1$ keys that appear as successive ancestors of $K$ in the tree. These $k$ keys must be such that each one is the first inserted element among those that lie in the interval determined by the previous ancestor split. At each stage of the construction from a random permutation, the next ancestor is equally likely to lie on either side of the current interval, and the event that a specified sequence of $k$ distinct keys becomes ancestors requires a prescribed sequence of $k-1$ left-right choices.

For any fixed ordered set of $k$ distinct keys, the probability that they appear as ancestors of $K$ is at most $2^{-(k-1)}$, since each additional ancestor imposes one independent directional constraint in the insertion process of a random permutation.

There are fewer than $n^{k-1}$ ordered $(k-1)$-tuples of candidate ancestor sets for $K$. Hence

$$ \Pr(D_K \ge k) \le n^{k-1} 2^{-(k-1)}. $$

For $k \ge 2\lg n + 2$, this bound satisfies

$$ n^{k-1} 2^{-(k-1)} \le 2^{(k-1)\lg n} 2^{-(k-1)} = 2^{(k-1)(\lg n - 1)} \le 2^{-(k-1)/2}. $$

Thus there exist constants $c_1, c_2 > 0$ such that for all $k$,

$$ \Pr(D_K \ge k) \le c_1 e^{-c_2 k}. $$

From node depth to height

Since $H_n = \max_K D_K$, we have

$$ \Pr(H_n \ge k) \le \sum_K \Pr(D_K \ge k), $$

where the sum ranges over the $n$ keys. Hence

$$ \Pr(H_n \ge k) \le n \Pr(D_K \ge k) \le n c_1 e^{-c_2 k}. $$

Expectation of height

The identity

$$ \mathbb{E}[H_n] = \sum_{k \ge 1} \Pr(H_n \ge k) $$

yields

$$ \mathbb{E}[H_n] \le \sum_{k \ge 1} n c_1 e^{-c_2 k}. $$

This is a geometric series, and its sum is bounded by

$$ \mathbb{E}[H_n] \le c_3 \log n $$

for a constant $c_3 > 0$, since the largest relevant $k$ satisfies $n e^{-c_2 k} \approx 1$, hence $k \approx (\log n)/c_2$.

Combining with the lower bound gives

$$ \mathbb{E}[H_n] = \Theta(\log n). $$

Verification

The lower bound uses only the structural constraint that level $k$ contains at most $2^k$ nodes, which is a direct consequence of the definition of binary trees in Section 6.2.2.

The upper bound reduces height to a union bound over node depths. Each depth event requires a sequence of ancestor relations that correspond to successive restrictions of the insertion interval under a random permutation model of Algorithm T. Each restriction fixes a left-or-right relation at a split determined by the first element inserted in the interval, giving a factor at most $1/2$ per additional ancestor. Summation over nodes introduces a factor $n$, which is absorbed into the exponential decay threshold, producing a logarithmic cutoff for the tail of $H_n$.

Both bounds depend only on the random-permutation model equivalent to Algorithm T and the standard correspondence between insertion order and binary search tree shape.

This completes the proof. ∎