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

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