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

Question

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

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

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

Answer 1

假设你的意思是"二叉搜索树"而不是"二叉树"，你不需要任何修改来找到树中的最小元素y，使得y>= x。

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( 也是如此。