樹堆，在數據結構中也稱Treap，是指有一個隨機附加域滿足堆的性質的二叉搜尋樹，其結構相當於以隨機數據插入的二叉搜尋樹。其基本操作的期望時間複雜度為O(logn)。相對於其他的平衡二叉搜尋樹，Treap的特點是實現簡單，且能基本實現隨機平衡的結構。
基本介紹
- 中文名：樹堆
- 外文名：Tree heap
- 別名：treap
- 性質：自平衡二叉查找樹
- 用途：實現關聯數組
介紹,操作,插入,刪除,模板,
介紹
我們可以看到，如果一個二叉排序樹節點插入的順序是隨機的，這樣我們得到的二叉排序樹大多數情況下是平衡的，即使存在一些極端情況，但是這種情況發生的機率很小，所以我們可以這樣建立一顆二叉排序樹，而不必要像AVL那樣旋轉，可以證明隨機順序建立的二叉排序樹在期望高度是O(logn)，但是某些時候我們並不能得知所有的帶插入節點，打亂以後再插入。所以我們需要一種規則來實現這種想法，並且不必要所有節點。也就是說節點是順序輸入的，我們實現這一點可以用Treap。
Treap=Tree+Heap
Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數據，就是優先權。Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆的性質(在這裡我們假設節點的優先權大於該節點的孩子的優先權)。但是這裡要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap可以並不一定是。
操作
Treap維護堆性質的方法用到了旋轉，這裡先簡單地介紹一下。Treap只需要兩種旋轉，這樣編程複雜度比Splay等就要小一些，這正是Treap的特色之一。
旋轉是這樣的：
treap旋轉插入
給節點隨機分配一個優先權，先和二叉排序樹的插入一樣，先把要插入的點插入到一個葉子上，然後跟維護堆一樣，如果當前節點的優先權比根大就旋轉，如果當前節點是根的左兒子就右旋如果當前節點是根的右兒子就左旋。
我們如果把插入寫成遞歸形式的話，只需要在遞歸調用完成後判斷是否滿足堆性質，如果不滿足就旋轉，實現非常容易。
由於是旋轉的二叉排序樹，最多進行h次(h是樹的高度),插入的複雜度是log( n )的，在期望情況下，所以它的期望複雜度是 O( log( N ) );
void insert(int &k,int x){ if(k==0) { size++;k=size; tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=rand(); return; } tr[k].size++; if(tr[k].v==x)tr[k].w++;//每個結點順便記錄下與該節點相同值的數的個數 else if(x>tr[k].v) { insert(tr[k].r,x); if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);//維護堆性質 } else { insert(tr[k].l,x); if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k); } }刪除
有了旋轉的操作之後，Treap的刪除比二叉排序樹還要簡單。因為Treap滿足堆性質，所以我們只需要把要刪除的節點旋轉到葉節點上，然後直接刪除就可以了。具體的方法就是每次找到優先權最大的兒子，向與其相反的方向旋轉，直到那個節點被旋轉到葉節點，然後直接刪除。刪除最多進行log( n )次旋轉，期望複雜度是log( n )。
void del(int &k,int x){ if(k==0)return; if(tr[k].v==x) { if(tr[k].w>1) { tr[k].w--;tr[k].size--;return;//若不止相同值的個數有多個，刪去一個 } if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;//有一個兒子為空 else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd) rturn(k),del(k,x); else lturn(k),del(k,x); } else if(x>tr[k].v) tr[k].size--,del(tr[k].r,x); else tr[k].size--,del(tr[k].l,x);}第二種刪除方法：為保證效率，可以用普通二叉查找樹的刪除方法，找到節點的中序前綴，然後替換，刪除，並使用非遞歸。雖然時間複雜度仍為log級別，但常數因子小了很多。
Pascal代碼：
procedure del(x:longint);var now,MinMax,p:point;begin now:=root;//root為根指針 null^.x:=x; whilenow^.x<>xdobegin p:=now; ifnow^.x>xthen now:=now^.lelse now:=now^.r;end; ifnow=nullthen//沒找到X exit; ifnow^.l<>nullthen//左子樹不為空，往左找begin MinMax:=now^.l; p:=now; whileMinMax^.r<>nulldobegin p:=MinMax; MinMax:=MinMax^.r;end; now^.x:=MinMax^.x; ifp<>nowthen p^.r:=MinMax^.lelse p^.l:=MinMax^.l; dispose(MinMax);endelse ifnow^.r<>nullthen//右子樹不為空，往右找begin MinMax:=now^.r; p:=now; whileMinMax^.l<>nulldobegin p:=MinMax; MinMax:=MinMax^.l;end; now^.x:=MinMax^.x; ifp<>nowthen p^.l:=MinMax^.relse p^.r:=MinMax^.r; dispose(MinMax);endelse//X本身是葉子begin ifp^.x>xthen p^.l:=nullelse p^.r:=null; dispose(now);end;end;
查找
和一般的二叉排序樹一樣，但是由於Treap的隨機化結構，可以證明Treap中查找的期望複雜度是log( n )。
分離
要把一個Treap按大小分成兩個Treap，只要在需要分開的位置加一個虛擬節點，然後旋至根節點刪除，左右兩個子樹就是得出的兩個Treap了。根據二叉排序樹的性質，這時左子樹的所有節點都小於右子樹的節點。
時間相當於一次插入操作的複雜度，也就是 log( n )
合併
合併是指把兩個Treap合併成一個Treap，其中第一個Treap的所有節點都必須小於或等於第二個Treap中的所有節點，也就是分離的結果所要滿足的條件。合併的過程和分離相反，只要加一個虛擬的根，把兩棵樹分別作為左右子樹，然後把根刪除就可以了。
時間複雜度和刪除一樣，也是期望
旋轉
旋轉就是把random出來的值進行維護堆得性質的操作.因為BST得特殊性質,所以在旋轉時,還要維護BST的性質。
void rturn(int &k){ int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k; k=t;}void lturn(int &k){ int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k; k=t;}算法分析
首先我們注意到二叉排序樹有一個特性，就是每個子樹的形態在優先權唯一確定的情況下都是唯一的，不受其他因素影響，也就是說，左子樹的形態與樹中大於根節點的值無關，右子樹亦然。
這是因為Treap滿足堆的性質，Treap的根節點是優先權最大的那個節點，考慮它的左子樹，樹根也是子樹裡面最大的一點，右子樹亦然。所以Treap相當於先把所有節點按照優先權排序，然後插入，實質上就相當於以隨機順序建立的二叉排序樹，只不過它並不需要一次讀入所有數據，可以一個一個地插入。而當這個隨機順序確定的時候，這個樹是唯一的。
因此在給定優先權的情況下，只要是用符合要求的操作，通過任何方式得出的Treap都是一樣的，所以不改變優先權的情況下，特殊的操作不會造成Treap結構的退化。而改變優先權可能會使Treap變得不夠隨機以致退化。
證明隨機建立二叉排序樹的大家可以參見CLRS P265 12.4 Randomly built binary search trees，這裡略去。
模板
模板
支持以下操作
1. 插入x數
2. 刪除x數(若有多個相同的數，應只刪除一個)
3. 查詢x數的排名(若有多個相同的數，應輸出最小的排名)
4. 查詢排名為x的數
5. 求x的前驅(前驅定義為小於x，且最大的數)
6. 求x的後繼(後繼定義為大於x，且最小的數)
//by hzwer#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;struct data{ int l,r,v,size,rnd,w;}tr[100005];int n,size,root,ans;void update(int k)//更新結點信息{ tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;}void rturn(int &k){ int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k; tr[t].size=tr[k].size;update(k);k=t;}void lturn(int &k){ int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k; tr[t].size=tr[k].size;update(k);k=t;}void insert(int &k,int x){ if(k==0) { size++;k=size; tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=rand(); return; } tr[k].size++; if(tr[k].v==x)tr[k].w++; else if(x>tr[k].v) { insert(tr[k].r,x); if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k); } else { insert(tr[k].l,x); if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k); } }void del(int &k,int x){ if(k==0)return; if(tr[k].v==x) { if(tr[k].w>1) { tr[k].w--;tr[k].size--;return; } if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r; else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd) rturn(k),del(k,x); else lturn(k),del(k,x); } else if(x>tr[k].v) tr[k].size--,del(tr[k].r,x); else tr[k].size--,del(tr[k].l,x);}int query_rank(int k,int x){ if(k==0)return 0; if(tr[k].v==x)return tr[tr[k].l].size+1; else if(x>tr[k].v) return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r,x); else return query_rank(tr[k].l,x);}int query_num(int k,int x){ if(k==0)return 0; if(x<=tr[tr[k].l].size) return query_num(tr[k].l,x); else if(x>tr[tr[k].l].size+tr[k].w) return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w); else return tr[k].v;}void query_pro(int k,int x){ if(k==0)return; if(tr[k].v<x) { ans=k;query_pro(tr[k].r,x); } else query_pro(tr[k].l,x);}void query_sub(int k,int x){ if(k==0)return; if(tr[k].v>x) { ans=k;query_sub(tr[k].l,x); } else query_sub(tr[k].r,x);}int main(){ scanf("%d",&n); int opt,x; for(int i=1;i<=n;i++) { scanf("%d%d",&opt,&x); switch(opt) { case 1:insert(root,x);break; case 2:del(root,x);break; case 3:printf("%d\n",query_rank(root,x));break; case 4:printf("%d\n",query_num(root,x));break; case 5:ans=0;query_pro(root,x);printf("%d\n",tr[ans].v);break; case 6:ans=0;query_sub(root,x);printf("%d\n",tr[ans].v);break; } } return 0;}