????Treap = Tree + Heap, 又稱樹堆， 它在滿足二叉搜索樹的同時(shí)又滿足堆的性質(zhì)。

????因?yàn)槎嫠阉鳂?，根?jù)輸入序列不同創(chuàng)建的樹也不同，最壞的情況會(huì)退化為線性（只有左子樹或右子樹）。

????二叉搜素樹的效率和樹高成正比，因此在構(gòu)建二叉搜索樹時(shí)，盡可能地平衡左右子樹，力求期望時(shí)間復(fù)雜度為 O(logn)。平衡地方法很多， AVL樹，splay樹，紅黑樹等，這些調(diào)平衡地方法相對(duì)復(fù)雜。

????如果一個(gè)二叉搜索樹插入結(jié)點(diǎn)地順序是隨機(jī)的，得到的二叉搜索樹大多情況下是平衡的，即使存在一些極端情況，但是這種情況發(fā)生的概率很小，因此以隨機(jī)順序創(chuàng)建的二叉搜索樹，其期望高度是 O(log n) 。可以將輸入數(shù)據(jù)隨機(jī)打亂，再創(chuàng)建二叉搜索樹，但是某些時(shí)候我們并不能事前得知所有待插入的結(jié)點(diǎn)， Treap 可以有效解決該問題。

????樹堆也是一種平衡二叉搜索樹，它給每個(gè)結(jié)點(diǎn)附加一個(gè)隨機(jī)數(shù)值，使其滿足堆的性質(zhì)，而結(jié)點(diǎn)的值又滿足二叉搜索樹，其基本操作（增刪改查）的期望時(shí)間復(fù)雜度 O(log n)。相對(duì)于其他的平衡二叉樹， Trap 的特點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，且能基本實(shí)現(xiàn)隨機(jī)平衡的結(jié)構(gòu)。

????樹堆的構(gòu)建過程中，插入結(jié)點(diǎn)時(shí)會(huì)給每個(gè)結(jié)點(diǎn)附加一個(gè)隨機(jī)數(shù)作為優(yōu)先級(jí)，該優(yōu)先級(jí)滿足堆的性質(zhì)（最大堆或最下堆均可，這里以最大堆為例，根的優(yōu)先級(jí)大于左右孩子），數(shù)值滿足二叉搜索樹性質(zhì)（中序有序，左子樹大于根，右子樹小于根）。

例如：輸入 6 4 9 7 2構(gòu)建的樹堆，如圖所示。

????

樹堆是如何構(gòu)建的呢？
? ? 調(diào)平衡：樹堆需要兩種旋轉(zhuǎn)操作，右旋和左旋。

（1）右旋（zig）

????結(jié)點(diǎn) p 右旋時(shí)，攜帶自己的右孩子，向右旋轉(zhuǎn)到 q 的右子樹位置， q 的右子樹被擠掉，此時(shí) p 右旋后左子樹正好空閑，將 q 的游資是放在 p 的左子樹，旋轉(zhuǎn)后的樹根為 q 。

（2）左旋（zag）

????結(jié)點(diǎn) p 左旋時(shí)，攜帶自己的孩子，向左旋轉(zhuǎn)到 q 的左子樹位置， q 的左子樹被擠掉拋棄，此時(shí) p 左旋后右子樹正好空閑，將 q 的左子樹放在 p 的右子樹，旋轉(zhuǎn)后的樹根為 q 。

總結(jié)：無論是右旋還是左旋，旋轉(zhuǎn)后，總有一個(gè)孩子被拋棄，一個(gè)指針空閑，正好配對(duì)。

（3）插入

????樹堆的插入操作，和二叉搜索樹一樣首先根據(jù)有序性找到插入位置，然后創(chuàng)建新結(jié)點(diǎn)插入； 創(chuàng)建新結(jié)點(diǎn)時(shí)，會(huì)給該結(jié)點(diǎn)附加一個(gè)隨機(jī)數(shù)作為優(yōu)先級(jí)，自底向上檢查該優(yōu)先級(jí)是否滿足堆性質(zhì)，如果不滿足則需要右旋或左旋，使其滿足堆性質(zhì)。

算法步驟：

???

回退操作/回溯：在遞歸調(diào)用的下面，寫回退程序。上面代碼就是在遞歸調(diào)用結(jié)束后，回退時(shí)進(jìn)行旋轉(zhuǎn)操作。

（4）刪除

????樹堆的刪除操作非常簡(jiǎn)單，首先找到待刪除的結(jié)點(diǎn)，然后將其向優(yōu)先級(jí)大的孩子旋轉(zhuǎn)，一直旋轉(zhuǎn)到葉子，直接刪除葉子即可。

性能分析：

????由于樹堆引入了隨機(jī)性，構(gòu)建的樹堆是一種平衡二叉樹，其查找，插入，刪除，求前驅(qū)和后繼的時(shí)間復(fù)雜度均為 O(log n)。