查找未出现在给定 AVL 树中的最小元素
Finding minimal element not presenting in a given AVL tree
给定一个 AVL 树，它存储了一个包含 n 个不同 个自然数的集合 G。在每个节点中存储以该节点为根的子树中的节点数。
我们如何在 O(log n) 的时间复杂度中找到不在 G 中且大于给定 p 的最小 m？
示例：
如果G={21,22,23,24,26,27,29,30}则：p=20 => m=25p=22 => m=25p=25 => m=28p=29 => m=31
想象一下，您是在数组而不是 AVL 树上解决这个问题。你会怎么做呢？首先，首先对数组进行二分查找，找到大于 p 的最小数 s。如果该数字大于 p+1，则 return p+1。否则，我们处于一些 运行 元素的中间，需要找到超过 运行 的最小数字。为此，您可以考虑解决以下问题：找到最小元素 x，使 x - s 大于 x 的索引减去 s 的索引。这可以通过对数组的剩余一半进行二进制搜索来完成：如果当前元素与 s 之间的差异等于当前元素与 s 之间的距离，则向右走，否则向左走。找到这个元素 x 后，转到它之前的元素，加一个，这就是你的答案。
要在 AVL 树上解决这个问题，您基本上需要调整上述算法以使用树搜索而不是二分搜索。拥有子树大小信息的事实意味着您可以使用标准顺序统计技术确定树中任何元素的索引。我想最终的算法会有点乱，但它会在时间 O(log n).
忠实地模拟上面的算法
给定一个 AVL 树，它存储了一个包含 n 个不同 个自然数的集合 G。在每个节点中存储以该节点为根的子树中的节点数。
我们如何在 O(log n) 的时间复杂度中找到不在 G 中且大于给定 p 的最小 m？
示例：
如果G={21,22,23,24,26,27,29,30}则：p=20 => m=25p=22 => m=25p=25 => m=28p=29 => m=31
想象一下，您是在数组而不是 AVL 树上解决这个问题。你会怎么做呢？首先，首先对数组进行二分查找，找到大于 p 的最小数 s。如果该数字大于 p+1，则 return p+1。否则，我们处于一些 运行 元素的中间，需要找到超过 运行 的最小数字。为此，您可以考虑解决以下问题：找到最小元素 x，使 x - s 大于 x 的索引减去 s 的索引。这可以通过对数组的剩余一半进行二进制搜索来完成：如果当前元素与 s 之间的差异等于当前元素与 s 之间的距离，则向右走，否则向左走。找到这个元素 x 后，转到它之前的元素，加一个，这就是你的答案。
要在 AVL 树上解决这个问题，您基本上需要调整上述算法以使用树搜索而不是二分搜索。拥有子树大小信息的事实意味着您可以使用标准顺序统计技术确定树中任何元素的索引。我想最终的算法会有点乱，但它会在时间 O(log n).
忠实地模拟上面的算法