用於刪除O（logN）中小於k的元素的數據結構其中N是元素數

Question

如何實現O（logN）中具有以下函數的數據結構？

插入（X） - 添加整數設置

構件（x）的 - 檢查是否集包含整數x

刪除（x）的 - 從設置

除去整數x

deleteLessThan（x）的 刪除等於或小於所有數字大於k

我唯一能想到的就是使用某種平衡的BST來獲取插入，成員和刪除的O（log N）。

deleteLessThan（）函數然後看起來像這樣：找到大於k的最小元素，刪除其左側子樹，然後重新平衡。但是，如果刪除其中的一個子樹，是否可以重新平衡O（logN）中的BST？

Answer 1

攤銷日誌N足夠好嗎？在這種情況下，您可以使用splay樹。除了刪除元素< = k之外的所有操作與維基百科上的說明相同。對於其餘操作，將大於k的最小元素展開到頂部，並刪除其左側子樹。

如果允許分期付款，您可以輕鬆地考慮在O（M）時間內刪除N個節點中的M個。