在二叉搜索树落地实施 [英] Floor implementation in binary search tree

问题描述

此声明由罗伯特·塞奇威克在他的 booksite ：

如果一个给定的键键小于在BST的根，密钥然后地板（在BST小于或等于键最大键）的键必须在左子树。如果关键字大于在根密钥，那么关键的底板可以是在右子树，但只有当有超过一个键小于或等于在右子树密钥;如果不是（或者如果键是等于在根密钥），然后在根，关键是关键的楼层。

我非常困惑的时候，关键是大于根会发生什么，尤其是当他说：不过，有总比一个关键小于或等于右子树的关键。我想他的意思是，如果该键小于根，关键是肯定的左子树。在另一方面，如果关键是磨碎机，关键可能是在右子树，因此它可能密钥将不能在右子树中为好。而根据他的地板（）方法：

 公钥楼（主要键）
{
   节点x =地板（根密钥）;
   如果（X == NULL）返回NULL;
   返回x.key;
}

私人节点楼（节点X，键键）
{
   如果（X == NULL）返回NULL;
   INT CMP = key.compareTo（x.key）;
   如果（CMP == 0）返回X;
   如果（CMP℃下）返回地面（x.left，键）;
   节点T =地板（x.right，键）;
   如果（T！= NULL）返回吨;
   否则返回X;
}
 

他确实做了检查右子树，而不是左子树。但是，我完全不能拿出一个例子，其中最关键的是大于根，但比右子树的按键较小。我真的认为这是不可能的。我失去了一些东西。任何人都可以解释我缺少的是什么？

解决方案

如果你有一个像树（原谅我的ASCII艺术技能）

  3
 / \
1 5
 

和你正在寻找地板（4），然后

1. 搜索关键字大于根
2. 有一个在右子树比搜索关键字时没有钥匙，所以
3. 的结果是根键（3）。

Consider this statement by Robert Sedgewick in his 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.

I'm extremely confused what happens when the key is greater than the root, particularly when he says: "but only if there is a key smaller than or equal to key in the right subtree". I think he means that, if the key is less than the root, the key is certainly in the left subtree. On the other hand if the key is grater, the key "could be" in the right subtree, so it's possible the key will not be found on the right subtree as well. And based on his floor() method:

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;
}

He indeed did check the right subtree, but not the left subtree. But I completely can't come up with an example where the key is greater than the root and yet is smaller than the keys in the right subtree. I really think it's impossible. I'm missing something. Can anyone explain what I'm missing?

解决方案

If you have a tree like (excuse my ASCII art skills)

  3
 / \
1   5

And you are looking for floor(4), then

1. the search key is greater than root
2. there is no key in the right sub-tree smaller than the search key, so
3. the result is the root key (3).

这篇关于在二叉搜索树落地实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！