小编典典

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

algorithm

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

AVL tree由有序

所以,如果我得到了2把钥匙,现在我想找到的最大 价值
的2个键之间。我尝试向每个节点添加其他信息,例如左侧子树中的最大值,以及右侧子树中的最大值,但是如果不“丢失”它们之间的某些节点,就无法获得正确的算法。

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


阅读 279

收藏
2020-07-28

共1个答案

小编典典

您需要在此组合树上执行哪些其他操作,以及它们需要哪些复杂性界限?

如果唯一的限制是查找键范围(j,k)的最大值,则存在一个愚蠢的解决方案,可以任意多地预先计算所有这些n ^ 2最大值时间;
您会将固定k的所有值存储在树中节点k中的数组中;那么您的操作将简化为查找。但是,如果您想支持插入或删除,那么复杂度将类似于O(n ^ 2)。

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

2020-07-28