algorithm - 在 2 个 AVL 节点之间搜索最大值

Question

我有一段AVL tree时间每个节点包括：

• 钥匙
• 价值

AVL tree是按键排序的。

因此，如果我有 2 个键，现在我想找到这 2 个键之间的最大值。我已经尝试向每个节点添加其他信息，例如左子树中的最大值和右子树中的最大值，但是如果不“丢失”一些节点之间的节点，我就无法获得正确的算法。

复杂度时间： O(log n) 最坏情况。

Answer 1

您还需要对这个复合树进行哪些其他操作，以及您需要对它们进行哪些复杂性限制？

如果唯一的限制是在这个look-up-the-max-value-for-a-range-of-keys(j, k) 操作上，那么有一个愚蠢的解决方案是任意地预先计算所有这些 n^2 最大值时间; 您将固定 k 的所有值存储在树中节点 k 的数组中；那么您的操作将简化为查找。但是，如果您想支持插入或删除，复杂度将类似于 O(n^2)。

更现实的选择是存储每个子树的最大值。任何两个节点之间最多有 O(log(n)) 个子树，并且您在从根到您的两个键 j 和 k 的途中遇到所有子树，或者就在树中它们的下方，所以这将是 O(日志（n））。这样你仍然会有 O(log(n)) 插入，但我认为现在删除可能是 O(n)，因为恢复你删除条目的子树的最大值很复杂。