TAOCP 6.2.3 Exercise 13
Storing the index of each node as its key forces the keys to represent a global linear order.
Exercise 13. [05] [05] Why is it better to use RANK fields as defined in the text, instead of simply to store the index of each node as its key (calling the first node “1”, the second node “2”, and so on)?
Verified: yes
Solve time: 1m31s
Storing the index of each node as its key forces the keys to represent a global linear order. After an insertion at position $k$, every node whose index is greater than or equal to $k$ must have its key increased by $1$, and after a deletion, all subsequent keys must be decreased by $1$. In a tree representation this requires updating $\Theta(N)$ nodes in the worst case, since a large fraction of the tree may lie in the affected suffix of the ordering. The cost is therefore incompatible with the $O(\log N)$ bounds intended for the operations in this section.
A RANK field, defined locally as the number of nodes in a subtree (or equivalently the number of preceding elements in symmetric order), avoids global renumbering. After an insertion or deletion, only nodes on the search path from the root to the modified position require adjustment of their RANK values, since only subtree sizes along that path change. These updates are therefore confined to $O(\log N)$ nodes in a balanced tree, and the same information permits finding the $k$th element directly by comparing $k$ with the rank of the left subtree at each step. This preserves efficient implementation of all four list operations described in Section 6.2.3. ∎