2

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

  • 钥匙
  • 价值

AVL tree按键排序的。

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

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

4

1 回答 1

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),因为恢复你删除条目的子树的最大值很复杂。

于 2011-05-17T19:35:22.280 回答