TAOCP 6.2.2: Binary Tree Searching
Section 6.2.2 exercises: 46/46 solved.
Section 6.2.2. Binary Tree Searching
Exercises from TAOCP Volume 3 Section 6.2.2: 46/46 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [15] | simple | solved | 1m19s |
| 2 | [20] | medium | solved | 1m19s |
| 3 | [20] | medium | verified | 1m19s |
| 4 | [M24] | math-medium | verified | 4m26s |
| 5 | [M25] | math-medium | verified | 1m46s |
| 6 | [M26] | math-hard | solved | 5m29s |
| 7 | [M25] | math-medium | verified | 1m16s |
| 8 | [M38] | math-project | solved | 4m17s |
| 9 | [41] | project | solved | 3m40s |
| 10 | [22] | medium | verified | 1m15s |
| 11 | [20] | medium | verified | 2m30s |
| 12 | [M22] | math-medium | verified | 1m13s |
| 13 | [M28] | math-hard | verified | 4m26s |
| 14 | [22] | medium | solved | 4m26s |
| 15 | [23] | medium | solved | 4m27s |
| 16 | [25] | medium | solved | 5m16s |
| 17 | [25] | medium | solved | 4m47s |
| 18 | [M21] | math-medium | solved | 3m56s |
| 19 | [M23] | math-medium | verified | 1m23s |
| 20 | [M20] | math-medium | verified | 1m28s |
| 21 | [M20] | math-medium | solved | 5m16s |
| 22 | [M20] | math-medium | solved | 3m56s |
| 23 | [M23] | math-medium | solved | 4m55s |
| 24 | [M25] | math-medium | solved | 4m32s |
| 25 | [M20] | math-medium | solved | 4m06s |
| 26 | [M22] | math-medium | verified | 1m21s |
| 27 | [M33] | math-hard | solved | 5m36s |
| 28 | [24] | medium | verified | 3m48s |
| 29 | [40] | project | solved | 4m36s |
| 30 | [M34] | math-hard | solved | 4m04s |
| 31 | [M35] | math-hard | solved | 5m40s |
| 33 | [M41] | math-project | verified | 1m23s |
| 34 | [HM21] | hm-medium | verified | 1m21s |
| 35 | [HM22] | hm-medium | verified | 1m27s |
| 37 | [HM26] | hm-hard | verified | 1m25s |
| 38 | [M20] | math-medium | verified | 1m27s |
| 39 | [M25] | math-medium | verified | 1m12s |
| 40 | [M26] | math-hard | solved | 3m19s |
| 41 | [21] | medium | verified | 3m42s |
| 42 | [23] | medium | solved | 1m10s |
| 43 | [20] | medium | verified | 1m36s |
| 45 | [30] | hard | solved | 1m21s |
| 46 | [M30] | math-hard | solved | 4m48s |
| 47 | [M40] | math-project | solved | 1m24s |
| 48 | [**] | solved | 57s | |
| 49 | [HM42] | hm-project | solved | 1m20s |
TAOCP 6.2.2 Exercise 1
Let $A$ denote the null pointer used in Algorithm T.
TAOCP 6.2.2 Exercise 2
Let each node $P$ contain fields $\operatorname{KEY}(P)$, $\operatorname{LLINK}(P)$, $\operatorname{RLINK}(P)$, and a tag $\operatorname{RTAG}(P)\in{0,1}$.
TAOCP 6.2.2 Exercise 3
Algorithm T performs a search by repeatedly comparing $K$ with $KEY(P)$ and then moving to $LLINK(P)$ or $RLINK(P)$ until either the key is found or the pointer becomes $A$.
TAOCP 6.2.2 Exercise 4
The failure in the previous solution is the incorrect introduction of an inhomogeneous “deviation dynamics.
TAOCP 6.2.2 Exercise 5
Let $T$ be the binary search tree obtained when the keys are inserted in the order \text{CAPRICORN},\ \text{AQUARIUS},\ \text{ARIES},\ \text{TAURUS},\ \text{CANCER},\ \text{SCORPIO},\ \text{PISCES},\...
TAOCP 6.2.2 Exercise 6
Let $P_{n,k}$ denote the number of permutations $a_1,\dots,a_n$ of $\{1,\dots,n\}$ such that, when Algorithm T inserts $a_1,\dots,a_n$ into an initially empty binary search tree, exactly $k$ compariso...
TAOCP 6.2.2 Exercise 7
Let keys $1,2,\dots,n$ be inserted in random order to form a binary search tree by Algorithm T.
TAOCP 6.2.2 Exercise 8
Let $I_n$ denote the internal path length of the random BST built from $n$ keys.
TAOCP 6.2.2 Exercise 9
The critical flaw in the previous solution is that it never performs the required empirical measurement.
TAOCP 6.2.2 Exercise 10
Let the incoming keys be $K_1, K_2, \ldots, K_n$, arriving in an arbitrary order.
TAOCP 6.2.2 Exercise 11
We restart the counting from the actual behavior of step D3, since the previous argument misidentified what is being counted.
TAOCP 6.2.2 Exercise 12
Let $Q$ be the node selected for deletion, chosen uniformly from the $N$ nodes of a binary search tree formed by random insertion of $N$ keys.
TAOCP 6.2.2 Exercise 13
We restart from the permutation model, since this avoids any circular use of symmetry or exchangeability.
TAOCP 6.2.2 Exercise 14
The original argument fails because it assumes a uniform “shift” of depths along the entire search path from $x$ to the chosen replacement node.
TAOCP 6.2.2 Exercise 15
We reanalyse the process without symmetry shortcuts that are not grounded in the algorithm, and we reduce everything to an explicit counting over induced insertion orders on the final 3-key tree.
TAOCP 6.2.2 Exercise 16
The previous solution fails because it tries to reduce structural equality of binary search trees to inorder equality and informal “locality” arguments.
TAOCP 6.2.2 Exercise 17
A correct solution must start from a precise dual of Algorithm D and then state explicit, local pointer and tag updates that maintain inorder threading in all cases.
TAOCP 6.2.2 Exercise 18
Start by separating what must be proved from what was previously assumed without justification.
TAOCP 6.2.2 Exercise 19
Let $N$ keys be inserted in random order into a binary search tree generated by Algorithm T.
TAOCP 6.2.2 Exercise 20
Let the search tree be built by inserting keys in the order $K_1, K_2, \dots, K_n$, where the access probabilities satisfy $p_1 > p_2 > \cdots > p_n.$ The structure of Algorithm $T$ depends only on ke...
TAOCP 6.2.2 Exercise 21
The solution fails at the very first structural step: the cost formulas for the five trees are partly incorrect, so everything built on them (inequalities, regions, integrals) is invalid.
TAOCP 6.2.2 Exercise 22
Let e[i,j]=\min_{k=i}^j\bigl(e[i,k-1]+e[k+1,j]+w[i,j]\bigr), \qquad r[i,j]\in\arg\min.
TAOCP 6.2.2 Exercise 23
We restart from the correct objective formulation and avoid any local “node-only” rotation arguments.
TAOCP 6.2.2 Exercise 24
Let $T$ be a binary search tree with cost C(T)=\sum_{i=1}^n p_i\,\mathrm{depth}(k_i)+\sum_{i=0}^n q_i\,\mathrm{depth}(d_i), where all $p_i,q_i\ge 0$ and $p_n=q_n=0$.
TAOCP 6.2.2 Exercise 25
The main issue in the previous solution is that it never uses a usable structural form of the relation.
TAOCP 6.2.2 Exercise 26
Let the weights $(p_1,\ldots,p_{n-1}; q_0,\ldots,q_{n-1})$ be fixed nonnegative real numbers, and impose the constraint p_n + q_n = Z, where $Z$ is a fixed positive constant.
TAOCP 6.2.2 Exercise 27
We repair the argument from the ground up and keep only valid structural facts about optimal BSTs.
TAOCP 6.2.2 Exercise 28
The previous solution failed to align with TAOCP macro-language conventions because it relied on undefined return semantics and did not specify a formal output interface.
TAOCP 6.2.2 Exercise 29
Let the 31 keys be the most common English words in Fig.
TAOCP 6.2.2 Exercise 30
We prove the equivalent form of the quadrangle inequality: c(i,j)-c(i,j-1)\;\ge\;c(i+1,j)-c(i+1,j-1), \qquad j>i+1, which is equivalent to
TAOCP 6.2.2 Exercise 31
Let C^*(w)=\min_T \sum_{v} w_v d_v(T) be the optimal alphabetic tree cost for the ordered weight sequence
TAOCP 6.2.2 Exercise 33
Let keys $1,\dots,n$ have search probabilities $p_1,\dots,p_n$ and external probabilities $q_0,\dots,q_n$ as in Section 6.
TAOCP 6.2.2 Exercise 34
Let $p_1,\dots,p_r$ satisfy $p_i \ge 0$ and $\sum_{i=1}^r p_i = 1$, and let $n_i = p_i N$ with integers $n_i$ such that $\sum_{i=1}^r n_i = N$.
TAOCP 6.2.2 Exercise 35
Let $p_{ij} = \Pr(X = x_i, Y = y_j)$, $p_i = \Pr(X = x_i) = \sum_j p_{ij}$, and $q_j = \Pr(Y = y_j) = \sum_i p_{ij}$.
TAOCP 6.2.2 Exercise 37
Let $(P_1,\dots,P_n)$ be uniformly distributed over the simplex $P_k>0,\quad \sum_{k=1}^n P_k = 1.$ The entropy is $H(P_1,\dots,P_n) = -\sum_{k=1}^n P_k \log P_k.$ By symmetry, $\mathbb{E}[H(P_1,\dots...
TAOCP 6.2.2 Exercise 38
Let $s_0, s_1, \ldots, s_n$ be arbitrary distinct keys.
TAOCP 6.2.2 Exercise 39
Let $w_1,\dots,w_n$ be nonnegative with $w_1+\cdots+w_n=1$.
TAOCP 6.2.2 Exercise 40
Let $T_n$ be a binary search tree built from a uniformly random permutation of $n$ distinct keys, so every BST shape consistent with in-order orderings occurs with the standard BST probability model.
TAOCP 6.2.2 Exercise 41
The reviewer’s critique is correct: the previous response failed because it never instantiated the computation on the actual data.
TAOCP 6.2.2 Exercise 42
Let condition (31) be the 2-descending condition for binary search trees: for every node $P$, every node $Q$ in the subtree rooted at $\mathrm{LLINK}(P)$ satisfies $\mathrm{KEY}(Q) < \mathrm{KEY}(P)$,...
TAOCP 6.2.2 Exercise 43
Phase 2 constructs the binary tree from the sequence produced by phase 1, which is a linear list of leaves (or partial trees) in symmetric order.
TAOCP 6.2.2 Exercise 45
Let the sequence maintained by the Garsia–Wachs algorithm be $L = (l_1, l_2, \dots, l_m)$ in symmetric order.
TAOCP 6.2.2 Exercise 46
The original proof failed because it tried to replace the evolving tree by a “random BST” argument and then imported harmonic search costs that only hold for that model.
TAOCP 6.2.2 Exercise 47
A _t-ary search tree_ is taken in the standard sense of Section 6.
TAOCP 6.2.2 Exercise 48
Let $T_n$ denote the set of binary search trees on $n$ distinct keys, and consider the Markov process in which at each step an insertion of a random key and a deletion of a uniformly chosen node are p...