是否存在具有以下操作的資料結構？
get(idx) -> Item獲取 index 處的專案idx。insert(idx, item)idx在結構中的索引處插入專案。應該是 O(log N) 最壞的情況。delete(idx)洗掉 index 處的專案idx。track_index(idx) -> Handle給出與 處的專案關聯的“句柄”idx，以便我稍后可以使用下一個函式來詢問該專案的索引是什么。retrieve_index(handle) -> index回傳與前一個函式創建的句柄關聯的項的當前索引。
我希望所有這些都具有O(log N)最壞情況的運行時間。
我已經對如何實作它有了一個想法（我正在考慮 AVL 樹，每個節點都存盤其左右后代的數量），但我想知道是否已經有這樣的名稱，或者它是否可以重新利用其他一些常見的資料結構來獲得這些操作。
編輯：我的專案資料型別不是完全或部分排序的。
uj5u.com熱心網友回復：
您可以使用任何自平衡搜索樹（AVL、紅黑、B-tree、B -tree、...），并使用在操作期間保持更新的節點計數屬性來擴充它們的節點。同樣，您可以使用此類屬性擴充跳過串列。
這將允許通過具有 O(logn) 時間復雜度的索引來檢索/插入/洗掉元素。
“句柄”將是指向樹中值所在位置的指標，并且通過執行緒化樹（即包括父指標），這樣的句柄提供了關于值在樹中的位置的完整資訊，允許獲取它的索引, 其前身或后繼者。
uj5u.com熱心網友回復：
具有這些屬性的資料結構的一個選項是平衡二叉搜索樹。這種型別的樹具有 O(log N) 的插入、洗掉和搜索時間復雜度，以及跟蹤樹中專案索引的能力。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505893.html
上一篇：匈牙利最大匹配中的除錯