在 RBTREE 中查找算法，时间复杂度为 O(logn)
我需要找到一个可以通过以下操作执行的数据结构：
- 构建（S，k） - O（nlogn）
- 搜索（S，k） - O（logn）
- 插入（S，k） - O（logn）
- 删除(S,k) - O(logn)
- Decrease-Upto(s,k,d) - O(logn) - 此方法应该减去 d(d>0) 每个 <=k 的节点
明显的第一个选择是 RedBlackTree 。
但是，我无法找到关于 O(Logn) 中的 Decrease-Upto 的解决方案。 如果 k 大于树中的最大键会发生什么 - 在这种情况下我必须更新整个树。
有人可以提出其他建议吗？也许有一些技巧？
I need to find a data structure which I can do with the following actions:
- Build(S,k) - O(nlogn)
- Search(S,k) - O(logn)
- Insert(S,k) - O(logn)
- Delete(S,k) - O(logn)
- Decrease-Upto(s,k,d) - O(logn) - this method should subtract d(d>0) every node which is <=k
The obvious first choise was RedBlackTree.
However, I can't come to a solution regarding Decrease-Upto in O(Logn).
what happens if k is greater then the max key in the tree - that case i gotta update the whole tree.
Can someone suggest otherwise ? maybe some tips ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以在树的每个节点中存储一个额外的值，我们称之为增量。您可以将节点的增量添加到存储在其所有后代中的键中，以获取实际的键。因此，要获取特定节点中键的实际值，您可以对从根到该节点的所有增量求和，并将该总和添加到存储的键中。
要实现
Decrease-Upto，您只需更改从根开始的一条路径上 O(log n) 个节点的增量。执行此操作后，您不必更改树的结构，因为它不会更改键的顺序。
You can store an extra value in each node of the tree, let's call it delta. You add delta of a node to keys stored in all its descendant to get the actual keys. So, to get the actual value of a key in a particular node, you sum all deltas from the root to that node and add this sum to the stored key.
To do
Decrease-Upto, you just change deltas of O(log n) nodes on one path from root.You don't have to change the structure of the tree after this operation, because is doesn't change ordering of the keys.