BST 中的 floor 函数，这是实现还是我误解了它的用法？

Question

我正在自学一些数据结构，我想知道这是否是 BST 中 floor 函数的正确实现？我会切入正题...

def floor(self, key):
    if self.root == None:
        return False

    return self._floor(self.root, key)

def _floor(self, node, key):
    if key == node.key:
        return node

    if key < node.key:
        if node.left == None:
            return node

        return self._floor(node.left, key)

    if node.right == None:
        return node

    return self._floor(node.right, key)

以上是我实现该功能的方法，似乎工作正常。但是我写了一些单元测试，其中一个失败了。

def test_floor_NoLeftSubTree_HighestElementLowerThanValueReturned(self):
    # Arrange
    self.tree.insert(100)
    self.tree.insert(102)
    self.tree.insert(101)
    self.tree.insert(110)
    self.tree.insert(115)
    self.tree.insert(120)
    self.tree.insert(130)

    # Act, Assert
    self.assertEqual(self.tree.floor(109).key, 102)

我只是想澄清一下，我的理解是正确的。上面的测试失败了，因为它是 returning 110，而不是 102。我认为它应该 return 102。任何正确方向的推动都会有所帮助，谢谢...

我正在从 this 文档中学习。

编辑： 这就是我认为树应该看起来的样子。

                    100
                        102
                    101     110
                                115
                                    120
                                        130

Answer 1

当您的代码到达节点 102 时，它决定转到正确的子节点，即 110。但是 110 节点没有左子节点，例程 return 是当前节点 (110)。在这种情况下你应该 return "None" （因为这里没有 floor(109) 候选人），然后在上一级 return当前节点（即102）：return self._floor(node.right, key) 如果不是None，return node 否则

BST 中的 floor 函数，这是实现还是我误解了它的用法？

Floor function in BST, Is this the Implementation or am i missunderstanding its use?

python

binary-search-tree