Treap

模板

支持以下操作

1. 插入x數(shù)

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

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

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

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

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

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

Treap=Tree+Heap

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