TAOCP 6.2.3 Exercise 15
Let $T$ be the binary search tree representing an ordered linear list, with fields $\text{KEY}(P)$ and $\text{RANK}(P)$ in each node $P$.
Exercise 15. [18] [18] (C. A. Crane.) Suppose that an ordered linear list is being represented as a binary tree, with both KEY and RANK fields in each node. Design an algorithm that searches the tree for a given key, K, and determines the position of K in the list; that is, it finds the number m such that K is the mth smallest key.
Verified: no
Solve time: 1m12s
Solution
Let $T$ be the binary search tree representing an ordered linear list, with fields $\text{KEY}(P)$ and $\text{RANK}(P)$ in each node $P$. The tree satisfies the search-tree property: if $Q$ is in the left subtree of $P$, then $\text{KEY}(Q) < \text{KEY}(P)$, and if $Q$ is in the right subtree, then $\text{KEY}(Q) > \text{KEY}(P)$.
Assume $\text{RANK}(P)$ is defined as the number of nodes in the subtree rooted at $P$ that are $\le \text{KEY}(P)$ in inorder position, equivalently $\text{RANK}(P) = 1 +$ (number of nodes in the left subtree of $P$). This interpretation is consistent with its use in list representation, since it makes $\text{RANK}(P)$ the local inorder position of $P$ within its subtree.
The goal is to determine, for a given key $K$, the integer $m$ such that $K$ is the $m$th smallest key in the entire tree, assuming $K$ occurs in the tree.
The algorithm maintains a pointer $P$ that descends the tree and an accumulator $r$.
Algorithm
A1. Set $P \leftarrow \text{RLINK}(\text{HEAD})$, $r \leftarrow 0$.
A2. If $P = \Lambda$, the search terminates unsuccessfully.
A3. If $K < \text{KEY}(P)$, set $P \leftarrow \text{LLINK}(P)$ and go to A2.
A4. If $K > \text{KEY}(P)$, set $r \leftarrow r + \text{RANK}(P)$, then set $P \leftarrow \text{RLINK}(P)$ and go to A2.
A5. If $K = \text{KEY}(P)$, the required position is $m = r + \text{RANK}(P)$.
Correctness proof
Let $P_0, P_1, \dots, P_t$ be the sequence of nodes visited by the algorithm, where $P_0 = \text{RLINK}(\text{HEAD})$ and $P_t = P$ is the node where $\text{KEY}(P) = K$.
Define $r_i$ as the value of $r$ after visiting $P_i$.
The invariant is that $r_i$ equals the number of nodes in the original tree whose keys are strictly less than $\text{KEY}(P_i)$ and which do not lie in the subtree rooted at $P_i$.
For the initial state, $r_0 = 0$, and no node lies outside the subtree rooted at $P_0$, so the invariant holds.
Assume the invariant holds at $P_i$.
If the next step moves from $P_i$ to its left child $Q$, then all nodes in the right subtree of $Q$ and $Q$ itself are still within the subtree of $P_i$, and no additional node less than $\text{KEY}(Q)$ lies outside the subtree of $Q$ beyond those already counted. Since no update is made to $r$, the invariant is preserved.
If the next step moves from $P_i$ to its right child $Q$, then every node in the left subtree of $P_i$ together with $P_i$ itself precedes $Q$ in inorder traversal and lies outside the subtree rooted at $Q$. The number of such nodes is exactly $\text{RANK}(P_i)$ by definition of the rank field. Since the update is $r_{i+1} = r_i + \text{RANK}(P_i)$, the invariant holds for $P_{i+1}$.
When the algorithm reaches $P_t$ with $\text{KEY}(P_t) = K$, every node in the left subtree of $P_t$ together with all nodes accumulated in $r_t$ precede $P_t$ in inorder order. The number of nodes in the left subtree of $P_t$ plus $1$ equals $\text{RANK}(P_t)$. Hence the total number of nodes less than or equal to $K$ is $r_t + \text{RANK}(P_t)$, which is exactly the inorder position of $K$.
Therefore $m = r + \text{RANK}(P)$ when $K = \text{KEY}(P)$, and the algorithm returns the correct rank.
This completes the proof. ∎