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$.
Section 6.2.2: Binary Tree Searching
Exercise 3. [20] [20] In Section 6.1 we found that a slight change to the sequential search Algorithm 6.15 made it faster (Algorithm 6.1Q). Can a similar trick be used to speed up Algorithm T?
Verified: yes
Solve time: 1m19s
Solution
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$. In its direct form, each iteration also requires a test of whether the link just followed is $A$, since the algorithm must detect unsuccessful search.
The same style of improvement used for sequential search (Algorithm 6.1Q) replaces a terminating condition check by a guaranteed hit using a sentinel. A parallel modification applies to Algorithm T by eliminating the need to test for $A$ at every step.
Replace each occurrence of $A$ in $LLINK$ or $RLINK$ by a distinguished external node $E$ such that $LLINK(E) = RLINK(E) = E$ and $KEY(E)$ is defined to lie outside the range of all admissible keys, for example larger than every key in the table. Every null subtree is represented by such an external node. The tree then becomes a full binary tree in which every internal node has two children.
The search procedure is modified so that step T2 always follows a link without testing whether it is $A$, since no pointer is ever null. The termination condition is reduced to a single comparison with the external node: the search stops when $P = E$ or when $KEY(P) = K$ holds.
Under this representation, each descent in the tree removes the explicit test for null pointers that is present in the original formulation of Algorithm T. The number of key comparisons remains unchanged, since each visited node still requires comparison of $K$ with $KEY(P)$, but one pointer test per step is eliminated.
This modification is therefore a direct analogue of Algorithm 6.1Q: it does not change the asymptotic behavior of the search, but it reduces the constant factor in the running time by removing the explicit $A$-test during traversal. ∎