樹：Treap樹

我們知道，二叉查找樹相對來說比較容易形成最壞的連結清單情況，是以前輩們想盡了各種優化政策，包括AVL，紅黑，以及今天要講的Treap樹。

Treap樹是什麼？

Treap=Tree+Heap

treap是heap和tree結合，中文名叫樹堆。

首先它每個節點有2個值value和weight，其中隻看weight的話，滿足heap二叉堆的特性(父親比兒子都小/大)，隻看value的話，滿足排序二叉樹特性(以左兒子為根的子樹元素都比父親小，右兒子為根的子樹都比父親大)，value是要維護的值，weight是随機生成的值。由于随機生成的堆使整棵treap變得平衡，是以treap是一種比較短小精悍的平衡樹的實作。

添加

首先我們知道各個節點的“優先級”是采用随機數的方法，那麼就存在一個問題，當我們插入一個節點後，優先級不滿足“堆定義"的時候我們該怎麼辦，前輩說此時需要旋轉，直到滿足堆定義為止。

删除

跟普通的二叉查找樹一樣，删除結點存在三種情況。

①：葉子結點

      跟普通查找樹一樣，直接釋放本節點即可。

②：單孩子結點

     跟普通查找樹一樣操作。

③：滿孩子結點

    其實在treap中删除滿孩子結點有兩種方式。

第一種：跟普通的二叉查找樹一樣，找到“右子樹”的最左結點，拷貝元素的值，但不拷貝元素的優先級，然後在右子樹中 删除結點即可。

第二種：将”結點下旋“，直到該節點不是”滿孩子的情況“，該賦null的賦null，該将孩子結點頂上的就頂上。

總結

treap樹在CURD中是期望的logN，由于我們加了”優先級“,是以會出現”連結清單“的情況幾乎不存在，但是他的Add和Remove相比嚴格的。

平衡二叉樹有更少的旋轉操作，可以說性能是在”普通二叉樹“和”平衡二叉樹“之間。

ps：

隻要無環無向聯通圖都叫樹，具體就是n個點n-1條無向邊連接配接且任意兩點聯通的一種拓撲結構，如果我們標明一個節點作為根，那麼這棵樹就是有根樹，周遊一遍就可以确定所有的父親-兒子的關系了，如果一棵有根樹的每一個結點至多有兩個兒子，那麼這棵樹稱為二叉樹。

如果一棵二叉樹的每一個節點都帶着一個值，且父親的值總是比兒子的值要大，我們稱這棵樹為大頂二叉堆，如果是父親比兒子都要小，那就是小頂二叉堆，統稱為二叉堆。

(其實一般都把二叉兩個字省略掉，畢竟通常說的堆都是二叉堆，然而堆不止二叉堆)。這一個良好的性質注定了堆可以用來當作優先隊列使用。

優先隊列支援以下操作

1.放一個元素進去

2.總是能取出一個最大的元素出來(大，小的規矩可以通過一個比較函數來定義)

顯然堆就是可以這麼做。

當然啦，之前說過堆不止二叉堆，還有更複雜的二項堆，斐波那契堆，配對堆等等。

是以，堆是一種特殊的樹。

參考：

https://www.zhihu.com/question/36134980/answer/66080662

http://www.cnblogs.com/huangxincheng/archive/2012/07/30/2614484.html