通過索引和鍵支持隨機訪問的數據結構，在維持順序的對數時間內插入和刪除

Question

我正在查找存儲E =（K，V）元素的有序列表並支持以下操作的數據結構最多爲O（log（N））時間，其中N是元素的數量。內存使用不成問題。

• Ë得到（指數）的指數//獲取元素
• INT查找（K）//找到元素，其ķ匹配
• 刪除（指數）的指數//在索引中刪除元素，以下的元件及其索引減少1個
• 刀片（指數，E）//插入在索引元件，下面的元件及其索引增加1

我已經考慮以下不正確的解決方案：

• 使用數組：find，delete，和insert仍將O（N）
• 使用陣列+ K的地圖索引：delete和insert仍然將花費O（N），用於切換元件和更新地圖
• 使用鏈接的K表+地圖元素地址：get和find仍然將花費O（N）

在我的想象中，最後的解決方案是最接近的，而是鏈表，一個自我平衡的樹每個節點在其左側存儲元素的數量將使我們可以在O（log（N））中執行get。

但是我不確定我是否正確，所以我想問一下我的想象是否正確以及是否有這種數據結構的名稱，以便我可以尋找現成的解決方案。

Answer 1

我能想到的最接近的數據結構是treaps。

隱式treap是對常規treap的簡單修改，這是一個非常強大的數據結構。事實上，隱式樹堆可以被認爲是與實施（全部在O（logN）的O（log⁡N）在在線模式）以下過程的數組：

1. 在任何位置處插入的元件陣列中的
2. 去除任意元素
3. 的上的任意間隔查找總和，最小/最大元件等
4. 加法，畫上的任意間隔
5. 上的任意間隔反向元件

使用隱式鍵修改允許您執行除第二個鍵外的所有操作（查找K匹配的元素的索引）。我會編輯這個答案，如果我想出一個更好的主意:)

Answer 2

您可以根據您的要求維護一個堆陣列。