algorithm - 二叉搜索树中的底层实现

Question

考虑 Robert Sedgewick 在他的 booksite 中的声明:

If a given key key is less than the key at the root of a BST, then the floor of key (the largest key in the BST less than or equal to key) must be in the left subtree. If key is greater than the key at the root, then the floor of key could be in the right subtree, but only if there is a key smaller than or equal to key in the right subtree; if not (or if key is equal to the key at the root), then the key at the root is the floor of key.

我非常困惑当键大于根时会发生什么，特别是当他说:“但前提是右子树中有一个键小于或等于键”。我认为他的意思是，如果 key 小于根，则 key 肯定在左子树中。另一方面，如果 key 更细，则 key “可能在”右子树中，因此也有可能在右子树中找不到 key 。并基于他的 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;
}

他确实检查了右子树，但没有检查左子树。但是我完全想不出一个例子，其中键大于根但小于右子树中的键。我真的认为这是不可能的。我错过了什么。谁能解释我错过了什么？

Answer 1

如果你有一棵树(请原谅我的 ASCII 艺术技能)

  3
 / \
1   5

而你正在寻找 floor(4)，那么

1. 搜索关键字大于根
2. 右子树中没有比搜索关键字小的关键字，所以
3. 结果是根 key (3)。