查找RBTREE在O（LOGN）的算法

Question

我需要找到一个数据结构，我可以用下面的动作做：

• 生成（S，K） - O（nlogn）
• 搜索（S，K） - O（logn）时间
• 插入（S，K） - O（logn）时间
• 删除（S，K） - O（logn）时间
• 减少-高达（S，K，d ） - O（logn） - 此方法应该将每个节点减去d（d> 0），即< = k

明显的第一选择是RedBlackTree。

但是，我不能找到有关O（Logn）中的减少-Upto的解决方案。 如果k大于树中的最大密钥，会发生什么情况 - 这种情况下，我需要更新整棵树。

有人可以建议吗？也许有些提示？

Answer 1

您可以在树的每个节点中存储一个额外的值，我们称它为delta。将节点的增量添加到存储在其所有后代中的键中以获取实际键。因此，要获取某个特定节点中密钥的实际值，可以将所有从根节点到该节点的增量相加，并将该和加到存储的密钥中。

要做Decrease-Upto，您只需更改根（root）的一个路径上O（log n）个节点的增量。

在此操作之后，您不必更改树的结构，因为不会更改密钥的排序。