二叉搜索树选择方法的实现

Question

我现在正在看罗伯特·塞奇威克的算法书。在这本书中，我试图理解select方法在二叉搜索树中的实现。作者用BST实现了一个符号表。作者描述select方法如下：

假设我们寻找秩为k的密钥（该密钥使得BST中的其他密钥精确地k个更小）。如果左子树中的键数t大于k，则我们在左子树中（递归地）寻找秩为k的键；如果t等于k，我们返回根处的键；如果t小于k，我们在右子树中递归地寻找秩为k-t-1的键。像往常一样，这个de-scription既是面向页面上递归select（）方法的基础，也是通过归纳证明它按预期工作的基础。

我想具体了解当左节点的大小小于小于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;
}

Answer 1

k-t-1等于k-(t+1)。当t