Empresas
Empleos
  • Sobre nosotros
  • Soluciones
    • Publicación de vacantes
      Publica tu vacante y recibe candidatos calificados en 48h.
    • Evaluación de candidatos
      500+ pruebas técnicas y psicológicas, más anti-fraude.
    • Headhunting
      Búsqueda ejecutiva a la medida de principio a fin.
    • Nómina + EOR
      Dispersión de nómina y EOR en más de 15 países de LATAM.
  • Precios
  • Empleos

0

280
Vistas
Binary Search Tree select method implementation

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.

enter image description here

over 4 years ago · Santiago Trujillo
1 Respuestas
Responde la pregunta

0

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.

over 4 years ago · Santiago Trujillo Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Comercial
Legal
Términos y condiciones Política de privacidad
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomiéndame algunas ofertas
Necesito ayuda