從二進制索引樹中刪除元素

我有二進制索引樹（BIT），它存儲了不同的排序值。例如。查詢（1）返回1，查詢（2）返回2等等。從二進制索引樹中刪除元素

我想在此BIT中找到第n個最大元素。但是這個元素不應該在下一次重複。例如。最初第四個最大值是4.下一次第四個最大值將是5，此後第四個最大值將是6.

我想過的一種方法是獲得第n個最大值，然後從BIT中刪除該元素或將所有元素左移該元素減1，以便下次不會重複。但我無法知道如何刪除BIT的元素或切換元素。

有人可以告訴如何做到這一點，如果有可能？

來源

2013-08-01 Gaurav Deshmukh

你有沒有試圖做出這個刪除功能呢？您是否受限於使用BIT或可以更改數據結構？ – lbrendanl

我想過刪除功能，但絕對不知道。我沒有限制使用BIT，但我想知道如何使用BIT來做到這一點（如果可以的話）。 –

另外我想在log（n）時間做它 –

基本比特數據結構看起來像這樣：

value 1|2|3|4|5|6 
f  1|0|2|1|1|3 
c  1|1|3|4|5|8 
tree 1|1|2|4|1|4

其中：

F [I] - 具有索引的值頻率I，I = 1 .. MaxVal最大值
Ç [i] - 指數i的累積頻率（f [1] + f [2] + ... + f [i]）
樹[i] - 存儲在具有索引i的BIT中的頻率之和

（以上是直接從article）。

看看上面的數據結構，我們可以看到在O（log n）時間內不可能做刪除操作。想象一下，我們想從樹中刪除第一個元素。爲了做到這一點，我們需要更新f [0]，c [0]和tree [0]，以反映該元素不再存在於樹中。不幸的是，我們還需要遍歷c結構的其餘部分，因爲它代表了一個累積和。在將c [0]設置爲0之後，c [1]不再準確，並且必須更新，並且c [2]不再準確...直到c [n-1]。

在最壞的情況下，這將是O（n）操作，最壞的情況是刪除樹中的第一個元素。

我認爲這將是一個更明智的選擇，使用不同的數據結構。 BIT和其他二叉樹非常適合高效地查找和添加元素，但不擅長刪除元素。我會建議使用優先隊列。優先隊列（參見this維基百科文章）通常使用min-heap作爲它們的基礎數據結構，並保證O（log n）的移除。

來源

2013-08-01 05:21:31 lbrendanl

從二進制索引樹中刪除元素

回答

相關問題