我正在看罗伯特·塞吉威克的算法书。在书中我试图理解 select 方法。作者使用bst实现了一个符号表。作者描述了 select 方法如下：
假设我们寻找秩为k的密钥（使得bst中的其他k个密钥更小的密钥）。如果左子树中的键数t大于k，则递归地寻找左子树中秩为k的键；如果t等于k，则返回根处的键；如果t小于k，我们（递归地）查找右子树中秩为k-t-1的键。像往常一样，这种描述既可以作为首页上递归select（）方法的基础，也可以作为归纳法证明它按预期工作的依据。
我想具体了解 k - t - 1 当左节点的大小小于 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;
}

如您所见，上面实现了 select 二叉搜索树的方法。当条件 t < k 作者通过 k-t-1 到递归 select 方法调用，但我仍然不明白为什么会这样。