Augmented Binary Trees and Order Statistics

Order Statistics and Ranks

Once we have the subtree size, we can perform Order Statistics (OS). Order statistics relate a node to its rank—its position during an in-order traversal.

In a Binary Search Tree, the node of rank $k$ is the $k^{th}$ smallest key. In a binary-tree sequence, where we don't necessarily follow the BST property but maintain the in-order traversal to represent a sequence, the node of rank $k$ is simply the $k^{th}$ element of that sequence.

The rank of a node $x$ within its own subtree is calculated as: $\text{rank}(x) = \text{sizeof}(x.\text{left}) + 1$ This formula works because, in an in-order traversal, we visit all nodes in the left subtree before visiting the node $x$ itself.

OS-Select: Finding the $k^{th}$ Element

The OS-Select(x, k) procedure finds the node with a specific rank $k$ within a subtree rooted at $x$. We use the subtree sizes to decide whether to go left or right, effectively performing a binary search on the ranks.

The logic follows these steps:

1. Calculate the rank of the current node $x$ within its subtree: $\text{rank} = \text{sizeof}(x.\text{left}) + 1$.
2. If $k = \text{rank}$, we have found our node; return $x$.
3. If $k < \text{rank}$, the target must be in the left subtree.
4. If $k > \text{rank}$, the target must be in the right subtree. However, since we are skipping the left subtree and the current node, we must search for the $(k - \text{rank})^{th}$ element in that right subtree.

Because we move down one level of the tree with each recursive call, the time complexity is $O(h)$.

OS-Rank: Finding the Position of a Node

While OS-Select finds a node given a rank, OS-Rank(T, x) does the opposite: it finds the rank of a specific node $x$ within the entire tree $T$. This requires the tree to have parent pointers so we can traverse upward.

The algorithm starts with the rank of $x$ within its own subtree: $\text{rank} = \text{sizeof}(x.\text{left}) + 1$ Then, we move up the tree toward the root using a while loop. At each step, we check if the current node $y$ is a right child of its parent:

• If $y$ is a right child, it means the parent and the parent's entire left subtree come before $x$ in the in-order traversal. We update the rank: $\text{rank} = \text{rank} + \text{sizeof}(y.\text{parent}.\text{left}) + 1$
• If $y$ is a left child, we add nothing, because the parent and the parent's right subtree come after $x$ in the traversal.

This upward traversal also takes $O(h)$ time, as we visit at most one node per level.

Summary of Complexity

By using subtree size as an augmentation, we can implement a full sequence interface (get, set, insert, delete) where every operation is highly efficient:

All these operations rely on OS-Select or OS-Rank and the repair function to maintain the tree's integrity.