我正在学习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
方法调用,但我仍然无法弄清楚原因。