Treap介紹

我們可以看到，如果一個二叉排序樹節(jié)點插入的順序是隨機的，這樣我們得到的二叉排序樹大多數(shù)情況下是平衡的，即使存在一些極端情況，但是這種情況發(fā)生的概率很小，所以我們可以這樣建立一顆二叉排序樹，而不必要像AVL那樣旋轉(zhuǎn)，可以證明隨機順序建立的二叉排序樹在期望高度是O(logn)，但是某些時候我們并不能得知所有的帶插入節(jié)點，打亂以后再插入。所以我們需要一種規(guī)則來實現(xiàn)這種想法，并且不必要所有節(jié)點。也就是說節(jié)點是順序輸入的，我們實現(xiàn)這一點可以用Treap。

Treap=Tree+Heap

Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數(shù)據(jù)，就是優(yōu)先級。Treap在以關(guān)鍵碼構(gòu)成二叉排序樹的同時，還滿足堆的性質(zhì)(在這里我們假設節(jié)點的優(yōu)先級大于該節(jié)點的孩子的優(yōu)先級)。但是這里要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap可以并不一定是。

模板

支持以下操作

1. 插入x數(shù)

2. 刪除x數(shù)(若有多個相同的數(shù)，因只刪除一個)

3. 查詢x數(shù)的排名(若有多個相同的數(shù)，因輸出最小的排名)

4. 查詢排名為x的數(shù)

5. 求x的前驅(qū)(前驅(qū)定義為小于x，且最大的數(shù))

6. 求x的后繼(后繼定義為大于x，且最小的數(shù))