我有一个 AVL树，而每一个节点包括：

I have an AVL tree while each node consists of:

在 AVL树是由键有序

所以，如果我有2把钥匙，现在我想找到的最大的值的2键之间。 我试图增加额外的信息，像左子树的最大值和同为右子树的每个节点，但我不能得到正确的算法之间没有丢失一些节点。

So if I got 2 keys and now I want to find the maximum value between those 2 keys. I've tried adding additional information to each node like the max value in the left subtree and same for the right subtree but I can't get the right algorithm without "losing" some nodes between.

复杂性时间： O（log n）的最坏的情况下的

推荐答案

你需要什么样的其它操作你需要对这个合成树，什么复杂的边界又在哪里？

What other operations do you need on this composite tree, and what complexity bounds do you require for them?

如果唯一的限制是在此查询-的-MAX值换一个范围 - 键 - （J，K）的操作，则有$ P $的pcomputing所有这n个愚蠢的解决方案^ 2 Maxima在任意多的时间;你存储在树节点k阵列固定请在所有价值;那么你的操作被减少到一个查找。不过，如果你想支持插入或删除，复杂性会像为O（n ^ 2）。

If the only restriction is on this look-up-the-max-value-for-a-range-of-keys(j, k) operation, then there is the silly solution of precomputing all these n^2 maxima in arbitrarily much time; you'd store all values for fixed k in an array in node k in the tree; then your operation is reduced to a lookup. However, if you'd want to support insert or delete, the complexity would be something like O(n^2).

一个比较现实的选择是将存储每个子树的最大值。有在任意两个节点之间的大多数为O（log（n））的子树，并且遇到所有的人都从根部一直到你的两个键J和K或者只是在它们下面的树，所以这将是O（日志（正））。这样，你还是得为O（log（n））的插入，但我认为删除将可能是为O（n），因为现在它的复杂恢复子树外面，你已经删除的条目的最大值。

A more realistic option would be to store the max of each subtree. There are at most O(log(n)) subtrees between any two nodes, and you encounter all of them on the way from the root to your two keys j and k or just underneath them in the tree, so that would be O(log(n)). This way you'd still have O(log(n)) insertion, but I think deletion would potentially be O(n) now since it's complicated to restore the maximum of a subtree out of which you've removed an entry.