algorithm - 二进制搜索树中的下层实现

想想罗伯特·塞吉威克在他的《美国汽车协会》中的这段话：
如果给定的键小于bst根上的键，则键的底（bst中小于或等于键的最大键）必须位于左子树中。如果键大于根上的键，则键的底可以在右子树中，但前提是右子树中有小于或等于键的键；如果不是（或如果键等于根上的键），则根上的键是键的底。
我非常困惑当键大于根时会发生什么，尤其是当他说：“但只有当右子树中有一个键小于或等于键时”。我想他是说，如果键小于根，那么键肯定在左子树中。另一方面，如果密钥是grater，则密钥“可能”在右子树中，因此可能在右子树中也找不到密钥。基于他的floor（）方法：

public Key floor(Key key)
{
   Node x = floor(root, key);
   if (x == null) return null;
   return x.key;
}

private Node floor(Node x, Key key)
{
   if (x == null) return null;
   int cmp = key.compareTo(x.key);
   if (cmp == 0) return x;
   if (cmp < 0)  return floor(x.left, key);
   Node t = floor(x.right, key);
   if (t != null) return t;
   else           return x;
}

他确实检查了右子树，但没有检查左子树但我完全不能给出一个例子，其中键大于根，但小于右子树中的键我真的认为这是不可能的我少了点东西。有人能解释一下我遗漏了什么吗？

最佳答案

如果你有一棵树（请原谅我的ASCII艺术技巧）

  3
 / \
1   5

你在找第四层，然后
搜索键大于根
右子树中没有小于搜索键的键，因此
结果是根键（3）。

关于algorithm - 二进制搜索树中的下层实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27362123/