I'm currently going over Robert Sedgewick's Algorithms book. In the book I'm trying to understand the implementation of the select method in a Binary Search Tree. The author uses a BST to implement a symbol table. The author describes the select method as follow:
Suppose that we seek the key of rank k (the key such that precisely k other keys in the BST are smaller). If the number of keys t in the left sub- tree is larger than k, we look (recursively) for the key of rank k in the left subtree; if t is equal to k, we return the key at the root; and if t is smaller than k, we look (recursively) for the key of rank k - t - 1 in the right subtree. As usual, this de- scription serves both as the basis for the recursive select() method on the facing page and for a proof by induction that it works as expected.
I want to understand specifically what is the purpose of the k - t - 1 pass to the recursive select method when the size of the left node is less than the number of keys smaller than k.
public Key select(int k)
{
return select(root, k).key;
}
private Node select(Node x, int k)
{ // Return Node containing key of rank k.
if (x == null) return null;
int t = size(x.left);
if (t > k) return select(x.left, k);
else if (t < k) return select(x.right, k-t-1);
else return x;
}
As you can see the above implementation of the select method of a Binary Search Tree. When the conditional t < k the author passes k-t-1 to the recursive select method call but I can't still figure out why that is.
k − t − 1 is equal to k − (t + 1). When t < k and we recurse into the right subtree, the t elements in the left subtree and the 1 root count toward the rank of the elements in the right subtree, so we need to adjust k to match.