? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

好了我就很愉快的回來補坑了~

Treap也是一種平衡樹，它較普通二叉查找樹而言，每個節(jié)點被賦予了一個新的屬性：優(yōu)先級（沒錯就是類似優(yōu)先隊列的優(yōu)先），對于Treap中的每個結(jié)點，除了它的權(quán)值滿足二叉查找樹的性質(zhì)外，它的優(yōu)先級還滿足堆性質(zhì)，也就是結(jié)點的優(yōu)先級小于它所有孩子的優(yōu)先級。

換句話說，從權(quán)值上看，Treap是一個二叉查找樹；從優(yōu)先級上看，Treap是一個堆。所以我們發(fā)現(xiàn)Treap其實可以看做是Tree+Heap。

我們發(fā)現(xiàn)普通BST會不平衡是因為有序的數(shù)據(jù)會使查找路徑退化成鏈，而隨機數(shù)據(jù)使其退化的概率非常小。因此我們在Treap中賦予的這個優(yōu)先級的值采用隨機生成的辦法，這樣Treap的結(jié)構(gòu)就趨于平衡了。（如果臉黑怎么辦（逃））

如果我們假設(shè)所有點的權(quán)值與優(yōu)先級都互不相同，那么Treap的形態(tài)是唯一確定的。

我們考慮在所有結(jié)點中找到優(yōu)先級最小的點，則它一定是Treap的根，而權(quán)值小于它的點會在根的左子樹，大于它的點會在根的右子樹，這就可以遞歸下去構(gòu)建Treap。這個建立過程與快速排序類似，因此Treap的期望深度與快排的期望遞歸層數(shù)一樣都是O(log n)的。

為了使Treap滿足性質(zhì)，有時我們不可避免地要對結(jié)構(gòu)進行調(diào)整，而我們調(diào)整的方式是旋轉(zhuǎn)。在維護Treap的過程中，我們會出現(xiàn)兩種旋轉(zhuǎn)：左旋與右旋。

左旋一個子樹，這個子樹的根節(jié)點為x，則旋轉(zhuǎn)后會把x變?yōu)檫@個子樹的新根的左兒子，x的右兒子會成為子樹新的根。右旋一個子樹，這個子樹的根節(jié)點為x，則旋轉(zhuǎn)后會把x變?yōu)檫@個子樹的新根的右兒子，x的右兒子會成為子樹新的根。（詳細圖解見Splay，傳送門：https://blog.csdn.net/g21glf/article/details/82931486）。

顯然旋轉(zhuǎn)后這個Treap仍然滿足權(quán)值的BST性質(zhì)，因此這個旋轉(zhuǎn)操作就保證了，若我們滿足了BST性質(zhì)，那么不滿足堆性質(zhì)的部分我們可以通過旋轉(zhuǎn)，使其滿足堆性質(zhì)。旋轉(zhuǎn)的意義也正是在此，使不滿足堆序的兩個節(jié)點通過調(diào)整位置，重新滿足堆序，而不改變BST性質(zhì)。

Treap的各種操作與BST無異，唯一有些不同的就是插入操作。我們從根節(jié)點開始插入，如果要插入的值小于當前節(jié)點的值，那么我們要在當前節(jié)點的左子樹進行插入；否則我們要在當前節(jié)點的右子樹進行插入； 若當前節(jié)點是個空節(jié)點， 則我們在這個位置上新建一個節(jié)點。插入之后新建的這個節(jié)點可能會使Treap不滿足堆性質(zhì)，那么我們就通過旋轉(zhuǎn)操作不斷調(diào)整，這個步驟可以通過遞歸來實現(xiàn)。

在刪除時，我們首先需要在Treap上走，找到需要刪除的那個節(jié)點，接著我們可以利用旋轉(zhuǎn)操作不停調(diào)整需要刪除的這個節(jié)點在樹中的位置。若刪除節(jié)點為葉節(jié)點，那么我們可以直接刪除； 若它只有一個兒子， 那么我們直接讓那個兒子代替這個被刪除的節(jié)點即可。 否則，若刪除節(jié)點左兒子的優(yōu)先級小于刪除節(jié)點右兒子優(yōu)先級，那么我們對刪除節(jié)點進行右旋，讓左兒子成為新的子樹的根；反之同理。直到它變?yōu)榍皟煞N情況。

由于Treap的樹高是期望O(log n)的，所以它各個操作的期望復雜度也是O(log n)。

【貼代碼~】

更新 void update(const int &k) {tr[k].size=tr[lc[k]].size+tr[rc[k]].size; } 右旋 void zig(int &k) {int y=lc[k];lc[k]=rc[y];rc[y]=k;size[y]=size[k];update(k);k=y; } 左旋 void zag(int &k) {int y=rc[k];rc[k]=lc[y];lc[y]=k;size[y]=size[k];update(k);k=y; } 插入 void insert(int &k,int &key) {if(!k){k=++pool;key[k]=key;pri[k]=rand();cnt[k]=size[k]=1;lc[k]=rc[k]=0;return ;}else++size[k];if(k.key==key)++cnt[k];else{if(key<k.key){insert(lc[k],key);if(pri[lc[k]]>pri[k])zig(k);}else{insert(rc[k],key);if(pri[rc[k]]<pri[k])zag(k);}}return ; } 刪除 void del(int &k,int &key) {if(k.key==key){if(cnt[k]>1)cnt[k]--,size[k]--;else{if(!lc[k]||!rc[k])k=lc[k]+rc[k];else{if(pri[lc[k]]<pri[rc[k]])zig(k),del(k,key);elsezag(k),del(k,key);}}}else--size[k];if(key<k.key)del(lc[k],key);elsedel(rc[k],key);return ; } 詢問優(yōu)先級 int queryrank(const int &key) {int x=rt,res=0;while(x){if(key==key[x])return res+size[lc[x]]+1;if(key<key[x])x=lc[x];elseres+=size[lc[x]]+cnt[x],x=rc[x];}return res; } 尋找第k大 int querykth(int k) {int x=rt;while(x){if(size[lc[x]]<k&&size[lc[x]]+size[x]>=k)return x.key;if(size[lc[x]]>=k)x=lc[x];elsek-=size[lc[x]]+cnt[x],x=rc[x];}return 0; } 求前驅(qū) int querypre(const int &k) {int x=rt,res=-INF;while(x){if(key[x]<key)res=key[x],x=rc[x];elsex=lc[x];}return res; } 求后繼 int querysuf(const int &k) {int x=rt,res=INF;while(x){if(key[x]>key)res=key[x],x=lc[x];elsex=rc[x];}return res; }

以上就是個人關(guān)于Treap的一些感悟，后續(xù)會補坑。。。

轉(zhuǎn)載于:https://www.cnblogs.com/Ishtar/p/10010833.html

總結(jié)

以上是生活随笔為你收集整理的关于Treap的学习感受的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。