數據構造之Treap詳解。本站提示廣大學習愛好者：（數據構造之Treap詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是數據構造之Treap詳解正文
1. 概述
同splay tree一樣，treap也是一個均衡二叉樹，不外Treap會記載一個額定的數據，即優先級。Treap在以症結碼組成二叉搜刮樹的同時，還按優先級來知足堆的性質。因此，Treap=tree+heap。這裡須要留意的是，Treap其實不是二叉堆，二叉堆必需是完整二叉樹，而Treap可以其實不必定是。
2. Treap根本操作
為了使Treap 中的節點同時知足BST性質和最小堆性質，弗成防止地要對其構造停止調劑，調劑方法被稱為扭轉。在保護Treap 的進程中，只要兩種扭轉，分離是左扭轉(簡稱左旋)和右扭轉(簡稱右旋)。
左旋一個子樹，會把它的根節點扭轉到根的左子樹地位，同時根節點的右子節點成為子樹的根；右旋一個子樹，會把它的根節點扭轉到根的右子樹地位，同時根節點的左子節點成為子樹的根。
struct Treap_Node
{
Treap_Node *left,*right; //節點的閣下子樹的指針
int value,fix; //節點的值和優先級
};
void Treap_Left_Rotate(Treap_Node *&a) //左旋 節點指針必定要傳遞援用
{
Treap_Node *b=a->right;
a->right=b->left;
b->left=a;
a=b;
}
void Treap_Right_Rotate(Treap_Node *&a) //右旋 節點指針必定要傳遞援用
{
Treap_Node *b=a->left;
a->left=b->right;
b->right=a;
a=b;
}
3. Treap的操作
同其他樹形構造一樣，treap的根本操作有：查找，拔出，刪除等。
3.1 查找
同其他二叉樹一樣，treap的查找進程就是二分查找的進程，龐雜度為O(lg n)。
3.2 拔出
在Treap 中拔出元素，與在BST 中拔出辦法類似。起首找到適合的拔出地位，然後樹立新的節點，存儲元素。然則要留意新的節點會有一個優先級屬性，該值能夠會損壞堆序，是以我們要依據須要停止適當的扭轉。詳細辦法以下：
1. 從根節點開端拔出；
2. 假如要拔出的值小於等於以後節點的值，在以後節點的左子樹中拔出，拔出後假如左子節點的優先級小於以後節點的優先級，對以後節點停止右旋；
3. 假如要拔出的值年夜於以後節點的值，在以後節點的右子樹中拔出，拔出後假如右子節點的優先級小於以後節點的優先級，對以後節點停止左旋；
4. 假如以後節點為空節點，在此樹立新的節點，該節點的值為要拔出的值，閣下子樹為空，拔出勝利。
Treap_Node *root;
void Treap_Insert(Treap_Node *&P,int value) //節點指針必定要傳遞援用
{
if (!P) //找到地位，樹立節點
{
P=new Treap_Node;
P->value=value;
P->fix=rand();//生成隨機的修改值
}
else if (value <= P->value)
{
Treap_Insert(P->left,r);
if (P->left->fix < P->fix)
Treap_Right_Rotate(P);//左子節點修改值小於以後節點修改值，右旋以後節點
}
else
{
Treap_Insert(P->right,r);
if (P->right->fix < P->fix)
Treap_Left_Rotate(P);//右子節點修改值小於以後節點修改值，左旋以後節點
}
}
3.3 刪除
與BST 一樣，在Treap 中刪除元素要斟酌多種情形。我們可以依照在BST 中刪除元素異樣的辦法來刪除Treap 中的元素，即用它的後繼(或先驅)節點的值取代它，然後刪除它的後繼(或先驅)節點。
上述辦法希冀時光龐雜度為O(logN)，然則這類辦法並沒有充足應用Treap 已有的隨機性質，而是從新得隨機拔取取代節點。我們給出一種更加通用的刪除辦法，這類辦法是基於扭轉調劑的。起首要在Treap 樹中找到待刪除節點的地位，然後分情形評論辯論：
情形一，該節點為葉節點或鏈節點，則該節點是可以直接刪除的節點。若該節點有非空子節點，用非空子節點取代該節點的，不然用空節點取代該節點，然後刪除該節點。
情形二，該節點有兩個非空子節點。我們的戰略是經由過程扭轉，使該節點變成可以直接刪除的節點。假如該節點的左子節點的優先級小於右子節點的優先級，右旋該節點，使該節點降為右子樹的根節點，然後拜訪右子樹的根節點，持續評論辯論；反之，左旋該節點，使該節點降為左子樹的根節點，然後拜訪左子樹的根節點，如許持續下去，直到釀成可以直接刪除的節點。
BST_Node *root;
void Treap_Delete(Treap_Node *&P,int *value) //節點指針要傳遞援用
{
if (value==P->value) //找到要刪除的節點 對其刪除
{
if (!P->right || !P->left) //情形一，該節點可以直接被刪除
{
Treap_Node *t=P;
if (!P->right)
P=P->left; //用左子節點取代它
else
P=P->right; //用右子節點取代它
delete t; //刪除該節點
}
else //情形二
{
if (P->left->fix < P->right->fix) //左子節點修改值較小，右旋
{
Treap_Right_Rotate(P);
Treap_Delete(P->right,r);
}
else //左子節點修改值較小，左旋
{
Treap_Left_Rotate(P);
Treap_Delete(P->left,r);
}
}
}
else if (value < P->value)
Treap_Delete(P->left,r); //在左子樹查找要刪除的節點
else
Treap_Delete(P->right,r); //在右子樹查找要刪除的節點
}
4. Treap運用
Treap可以處理splay tree可以處理的一切成績，詳細拜見另外一篇文章：《數據構造之舒展樹詳解》
可以如許界說構造體：
struct Treap_Node
{
Treap_Node *left,*right; //節點的閣下子樹的指針
int value,fix,weight,size; //節點的值，優先級，反復計數（記載雷同節點個數，節儉空間），子樹年夜小
inline int lsize(){ return left ?left->size ?0; } //前往左子樹的節點個數
inline int rsize(){ return right?right->size?0; } //前往右子樹的節點個數
};
5. 總結
Treap 作為一種簡練高效的有序數據構造，在盤算機迷信和技巧運用中有側重要的位置。它可以用來完成聚集、多重聚集、字典等容器型數據構造，也能夠用來設計靜態統計數據構造。
6. 參考材料
（1）Treap：http://www.nocow.cn/index.php/Treap
（2）隨機均衡二叉查找樹Treap 的剖析與運用：http://www.byvoid.com/blog/wp-content/uploads/2010/12/treap-analysis-and-application.pdf
