在虛擬樹中，一些邊被視為實線，一些被視為虛線。通常的伸展操作僅在實線樹中執行。為了在虛擬樹中的節點 y 上進行伸展操作，實現了以下方法。該演算法檢視樹三次，每次遍歷一次，並對其進行更改。在第一次遍歷中，僅在實線樹中進行伸展操作，從節點 y 開始，從 y 到整個樹根的路徑變為虛線。此路徑透過拼接變為實線。現在，在節點 y 上進行最終的伸展操作將使 y 成為樹的根。… 閱讀更多

對於給定的森林，我們建立一些給定的邊為“虛線”，其餘邊保持為實線。每個非葉節點僅與一條到其子節點的“實線”邊相關聯。所有其他子節點將透過虛線邊連線。更具體地說，在任何給定的樹中，最右邊的連結（到其子節點）應保持為實線，而所有其他到其其他子節點的連結都建立為“虛線”。結果，樹將被分解成一系列實線路徑。實線路徑的根將連線到其他… 閱讀更多

靜態手指定理 - 假設 f 被視為稱為手指的特定元素。然後，以下表達式是伸展序列成本的上限 O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j注意 - |f-i| 表示專案在專案 i 和手指之間的對稱排序中的距離。其中 m 表示對最多包含 n 個節點的樹進行更新或訪問操作的次數。觀察到，至少在攤銷意義上，在從未超過 n 的樹上進行前 m 次操作所需的時間… 閱讀更多

動態最優性猜想除了伸展樹的已證明效能保證之外，還有一個未經證實的猜想引起了極大的興趣。動態最優性猜想表示此猜想。設任何二叉搜尋樹演算法（如 B）透過遍歷從根到 y 的路徑來訪問元素 y，其成本為 d(y)+1，並且在訪問之間可以在樹中進行任何旋轉，每次旋轉的成本為 1。設 B(s) 為 B 執行訪問序列 s 的成本。那麼伸展樹執行相同訪問的成本為 O[n+B(s)]。有… 閱讀更多

自適應合併排序自適應合併排序執行合併排序所執行的有序子列表的合併。但是，初始子列表的大小取決於元素列表中是否存在排序，而不是具有大小為 1 的子列表。例如，考慮圖中的列表。它包含 2 個有序子列表。子列表 1 包含元素 16、15、14、13。子列表 2 包含元素 9、10、11、12。子列表 1 是有序的，但順序相反。因此，子列表 1 反轉，如圖所示。一旦找到子列表，合併過程就開始了。自適應合併排序開始合併子列表。自適應合併… 閱讀更多

在跳錶中，可以從包含元素 b 的節點開始對元素 a 進行手指搜尋，只需從此處繼續搜尋 a 即可。請注意，如果 a < b，則搜尋向後進行，如果 a > b，則搜尋向前進行。向後情況與跳錶中的正常搜尋對稱，但向前情況實際上更復雜。通常，跳錶中的搜尋預計會很快，因為列表開頭的哨兵被視為最高的節點。但是，我們的手指可能與… 閱讀更多

確定性搜尋樹的兩種隨機化替代方案是隨機二叉搜尋樹、treap 和跳錶。treap 和跳錶都被定義為優雅的資料結構，其中隨機化有助於簡單高效地進行更新操作。在本節中，我們將解釋 treap 和跳錶如何都可以在不更改資料結構的情況下實現為高效的手指搜尋樹。這兩種資料結構都支援手指搜尋，消耗預期 O(log d) 時間，其中期望值取自演算法在構建資料結構期間建立的隨機選擇。跳錶在跳錶中，可以… 閱讀更多

在本節中，我們將解釋 (2, 4) 樹如何透過引入層級連結來支援高效的手指搜尋。本節中解釋的想法也適用於更通用的高度平衡樹類，表示為 (a, b) 樹，其中 b ≥ 2a。(2, 4) 樹被定義為高度平衡的搜尋樹，其中所有葉子都具有相同的深度，並且所有內部節點都具有二、三或四個度。元素儲存在葉子中，內部節點僅儲存搜尋鍵以指導搜尋。由於每個內部節點的度至少為二，因此可以得出 (2, 4) 樹… 閱讀更多

除了手指搜尋之外，動態手指搜尋資料結構還應該執行在由手指給出的位置插入和刪除元素的操作。手指搜尋樹被定義為支援手指搜尋的 B 樹的變體，時間為 O(log d)，更新時間為 O(1)，假設僅維護 O(1) 個可移動手指。遍歷手指 d 個位置需要 O(log d) 時間。手指搜尋樹（即 AVL 樹、紅黑樹）的構造要麼考慮固定數量的手指，要麼僅支援攤銷常數時間內的更新。支援任意數量的手指並在最壞情況下更新的構造… 閱讀更多

資料結構上的手指搜尋被定義為結構支援的任何搜尋操作的擴充套件，其中給出了對資料結構中元素的引用（手指）以及查詢。雖然元素的搜尋時間最常表示為資料結構中元素數量的函式，但手指搜尋時間被視為元素與手指之間距離的函式。在一組 m 個元素中，兩個元素 a 和 b 之間的距離 d(a, b) 是它們在秩中的差值。如果元素 a 和… 閱讀更多