基本介紹
- 中文名：樹堆
- 外文名：Tree heap
- 別名：treap
- 性質：自平衡二叉查找樹
- 用途：實現關聯數組
簡介,基本介紹,插入,刪除,查找,算法分析,與其他結構的比較,
簡介
樹堆（英語：Treap），是有一個隨機附加域滿足堆的性質的二叉搜尋樹，其結構相當於以隨機數據插入的二叉搜尋樹。其基本操作的期望時間複雜度為{\displaystyle O(\log {n})}。相對於其他的平衡二叉搜尋樹，Treap的特點是實現簡單，且能基本實現隨機平衡的結構。
基本介紹
Treap=Tree+Heap。Treap本身是一棵二叉搜尋樹，它的左子樹和右子樹也分別是一個Treap，和一般的二叉搜尋樹不同的是，Treap紀錄一個額外的數據，就是優先權。Treap在以關鍵碼構成二叉搜尋樹的同時，還滿足堆的性質。Treap維護堆性質的方法用到了旋轉，只需要兩種旋轉，編程複雜度比Splay要小一些。
插入
給節點隨機分配一個優先權，先和二叉搜尋樹的插入一樣，先把要插入的點插入到一個葉子上，然後跟維護堆一樣，如果當前節點的優先權比根大就旋轉，如果當前節點是根的左兒子就右旋如果當前節點是根的右兒子就左旋。
由於旋轉是O(1)的，最多進行h次（h是樹的高度），插入的複雜度是O(h)的，在期望情況下
，所以它的期望複雜度是。
刪除
因為Treap滿足堆性質，所以只需要把要刪除的節點旋轉到葉節點上，然後直接刪除就可以了。具體的方法就是每次找到優先權最大的兒子，向與其相反的方向旋轉，直到那個節點被旋轉到了葉節點，然後直接刪除。
刪除最多進行O(h)次旋轉，期望複雜度是。
查找
和一般的二叉搜尋樹一樣，但是由於Treap的隨機化結構，Treap中查找的期望複雜度是。
算法分析
二叉搜尋樹有一個特性，就是每個子樹的形態在優先權唯一確定的情況下都是唯一的，不受其他因素影響，也就是說，左子樹的形態與樹中大於根節點的值無關，右子樹亦然。這是因為Treap滿足堆的性質，Treap的根節點是優先權最大的那個節點，考慮它的左子樹，樹根也是子樹裡面最大的一點，右子樹亦然。所以Treap相當於先把所有節點按照優先權排序，然後插入，實質上就相當於以隨機順序建立的二叉搜尋樹，只不過它並不需要一次讀入所有數據，可以一個一個地插入。而當這個隨機順序確定的時候，這個樹是唯一的。因此在給定優先權的情況下，只要是用符合要求的操作，通過任何方式得出的Treap都是一樣的，所以不改變優先權的情況下，特殊的操作不會造成Treap結構的退化。而改變優先權可能會使Treap變得不夠隨機以致退化。
Treap的其它操作的期望複雜度同樣是。
與其他結構的比較
- 伸展樹（Splay Tree）
- Size Balanced Tree
