找到一个算法在RBTREE在O(的)

Question

我需要找到一个数据结构，我可以做以下行动：

• 建立(S、k)-O(nlogn)
• 搜索(S、k)-O(的)
• 插入(S、k)-O(的)
• 删除(S、k)-O(的)
• 减少高达(s、k,d)-O(的)--该方法应该减d(d>0)每个节点 <=k

显而易见的第一选择是RedBlackTree.

然而，我不能走到一个解决方案对减少高达在O(的).会发生什么，如果k大后的最大关键在树那种情况下，我要更新整个树。

可以有人建议，否则？也许一些技巧？

Answer 1

你可以存储额外的价值在每个节点的树木，让我们把它叫做delta。添加三角洲的一个节点钥储存在其所有的后代获得的实际键。因此，要获得的实际价值的一个关键在一个特定的节点，你总结的所有三角洲从根到这一点，并添加这笔款项，所存储的关键。

做 Decrease-Upto, 你只要改变三角洲的O(日志n)节点上的一个路径是从根源。

你不必改变结构的树后，这种操作，因为是不会改变排序的关键。