algorithm - 秩树特殊情况的算法

Question

我正在尝试基于具有特殊要求的 AVL 树创建一些等级树，假设我有带有节点的 AVL 树，每个节点有 2 个字段：

id, priority

我的 AVL 树按 id 排序，我还有一个功能：

foo(currentId, delta)

这降低了小于或等于此函数的所有 id 的优先级currentId必须delta 处理复杂度 O(log n)，所以我的问题是我需要存储哪些附加信息才能使用highest priorityat弹出节点任何阶段with complexity O(1)（也使用 foo 之后！）。

P.S.我试图在右子树中存储有关最大优先级的信息，在左子树中存储有关最大优先级的信息，但是在foo. 它需要的不仅仅是 O(log n)。在此先感谢您提供有关树木的任何好主意或好书。

score 1 · Accepted Answer

与其存储出现在每个子树中的最大优先级，不如为每个具有父 p 的节点 c，将c 的子树中的最大优先级与 p 的子树中的最大优先级之间的差存储在 c 中。这样，您可以在 O(log n) 时间内更新一系列优先级，并且仍然在 O(log n) 时间内找到最大优先级的元素。

1 回答 1