資料結構中的動態手指搜尋樹

• 動態手指搜尋資料結構除了手指搜尋之外，還應該在由手指給定的位置執行元素的插入和刪除操作。
• 手指搜尋樹定義為 B 樹的一種變體，支援在 O(log d) 時間內進行手指搜尋，並在 O(1) 時間內進行更新，假設僅維護 O(1) 個可移動手指。
• 遍歷 d 個手指位置需要 O(log d) 時間。
• 手指搜尋樹（即 AVL 樹、紅黑樹）的構建要麼考慮固定數量的手指，要麼僅支援攤銷常數時間內的更新。
• 已經建立了支援任意數量的手指並在最壞情況下更新的構建方法。
• 一種搜尋樹，它支援在任意位置以最壞情況 O(1) 時間進行更新，但僅支援在 O(log n) 時間內進行搜尋。
• 支援 O(log d) 時間搜尋和 O(log d n) 時間插入和刪除的構建方法。
• 手指搜尋樹消耗最壞情況常數時間插入和 O(log d n) 時間刪除。
• 根據一種對級別連結 (2,4) 樹的空間高效的替代方案，允許一個手指，它可以透過與 (2,4) 樹相同的效能成本進行處理。在該方案中，不需要級別連結和父指標，而是為手指建立了一個特殊的 O(log n) 空間資料結構（hand），允許有效地遍歷手指。
• 伸展樹定義為一類自調整二叉搜尋樹，支援在攤銷 O(log n) 時間內進行搜尋、插入和刪除。即伸展樹可以作為高效的手指搜尋樹來實現。
• 給定 O(n) 的初始化成本，在伸展樹中距離上次訪問位置 d 的訪問的攤銷成本為 O(log d)，其中訪問包括搜尋、插入和刪除。
• 請注意，該語句僅在存在一個手指的情況下實現，該手指始終指向上次訪問的元素。
• 所有上述構建方法都可以在指標機上應用，其中在元素上唯一允許的操作是比較兩個元素。
• 對於隨機訪問機計算模型 (RAM)，開發了一種具有常數更新時間和 O(log d) 搜尋時間的手指搜尋樹。此結果是透過製表小型樹結構實現的，但僅執行元素的比較。

Arnab Chakraborty

更新於： 2020年1月7日

296 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習