TAOCP 6.2.1 Exercise 12

Let $N=12$.

taocpmathematicsalgorithmsvolume-3medium

Section 6.2.1: Searching an Ordered Table

Exercise 12. [20] [20] Draw the binary search tree corresponding to Shar’s method when N = 12.

Verified: yes
Solve time: 1m42s

Solution

Let $N=12$. Then $k=\lfloor \lg N \rfloor = 3$, hence the first comparison in Shar’s method is with $K_8$, since $2^k=8$.

The first step splits the table into the left interval $1 \le i \le 7$ and the right interval $9 \le i \le 12$.

Left subtree ($K < K_8$)

In this case Shar’s method applies a uniform scheme with differences

$4,2,1,0,$

corresponding to $2^{k-1},2^{k-2},2^{k-3},0$.

The induced comparison structure is the uniform binary tree on the indices $1,\dots,7$ centered at $4$, and then refined symmetrically.

Starting from $i=8$:

  • first comparison is with $K_4$;
  • from $4$, the next level splits to $2$ and $6$;
  • from $2$, the next splits to $1$ and $3$;
  • from $6$, the next splits to $5$ and $7$.

Thus the left subtree is:

$$ 8 \to 4,\quad 4 \to (2,6),\quad 2 \to (1,3),\quad 6 \to (5,7). $$

Each arrow represents a comparison node whose outgoing edges correspond to $K<K_i$ (left) and $K>K_i$ (right) within the restricted interval.

Right subtree ($K > K_8$)

Here Shar’s method resets the index to

$i' = N+1-2^k = 13-8 = 5,$

and applies a uniform scheme with differences

$2,1,0.$

This corresponds to a uniform binary search on the remaining four elements $9,10,11,12$.

The structure is the same shape as a uniform tree of size $4$, but translated into the index interval $9$ to $12$. The comparison pattern is:

  • first comparison corresponds to the midpoint of the block, namely $K_{11}$;
  • then the interval splits into singletons according to offsets $\pm 2$ and $\pm 1$ within the shifted block.

Writing the induced comparisons explicitly in index form gives:

$$ 8 \to 11,\quad 11 \to (9,12),\quad 9 \to 10. $$

Here $11$ is the first node in the right subtree, and it partitions ${9,10,11,12}$ into ${9,10}$ and ${12}$; the subsequent refinement yields the comparison between $9$ and $10$.

Final tree

Combining both parts, the full comparison tree is:

$$ \begin{array}{c} 8 \ / \quad \backslash \ 4 \quad 11 \ / \ \quad / \ \ 2 \ 6 \ 9 \ 12 \ / \ \ / \ 1 \ 3 \ 10 \ (5,7\ \text{attached to left subtree as below}) \end{array} $$

More explicitly in full expanded form:

$$ \begin{aligned} &8 \to 4,; 11 \ &4 \to 2,; 6 \ &2 \to 1,; 3 \ &6 \to 5,; 7 \ &11 \to 9,; 12 \ &9 \to 10 \end{aligned} $$

This completes the construction of Shar’s binary search tree for $N=12$. ∎