立即从平衡二叉树中删除多个项目

我在项目中使用带有链接叶子的红黑二叉树（Java的TreeMap），以快速查找并遍历项目。问题是我可以很容易地在树上获得35000个物品，并且我需要多次删除“X以上的所有物品”，这几乎可以是整个树（比如30000个物品，因为它们都更大比X）要花费太多时间去除它们并且每次重新平衡树。立即从平衡二叉树中删除多个项目

是否有任何算法可以帮助我在这里（所以我可以让自己的树实现）？

来源

2013-07-14 paulotorrens

你还对数据做了什么？总是有一个权衡，但是你可能能够为你的主要使用模式优化数据结构/算法。 – AndrewC

该映射用于语法高亮组件，它使用从Integer到Token的映射来跟踪每个令牌及其颜色。每个绘图周期我需要获取树的一部分（“位置X和Y之间的每个标记”），这就是为什么这些项也被链接，以便快速迭代。每当用户在组件上键入某些内容时，它后面的每个标记都将被删除...因此，如果他在文件的开头进行编辑，则必须立即删除大量节点。如果他在文件末尾进行编辑，只需要从树中删除一些。我试图优化这种行为。 =/ – paulotorrens

您正在查找的是分割在一棵红黑树上进行操作，它将红/黑树和某个值k分割成两棵红/黑树，其中一棵的键大于或等于到k，并且所有的密钥都小于k。如果你增加结构来存储一些额外的信息，这可以在O（log n）时间内实现。就你而言，因为你使用的是Java，所以你可以拆分树并丢弃你不关心的树的根，这样垃圾回收器就可以处理它。关于如何实现这一

详细情况this paper给出，开始9.在一个链状方面实现页面上（或加入）操作结合了两棵树，但我认为本届博览会是相当清楚的。

希望这会有所帮助！

来源

2013-10-20 22:59:25 templatetypedef

这有助于！谢谢。 :) – paulotorrens

立即从平衡二叉树中删除多个项目

回答

相关问题