查找最多 h + 1 次比较的 BST 元素

Question

给定一棵二叉搜索树和一个元素 e，最多进行 h + 1 次比较来确定树是否包含 e，其中 h 是树的高度，==、!=、>、>= 、< 和 <= 是比较。有谁知道如何创建这个算法？

Answer 1

首先，编写一个函数，在树中找到大于或等于您的值的最小项。

在pseudo-code中：

function find_min_ge(x, node, min_ge) {
    if node is nil {
        return min_ge
    }
    if node.x >= x {
        return find_min_ge(x, node.left, node.x)
    } else {
        return find_min_ge(x, node.right, min_ge)
    }
}

此处，"min_ge" 参数是目前找到的 >= x 的最小值。

然后，将结果与x比较：

x_in_tree = find_min_ge(x, root, x + 1) == x

x+1 是一个虚拟值，如果树中没有 >= x 的元素，它将被返回。 x+1 可以是任何不等于 x 的表达式。

总的来说，find_min_ge 执行最多 h 次“>=”比较，然后在最后进行一次额外的“==”比较，总计达到要求的最大 h+1 次。