立即從平衡二叉樹中刪除多個項目

我在項目中使用帶有鏈接葉子的紅黑二叉樹（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

立即從平衡二叉樹中刪除多個項目

回答

相關問題