TAOCP 6.3 Exercise 6
Algorithm D inserts keys one at a time.
Section 6.3: Digital Searching
Exercise 6. [15] [15] What digital search tree is obtained if the fifteen 4-bit binary keys 0001, 0010, 0011, ..., 1111 are inserted in increasing order by Algorithm D? (Start with 0001 at the root and then do fourteen insertions.)
- [M26] If the fifteen keys of exercise 6 are inserted in a different order, we might get a different tree. Of all the 15! possible permutations of these keys, which is the worst, in the sense that it produces a tree with the greatest internal path length?
Verified: no
Solve time: 4m02s
Solution
Algorithm D inserts keys one at a time. When a key reaches a node at level $j$, the $(j+1)$st bit determines whether the search proceeds to the left or right link. If that link is empty, the new key is inserted there; otherwise the process continues at the next node. Thus the structure depends on the insertion order and must be obtained by tracing the fourteen insertions.
The keys are inserted in increasing order,
$$ 0001,0010,0011,\ldots,1111. $$
Start with
$$ 0001 $$
as the root.
Insertion of $0010$
At the root $0001$, the first bit of $0010$ is $0$, so the left link is used.
It is empty, hence $0010$ becomes the left child of $0001$:
$$ 0001 \longleftarrow 0010. $$
Insertion of $0011$
At $0001$, bit $1$ is $0$, so we go left to $0010$.
At $0010$, bit $2$ is $0$, hence the left link is chosen.
It is empty, therefore $0011$ is inserted as the left child of $0010$:
$$ 0001 \longleftarrow 0010 \longleftarrow 0011. $$
Insertion of $0100$
At $0001$, bit $1$ is $0$, so we go to $0010$.
At $0010$, bit $2$ is $1$, hence the right link is chosen.
It is empty, therefore $0100$ becomes the right child of $0010$.
Insertion of $0101$
The path is
$$ 0001 \rightarrow 0010 \rightarrow 0100. $$
At $0100$, bit $3$ of $0101$ is $0$, so the left link is used and $0101$ is inserted there.
Insertion of $0110$
The path is again
$$ 0001 \rightarrow 0010 \rightarrow 0100. $$
At $0100$, bit $3$ of $0110$ is $1$, so $0110$ becomes the right child of $0100$.
Insertion of $0111$
The path is
$$ 0001\rightarrow0010\rightarrow0100\rightarrow0110. $$
At level $3$, the fourth bit of $0111$ is $1$, so $0111$ is inserted as the right child of $0110$.
Insertion of $1000$
At the root $0001$, the first bit is $1$, so the right link is used.
Since it is empty, $1000$ becomes the right child of the root.
Insertion of $1001$
The path is
$$ 0001\rightarrow1000. $$
At $1000$, bit $2$ is $0$, hence $1001$ becomes the left child of $1000$.
Insertion of $1010$
The path is
$$ 0001\rightarrow1000\rightarrow1001. $$
At $1001$, bit $3$ is $1$, so $1010$ becomes the right child of $1001$.
Insertion of $1011$
The path is
$$ 0001\rightarrow1000\rightarrow1001\rightarrow1010. $$
At $1010$, bit $4$ is $1$, hence $1011$ becomes the right child of $1010$.
Insertion of $1100$
The path is
$$ 0001\rightarrow1000. $$
At $1000$, bit $2$ is $1$, so $1100$ is inserted as the right child of $1000$.
Insertion of $1101$
The path is
$$ 0001\rightarrow1000\rightarrow1100. $$
At $1100$, bit $3$ is $0$, hence $1101$ becomes the left child of $1100$.
Insertion of $1110$
The path is
$$ 0001\rightarrow1000\rightarrow1100. $$
At $1100$, bit $3$ is $1$, so $1110$ becomes the right child of $1100$.
Insertion of $1111$
The path is
$$ 0001\rightarrow1000\rightarrow1100\rightarrow1110. $$
At $1110$, bit $4$ is $1$, therefore $1111$ becomes the right child of $1110$.
Hence the digital search tree obtained from the insertion sequence
$$ 0001,0010,0011,\ldots,1111 $$
is
$$ \boxed{ \begin{array}{c} 0001\[1mm] /\qquad\backslash\[1mm] 0010\qquad1000\[1mm] /\ \backslash\qquad/\ \backslash\[1mm] 0011\quad0100\qquad1001\quad1100\[1mm] \qquad/\ \backslash\qquad\qquad\backslash\qquad/\ \backslash\[1mm] \qquad0101\quad0110\qquad1010\qquad1101\quad1110\[1mm] \qquad\qquad\backslash\qquad\qquad\qquad\backslash\qquad\qquad\backslash\[1mm] \qquad\qquad0111\qquad\qquad\qquad1011\qquad\qquad1111 \end{array}} $$
This tree contains each of the fifteen keys exactly once and is obtained by following Algorithm D step by step.