在O（logn）O（logn）刪除和索引訪問的數據結構

Question

請推薦一個O（logn）刪除的數據結構，並且我需要索引O（1）或O（logn）中數據結構中的元素。

Answer 1

大多數自我平衡有序的二叉樹可以被修改，以保持每個節點的孩子數量，並保持每個操作的lg（n）時間是非常容易的。

它們明確修改每個操作少於lg（n）個節點，並且根據我的經驗，它們修改的節點通常是「垂直相關的」。它不是免費的，但它往往不昂貴。

一旦你有樹的節點，找到n個元素的數據很容易（如果n是更大然後＃在左子樹，從n減去＃左子樹和遞歸到右子樹，否則遞歸到左子樹中，保持不變n）。

這也適用於非二元自平衡樹，如B樹。

據我所知，沒有std容器支持隨機對數刪除，插入和索引操作。我找了一回。我也對boost進行了快速檢查，甚至查看了多索引容器，並且找不到一種方法來實現它。

腳註：

當你修改你想要得到一個節點的孩子的數量的成本是一棵樹O（1）在節點上，你必須從修改節點你的變化一直到根。每個修改節點至多有lg（n）個。但是，如果節點彼此「垂直相關」，則需要修復的節點在每個節點更改上幾乎都是相同的。另一方面，假設你的樹重新平衡算法以某種方式設法修改lg（n）完全不相關的節點，成本將高達lg（n）* lg（n）來維持計數。