二叉树查找最接近且大于键的数字

Question

假设我有一个平衡二叉树。我希望在树中搜索密钥 k。但是，如果二叉树中不存在 k，它应该给我最接近 k 的下一个最大数字。

例如，假设我将这些数字 [1,5,6,8,10] 作为树中的键。如果我搜索“7”，它应该返回 8，如果我搜索 2，它应该返回 5，等等。

为了能够执行这样的搜索，二叉树必须进行哪些修改？我也想要一个 O(log n) 的解决方案。

Answer 1

假设您的意思是“二叉搜索树”而不是“二叉树”，则不需要任何修改即可找到树中满足 y >= x 的最小元素 y。

search(n, x, best_so_far) ::=
    if n == nil { return best_so_far }
    if n.value == x { return x }
    if n.value > x { return search(n.left, x, min(best_so_far, n.value) }
    if n.value < x { return search(n.right, x, best_so_far) }

您可以将此函数称为search(root, x, +infinity).

这个想法是，如果您正在探索节点 n 处的左分支，则无需考虑 n 右侧的任何内容：n.value 大于 x，并且右侧的所有内容都大于 n.value 。类似地，如果您正在探索节点 n 的右分支，则可以丢弃 n 左侧的所有内容：n.value 小于 x，并且 n 左侧的所有内容都小于 n.value。

代码的运行时间受树的高度限制，如果树是平衡的，则 O(log n) 也是如此。