我在项目（Java's）上使用带有链接叶子的红黑二叉树TreeMap，以快速查找和迭代项目。问题是我可以轻松地在树上获得 35000 个左右的项目，并且有几次我必须删除“X 以上的所有项目”，这几乎可以是整个树（就像一次 30000 个项目，因为它们都更大比 X），并且每次都需要花费太多时间来删除它们并重新平衡树。
有什么算法可以帮助我（所以我可以自己实现树）？
问问题
78 次
1 回答
2
您正在寻找红/黑树上的拆分操作，该操作采用红/黑树和某个值 k 并将其拆分为两棵红/黑树，一棵所有键都大于或等于 k，一棵所有小于 k 的键。如果您扩充结构以存储一些额外信息，这可以在 O(log n) 时间内实现。在您的情况下，由于您使用的是 Java，您可以只拆分树并丢弃您不关心的树的根，以便垃圾收集器可以处理它。
本文从第 9 页开始详细介绍了如何实现这一点。它是根据结合了两棵树的catenate（或join）操作来实现的，但我认为说明非常清楚。
希望这可以帮助！
于 2013-10-20T22:59:25.477 回答