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中查找的期望複雜度是

。 ^[1] 

二叉搜索樹有一個特性，就是每個子樹的形態在優先級唯一確定的情況下都是唯一的，不受其他因素影響，也就是説，左子樹的形態與樹中大於根節點的值無關，右子樹亦然。這是因為Treap滿足堆的性質，Treap的根節點是優先級最大的那個節點，考慮它的左子樹，樹根也是子樹裏面最大的一點，右子樹亦然。所以Treap相當於先把所有節點按照優先級排序，然後插入，實質上就相當於以隨機順序建立的二叉搜索樹，只不過它並不需要一次讀入所有數據，可以一個一個地插入。而當這個隨機順序確定的時候，這個樹是唯一的。因此在給定優先級的情況下，只要是用符合要求的操作，通過任何方式得出的Treap都是一樣的，所以不改變優先級的情況下，特殊的操作不會造成Treap結構的退化。而改變優先級可能會使Treap變得不夠隨機以致退化。

Treap的其它操作的期望複雜度同樣是

。 ^[1]