資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法學研究資料結構中的隨機化手指搜尋樹
確定性搜尋樹的兩種隨機化替代方案是隨機二叉搜尋樹、treap 和跳錶。treap 和跳錶都被定義為優雅的資料結構，其中隨機化簡化了簡單而高效的更新操作。
在本節中，我們將解釋 treap 和跳錶如何都能夠實現為高效的手指搜尋樹，而無需更改資料結構本身。兩種資料結構都支援手指搜尋，預期時間複雜度為 O(log d)，其中預期值是在資料結構構建過程中演算法建立的隨機選擇上取的。
跳錶
在跳錶中，可以從包含元素 b 的節點開始對手指搜尋元素 a，只需從此處繼續搜尋即可。請注意，如果 a < b，則搜尋將向後進行；如果 a > b，則搜尋將向前進行。向後搜尋與跳錶中的普通搜尋對稱，但向前搜尋實際上更復雜。通常，跳錶中的搜尋預期速度很快，因為列表開頭的哨兵被認為是最高的節點。但是，我們的手指可能與高度為 1 的節點相關聯。因此，在嘗試搜尋時，我們可能很少向上攀爬；這在正常情況下是永遠不會發生的。但是，即使存在這種複雜性，我們仍然能夠實現 O(log d) 的預期搜尋時間。
Treap
Treap 被定義為隨機二叉搜尋樹 (BST)。在 treap 中搜索與在任何其他 BST 中搜索元素類似。但是，treap 具有這樣的特性：距離為 d 的兩個元素之間的預期路徑長度表示為 O(log d)。因此，對手指搜尋從包含元素 b 的節點開始搜尋元素 a，可以從 b 元素向上遍歷樹，直到找到元素 a 的祖先，此時正常 BST 搜尋將照常進行。雖然計算一個節點是否為另一個節點的祖先並非易事，但可以增強樹以支援這種形式的查詢，以提供 O(log d) 的預期手指搜尋時間。
更新於：2020年1月7日
瀏覽量 136
廣告