二叉搜索树的select方法实现

Question

我正在学习Robert Sedgewick的算法书。在书中，我试图理解二叉搜索树中select方法的实现。作者使用BST来实现符号表。作者将select方法描述如下： 假设我们寻找排名为k的键（恰好有k个比BST中其他键更小）。如果左子树中的键数t大于k，则在左子树中递归查找排名为k的键；如果t等于k，则返回根节点上的键；如果t小于k，则在右子树中递归查找排名为k-t-1的键。通常，这个描述既是面对页面上递归选择()方法的基础，也是通过归纳证明它按预期工作的依据。 我想特别了解当左节点的大小小于比k小的键数时，向递归选择方法传递k-t-1的目的是什么。

 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;
}

正如您所看到的，这是二叉搜索树的select方法的实现。 当条件t < k成立时，作者将k-t-1传递给递归的select方法调用，但我仍然无法弄清楚原因。

- Steven Aguilar

---

我还建议查看PriorityQueue的源代码，以获取一个特定的实现示例。它非常不错。 - Blake

Answer 1

k − t − 1等于k − (t + 1)。当t < k且我们递归到右子树时，左子树中的t个元素和1个根节点计入右子树元素的排名，因此我们需要调整k以匹配。

- David Eisenstat

---

那么，如果根的等级是k+1，为什么当t == k时会返回根？ - Yash Shah

@YashShah 基于0的索引。 - David Eisenstat