二叉搜索树中的楼层实现-Java 学习之路

请考虑Robert Sedgewick在他的_2705806中的这句话：

如果给定的密钥小于BST根的密钥，则密钥的底限（BST中的最大密钥小于或等于密钥）必须在左子树中 . 如果key大于root的密钥，那么key的floor可以在右子树中，但只有在右子树中有一个小于或等于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;
}

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

2 回答

0
如果你有一棵树（请原谅我的ASCII艺术技巧）
```
3
 / \
1   5
```
而你正在寻找楼（4）
- 搜索键大于root
- 右侧子树中没有小于搜索键的键，所以
- 结果是根密钥（3） .
回复于 2024-05-17T11:14:15+08:00

简单的解决方案：

int FloorInBST(Node* root,int data)
            {
              if(root == NULL)
              {
                  return -1;//when MinNode of tree is greater than the input value
              }
              if(root->data == data) return data;

              if(root->data > data)
              {
                  return FloorInBST(root->left, data);//MUST be in left subtree 
              }
              else if (root->data < data)
              {
                  //MAY be in right subtree OR root itself
                  int floor = FloorInBST(root->right, data);
                  return (root->data >= floor ? root->data:floor);
              }
            }

回复于 2024-05-17T11:14:15+08:00

二叉搜索树中的楼层实现

2 回答

相关问题