Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

281
Visualizações
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 Respostas
Responde à pergunta

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 Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda