特殊情况下的排名树算法

Question

特殊情况下的排名树算法

3

我将尝试创建一些基于AVL树的排名树，具有特殊要求。假设我有AVL树和节点，每个节点有2个字段：

id, priority

我的AVL树按照id排序，同时我有一个函数：

foo(currentId, delta)

降低所有 ID 的优先级，即小于或等于 currentId 的所有 ID 优先级下降 delta。该函数需要以 O(log n) 的复杂度工作。因此，我的问题是：我需要存储哪些额外信息才能在任何阶段使用 foo 后，在 O(1) 的复杂度下弹出具有最高优先级的节点（after using foo also！）。

P.S. 我尝试过在右子树和左子树中存储有关最大优先级的信息，但是在使用 foo 后需要进行很多更改。这将需要超过仅 O(log n) 的时间。提前感谢任何关于树的好主意或好书。

- rookie

使用AVL树的原因是什么？似乎各种优先队列实现在这里可能更好。 - templatetypedef

@templatetypedef: 请问您能给我提供一些有用的信息链接吗？我不知道您在说什么... - rookie

你在每次弹出后都调用了 foo() 吗？相对于 id，你使用了哪些 delta 值？一个详细的示例将有助于我们理解你在这里尝试实现什么。 - moinudin

@marcog：不是随机的，关于ID始终大于0，没有其他信息... - rookie

如果一切都是完全随机的，而你没有其他依据可依，那么最好的平均情况就是通过暴力搜索最高优先级。如果你有更多信息，请在一个实例中告诉我们，我们可以为你提供进一步的帮助。 - moinudin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jonderry · Accepted Answer

与其存储每个子树中出现的最大优先级，对于每个父节点p的子节点c，在c中存储c子树中的最大优先级和p子树中的最大优先级之间的差异。这样，您就可以在O(log n)时间内更新一系列优先级，并仍然可以在O(logn)时间内找到最高优先级的元素。