# 12.4 Randomly built binary search trees

## 12.4-1

Prove equation $\text{(12.3)}$.

The equation is

$$\sum_{i = 0}^{n - 1} \binom{i + 3}{3} = \binom{n + 3}{4}. \tag{12.3}$$

\begin{aligned} \sum_{i = 0}^{n - 1} \binom{i + 3}{3} & = \sum_{i = 0}^{n - 1} \frac{(i + 3)(i + 2)(i + 1)}{6} \\ & = \frac{1}{6} \sum_{i = 0}^{n - 1} i^3 + 6i^2 + 11i + 6 \\ & = \frac{1}{6} (\frac{(n - 1)^2 n^2}{4} + \frac{6(n - 1)n(2n - 1)}{6} + \frac{11n(n - 1)}{2} + 6n) \\ & = \frac{n(n + 1)(n + 2)(n + 3)}{24} \\ & = \binom{n + 3}{4}. \end{aligned}

## 12.4-2

Describe a binary search tree on n nodes such that the average depth of a node in the tree is $\Theta(\lg n)$ but the height of the tree is $\omega(\lg n)$. Give an asymptotic upper bound on the height of an $n$-node binary search tree in which the average depth of a node is $\Theta(\lg n)$.

We will answer the second part first. We shall show that if the average depth of a p node is $\Theta(\lg n)$, then the height of the tree is $O(n\lg n)$. Then we will answer the first part by exhibiting that this bound is tight: there is a binary search tree with p average node depth $\Theta(\lg n)$ and height $\Theta(\sqrt{n\lg n}) = \omega(\lg n)$.

Lemma

If the average depth of p a node in an $n$-node binary search tree is $\Theta(\lg n)$, then the height of the tree is $O(\sqrt{n\lg n})$.

Proof

Suppose that an $n$-node binary search tree has average depth $\Theta(\lg n)$ and height $h$. Then there exists a path from the root to a node at depth $h$, and the depths of the nodes on this path are $0, 1, \ldots, h$. Let $P$ be the set of nodes on this path and $Q$ be all other nodes. Then the average depth of a node is

\begin{aligned} \frac{1}{n} \Big(\sum_{x \in P} \text{depth(x)} + \sum_{y \in Q} \text{depth(y)}\Big) & \ge \frac{1}{n} \sum_{x \in P} \text{depth(x)} \\ & = \frac{1}{n} \sum_{d = 0}^h d \\ & = \frac{1}{n} \cdot \Theta(h^2). \end{aligned}

For the purpose of contradiction, suppose that $h$ is not $O(\sqrt{n\lg n})$, so that $h = \omega(\sqrt{n\lg n})$. Then we have

\begin{aligned} \frac{1}{n} \cdot \Theta(h^2) & = \frac{1}{n} \cdot \omega(n\lg n) \\ & = \omega(\lg n), \end{aligned}

which contradicts the assumption that the average depth is $\Theta(\lg n)$. Thus, the height is $O(\sqrt{n\lg n})$.

Here is an example of an $n$-node binary search tree with average node depth $\Theta(\lg n)$ but height $\omega(\lg n)$:

In this tree, $n - \sqrt{n\lg n}$ nodes are a complete binary tree, and the other $\sqrt{n\lg n}$ nodes protrude from below as a single chain. This tree has height

\begin{aligned} \Theta(\lg(n - \sqrt{n\lg n})) + \sqrt{n\lg n} & = \Theta(\sqrt{n\lg n}) \\ & = \omega(\lg n). \end{aligned}

To compute an upper bound on the average depth of a node, we use $O(\lg n)$ as an upper bound on the depth p of each of the $n - \sqrt{n\lg n}$ nodes in the complete binary tree part and $O(\lg n + \sqrt{n\lg n})$ as an upper bound on the depth of each of the $\sqrt{n\lg n}$ nodes in the protruding chain. Thus, the average depth of a node is bounded from above by

\begin{aligned} \frac{1}{n} \cdot O(\sqrt{n\lg n}(\lg n + \sqrt{n\lg n}) + (n - \sqrt{n\lg n})\lg n) & = \frac{1}{n} \cdot O(n\lg n) \\ & = O(\lg n). \end{aligned}

To bound the average depth of a node from below, observe that the bottommost level of the complete binary tree part has $\Theta(n - \sqrt{n - \lg n})$ nodes, and each of these nodes has depth $\Theta(\lg n)$. Thus, the average node depth is at least

\begin{aligned} \frac{1}{n} \cdot \Theta((n - \sqrt{n - \lg n})\lg n) & = \frac{1}{n} \cdot \Omega(n\lg n) \\ & = \Omega(\lg n). \end{aligned}

Because the average node depth is both $O(\lg n)$ and $\Omega(\lg n)$, it is $\Theta(\lg n)$.

## 12.4-3

Show that the notion of a randomly chosen binary search tree on $n$ keys, where each binary search tree of $n$ keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section. ($\textit{Hint:}$ List the possibilities when $n = 3$.)

For $n = 3$, there are $5$ binary search trees. However, if we build the trees will a random permutation, the first tree will built twice.

## 12.4-4

Show that the function $f(x) = 2^x$ is convex.

We'll go one better than showing that the function $2^x$ is convex. Instead, we'll show that the function $c^x$ is convex, for any positive constant $c$. According to the definition of convexity on page 1199 of the text, a function $f(x)$ is convex if for all $x$ and $y$ and for all $0 \le \lambda \le 1$, we have $f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda)f(y)$. Thus, we need to show that for all $0 \le \lambda \le 1$, we have $c^{\lambda x + (1 - \lambda)y} \le \lambda c^x + (1 - \lambda)c^y$.

We start by proving the following lemma.

Lemma

For any real numbers $a$ and $b$ and any positive real number $c$,

$$c^a \ge c^b + (a - b)c^b\ln c.$$

Proof

We first show that for all real $r$, we have $c^r \ge 1 + r\ln c$. By equation $\text{(3.12)}$ from the text, we have $e^x \ge 1 + x$ for all real $x$. Let $x = r\ln c$, so that $e^x = e^{r\ln c} = (e^{\ln c})^r = c^r$. Then we have $c^r = e^{r\ln c} \ge 1 + r\ln c$.

Substituting $a - b$ for $r$ in the above inequality, we have $c^{a - b} \ge 1 + (a - b)\ln c$. Multiplying both sides by $c^b$ gives $c^a \ge c^b + (a - b)c^b\ln c$. (lemma)

Now we can show that $c^{\lambda x + (1 - \lambda)y} \le \lambda c^x + (1 - \lambda)c^y$ for all $0 \le \lambda \le 1$. For convenience, let $z = \lambda x + (1 - \lambda)y$.

In the inequality given by the lemma, substitute $x$ for $a$ and $z$ for $b$, giving

$$c^x \ge c^z + (x - z)c^z\ln c.$$

Also substitute $y$ for $a$ and $z$ for $b$, giving

$$c^y \ge c^z + (y - z)c^z\ln c.$$

If we multiply the first inequality by $\lambda$ and the second by $1 - \lambda$ and then add the resulting inequalities, we get

\begin{aligned} \lambda c^x + (1 - \lambda)c^y & \ge \lambda(c^z + (x - z)c^z\ln c) + (1 - \lambda)(c^z + (y - z)c^z\ln c) \\ & = \lambda c^z + \lambda x c^z\ln c - \lambda z c^z\ln c + (1 - \lambda)c^z + (1 - \lambda)yc^z\ln c - (1 - \lambda)zc^z\ln c \\ & = (\lambda + (1 - \lambda))c^z + (\lambda x + (1 - \lambda)y)c^z\ln c - (\lambda + (1 - \lambda))zc^z\ln c \\ & = c^z + zc^z\ln c - zc^z\ln c \\ & = c^z \\ & = c^{\lambda x + (1 - \lambda)y}, \end{aligned}

as we wished to show.

## 12.4-5 $\star$

Consider $\text{RANDOMIZED-QUICKSORT}$ operating on a sequence of $n$ distinct input numbers. Prove that for any constant $k > 0$, all but $O(1 / n^k)$ of the $n!$ input permutations yield an $O(n\lg n)$ running time.

Let $A(n)$ denote the probability that when quicksorting a list of length $n$, some pivot is selected to not be in the middle $n^{1 - k / 2}$ of the numberes. This doesn't happen with probability $\frac{1}{n^{k / 2}}$. Then, we have that the two subproblems are of size $n_1, n_2$ with $n_1 + n_2 = n - 1$, then

$$A(n) \le \frac{1}{n^{k / 2}} + T(n_1)+T(n_2).$$

Since we bounded the depth by $O(1 / \lg n)$ let $\{a_{i, j}\}_i$ be all the subproblem sizes left at depth $j$,

$$A(n) \le \frac{1}{n^{k / 2}} \sum_j\sum_i \frac{1}{a}.$$