Actualmente estoy revisando el libro Algorithms de Robert Sedgewick . En el libro, intento comprender la implementación del método de select en un árbol de búsqueda binaria. El autor usa un BST para implementar una tabla de símbolos. El autor describe el método de select de la siguiente manera:

Supongamos que buscamos la clave de rango k (la clave tal que precisamente k otras claves en el BST son más pequeñas). Si el número de claves t en el subárbol izquierdo es mayor que k, buscamos (recursivamente) la clave de rango k en el subárbol izquierdo; si t es igual a k, devolvemos la clave a la raíz; y si t es menor que k, buscamos (recursivamente) la clave de rango k - t - 1 en el subárbol derecho. Como de costumbre, esta descripción sirve como base para el método recursivo select() en la página opuesta y para una prueba por inducción de que funciona como se esperaba.

Quiero entender específicamente cuál es el propósito del paso k - t - 1 al método de selección recursivo cuando el tamaño del nodo izquierdo es menor que el número de claves más pequeñas que 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, kt-1); else return x; }

Como puede ver, la implementación anterior del método de select de un árbol de búsqueda binario. Cuando el condicional t < k , el autor pasa kt-1 a la llamada al método de select recursiva, pero todavía no puedo entender por qué.