我有上述问题，我正在尝试解决。Avl 树的每个节点也有子树的大小，我知道最大值。我需要找到i之后的下一个第一个数字，它不在树中。我需要在O(logn)时间内完成。
我到了
if i bigger/equal the maximum then return i+1，
我尝试做其他情况以找到树中i后的最小值，我知道如果我找到的数字大于i+1return i+1，我可以在O(logn)中做到这一点。
现在我明白了，如果i+1在树中，我需要继续搜索，但我的时间复杂度比我需要的要大。 将非常感谢任何指导。我不是在寻找代码，只是在寻找如何在指定时间内解决它的想法或指导
我认为您的问题可能更多地存在于时间复杂度分析中，而不是实际算法中。
我们知道，如果操作得当，在高度log[2](n)的良好形成的AVL树中进行搜索的时间将始终log[2](n)。 在这种情况下，搜索缺失的项目与搜索现有项目没有什么不同。
假设您有一个 AVL 树A它包括i和i+1。然后我们知道i+1必须是i的父节点，i是左子节点，或者i+1是i的右子节点。因此，我们可以得出结论：
if i ^ i+1 in A => i+1(l)=i v i(r)=i+1
因此，如果您发现i并且其父节点不i+1则必须i+1其右侧子节点。您可以在找到i+1后将其扩展到i=i+1，并继续检查此情况。这里很酷的事情是，如果您跟踪已遍历的节点，则只需要在i之后查看每个值i+n一个位置。
如果你通过[i+7, i+4, i]你会立即知道，如果A包含i它不能包含i+1。这是由于i+1 < i+4但i < i+1 < i+4.
如果你通过[i-6, i-2, i]你也会立即知道，如果A包含i+1它不能包含i+1。这是由于i-2 < i+1但i-2 < i < i+1.
如果你要经历[i+7, i+3, i+1, i]你会发现i，i+1并且由于i+3不是i+2你知道i+2必须是i+1的右子节点，因为它一定不是i+3的子节点，因为它更小，但i+1已经占据了左子节点的位置。所以你检查i+1的右子是否i+2，你从i+3开始继续检查i+4，基本上使用算法：
define stack //use your favourite stack implementaion
let n = root node
let i = yourval
while n.val != i
stack.push(n)
if i > n.val
n = n.right
else //equivalent to "else if i < n.val" since loop condition ensures they are not equal
n = n.left
while !stack.empty
if stack.peek.right.val != queue.peek.val + 1
//Implies parent holds value
temp = stack.pop.val + 1
if(temp != stack.peek.val) //If the parent does not hold the next value return it
return temp;
else //Right child holds value
stack.push(queue.peek.right)
i = stack.peek.val
return i+1 //if the stack is empty eventually return the next value
由于 AVL 树的形成方式，您的堆栈最多2*logn[2](n)元素很大(如果i是 LHS 上的叶子，最后一个值是 RHS 上的叶子)。因此，总的来说，您的搜索将需要log[2](n)才能初步搜索i和另一个2*log[2](n)组合，使3*log[2](n)，这在大奥密克戎中仍然O(log[2](n))。
作为提示，请考虑一下，如果元素位于数组而不是 AVL 树中，您将如何解决此问题。您将如何使用修改后的二进制搜索在数组中的时间 O(log n) 中解决此问题？
一旦你弄清楚了如何做到这一点，看看你是否可以调整你的解决方案，以便在二叉搜索树而不是数组中工作。直觉将非常相似，除了不是在每个点查看整体元素范围的中间，而是查看当前子树的根，虽然接近中间，但并不总是完全在中间。