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

Question

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

Answer 1

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

在伪代码中:

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 次。