通過O（logn）訪問和O（logn）插入實現數據結構？

Question

有沒有人知道一個數據結構，我可以在最壞的情況下訪問和刪除第k個項目O（logn），並且還支持在最壞的情況下O（logn）在第k個項目之後插入項目的操作？

Answer 1

是的。你所描述的可以通過增強樹來實現。每個節點都有一個計數器，指示其子樹（包括其本身）中的節點數量。對於葉節點，計數器爲1.對於根節點，計數器是節點的總數。這樣，您可以從根開始查找具有二分搜索的第k個項目。無論何時插入/移除元素，都必須更新從該位置到根的路徑中的計數器。

這種樹被稱爲order statistic trees，排名樹木，樹木櫃臺...

你可以找到一個實現here，另一個here。

請參閱Cormen，Leiserson，Rivest和Stein撰寫的名爲「Intorduction to Algorithms」的第14章「增加數據結構」。

Answer 2

如果您需要整數索引（與鍵相對），請查看rope或deque，這對於這些操作本質上是O（c）。對於關聯數據結構，一個典型的散列表也將被分攤到O（c），而一個平衡樹將是O（log（n））。