查找最大整数小于最大键，但在AVL树中却不
给定avl树T，我需要找到比树中最大钥匙小的最大整数，但不在树上。
我已经写了辅助功能来获得最大的节点，但我的想法被卡住了。
我尝试查看最大节点的排名及其继任者的等级，但没有任何帮助。
任何想法都会有所帮助！
Given AVL tree T, I need to find the maximal integer which is smaller than maximal key in tree, but is not in tree.
I've written auxiliary functions to get the biggest node, yet my thoughts are stuck.
I tried looking at the rank of the maximal node and the rank of it's successor yet that doesn't do any help.
Any ideas would be really helpful!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
总体想法是：用
max（crawl＆lt; - max）初始化变量爬网）。搜索第二个最大值。如果它小于crawl-1，您的答案是crawl-1。否则，有两种可能性：crawl-1：分配crawl＆lt; - crawl-1。爬网。在任何情况下，搜索第三个最大值。如果它小于
crawl-1，您的答案是crawl-1。否则，有两种可能性：crawl-1：分配crawl＆lt; - crawl-1。爬网。...
您注意到递归结构吗？
您要么在某个步骤中找到答案，要么您将获得最小的元素而没有答案。在这种情况下，答案将为
crawl-1（在此步骤中将存储min-1）。要找到连续的最大值，您可以迭代删除最大值。例如，要找到第二个最大值，请删除最大值并在新的AVL树中找到最大值。
时间复杂性将为
o（n * log n）。每个拆卸操作都采用o（log n），您最多可以做n删除。The general idea is: initialize a variable
crawlwith themax(crawl <- max). Search the second maximum. If it's smaller thancrawl-1, your answer iscrawl-1. Else, there are two possibilities:crawl-1: assigncrawl <- crawl-1.crawl.In any of the cases, search the third maximum. If it's smaller than
crawl-1, your answer iscrawl-1. Else, there are two possibilities:crawl-1: assigncrawl <- crawl-1.crawl....
Did you notice the recursion structure ?
Either you will find the answer at some step or you will achieve the smallest element without answer. In this case the answer will be
crawl-1(which will storemin-1at this step).To find the successive maximums, you can iteratively remove the maximum. For example, to find the second maximum, remove the maximum and find the maximum in the new AVL tree.
The time complexity would be
O(n * log n). Each removal operation takesO(log n)and you do at mostnremovals.如果我们知道等级数组和所有值都是不同的（
n值），我们可以进行以下二进制搜索：如果
max -max -min + 1 = n，答案是min-1。否则，将[Min，Max]的中间元素占据。
max -med + 1 = n/2。在这种情况下，请考虑med之前的元素是med_before。如果med_before＆lt; Med -1，答案是MED -1。否则，转到[min，med_before]。max -med + 1＆gt; N/2。在这种情况下，请考虑Med之后的元素是Med_after。转到[Med_after，Max]。If we know the rank array and all values are distinct (
nvalues), we can do a binary search like the following:If
max - min + 1 = n, the answer ismin-1.Else, take the median element of [min, max] in the tree.
max - med + 1 = n/2. In this case, consider that the element right beforemedismed_before. Ifmed_before < med - 1, the answer ismed - 1. Else, go to[min, med_before].max - med + 1 > n/2. In this case, consider that the element right aftermedismed_after. Go to[med_after, max].