排序树特殊情况的算法
我正在尝试创建一些基于具有特殊要求的AVL树的排名树，假设我有带有节点的AVL树，每个节点有2个字段：
id, priority
我的AVL树按id排序，我还有一个函数：
foo(currentId, delta)
它降低了小于或等于 currentId by delta 的所有 id 的优先级 该函数的复杂度为 O(log n)， 所以我的问题是我需要存储哪些附加信息才能在任何阶段以复杂度 O(1) 弹出具有最高优先级的节点（使用 foo 之后）还！）。
PS我尝试在右子树中存储有关最大优先级的信息，在左子树中存储最大优先级的信息，但在foo之后需要进行很多更改。这将不仅仅需要 O(log n)。预先感谢任何关于树的好主意或好书。
I'm trying to create some rank tree based on AVL tree with special requirements, lets assume that I have AVL tree with nodes, each node has 2 fields:
id, priority
my AVL tree is sorted by id, also I have a function:
foo(currentId, delta)
which lowers the priority of the all ids which is less or equal to currentId by delta
this function has to work with complexity O(log n),
so my question is which additional information do I need to store to be able to pop the node with the highest priority at any stage with complexity O(1) (after using foo also!).
P.S. I tried to store info about max priority in the right subtree, max priority in the left subtree, but it needs a lot of changes after foo. It will take more than just O(log n). Thanks in advance for any good ideas or good books about Trees.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于具有父级 p 的每个节点 c，不是存储每个子树中出现的最大优先级，而是在 c 中存储 c 的子树中的最大优先级与最大优先级之间的差在 p 的子树中。这样，您可以在 O(log n) 时间内更新一系列优先级，并且仍然在 O(log n) 时间内找到最大优先级的元素。
Rather than store the maximum priority that appears in each subtree, for each node c with parent p, store in c the difference between the maximum priority in c's subtree and the maximum priority in p's subtree. This way, you can update a range of priorities in O(log n) time, and still find the element of maximum priority in O(log n) time.