1. 概述

同splay tree一樣，treap也是一個(gè)平衡二叉樹(shù)，不過(guò)Treap會(huì)記錄一個(gè)額外的數(shù)據(jù)，即優(yōu)先級(jí)。Treap在以關(guān)鍵碼構(gòu)成二叉搜索樹(shù)的同時(shí)，還按優(yōu)先級(jí)來(lái)滿足堆的性質(zhì)。因而，Treap=tree+heap。這里需要注意的是，Treap并不是二叉堆，二叉堆必須是完全二叉樹(shù)，而Treap可以并不一定是。

2. Treap基本操作

為了使Treap 中的節(jié)點(diǎn)同時(shí)滿足BST性質(zhì)和最小堆性質(zhì)，不可避免地要對(duì)其結(jié)構(gòu)進(jìn)行調(diào)整，調(diào)整方式被稱為旋轉(zhuǎn)。在維護(hù)Treap 的過(guò)程中，只有兩種旋轉(zhuǎn)，分別是左旋轉(zhuǎn)(簡(jiǎn)稱左旋)和右旋轉(zhuǎn)(簡(jiǎn)稱右旋)。
左旋一個(gè)子樹(shù)，會(huì)把它的根節(jié)點(diǎn)旋轉(zhuǎn)到根的左子樹(shù)位置，同時(shí)根節(jié)點(diǎn)的右子節(jié)點(diǎn)成為子樹(shù)的根；右旋一個(gè)子樹(shù)，會(huì)把它的根節(jié)點(diǎn)旋轉(zhuǎn)到根的右子樹(shù)位置，同時(shí)根節(jié)點(diǎn)的左子節(jié)點(diǎn)成為子樹(shù)的根。

struct Treap_Node
 
{
 
 Treap_Node *left,*right; //節(jié)點(diǎn)的左右子樹(shù)的指針
 
 int value,fix; //節(jié)點(diǎn)的值和優(yōu)先級(jí)
 
};
 
void Treap_Left_Rotate(Treap_Node *&a) //左旋 節(jié)點(diǎn)指針一定要傳遞引用
 
{
 
 Treap_Node *b=a->right;
 
 a->right=b->left;
 
 b->left=a;
 
 a=b;
 
}
 
void Treap_Right_Rotate(Treap_Node *&a) //右旋 節(jié)點(diǎn)指針一定要傳遞引用
 
{
 
 Treap_Node *b=a->left;
 
 a->left=b->right;
 
 b->right=a;
 
 a=b;
 
}

3. Treap的操作

同其他樹(shù)形結(jié)構(gòu)一樣，treap的基本操作有：查找，插入，刪除等。

3.1    查找

同其他二叉樹(shù)一樣，treap的查找過(guò)程就是二分查找的過(guò)程，復(fù)雜度為O(lg n)。

3.2    插入

在Treap 中插入元素，與在BST 中插入方法相似。首先找到合適的插入位置，然后建立新的節(jié)點(diǎn)，存儲(chǔ)元素。但是要注意新的節(jié)點(diǎn)會(huì)有一個(gè)優(yōu)先級(jí)屬性，該值可能會(huì)破壞堆序，因此我們要根據(jù)需要進(jìn)行恰當(dāng)?shù)男D(zhuǎn)。具體方法如下：

1. 從根節(jié)點(diǎn)開(kāi)始插入；
2. 如果要插入的值小于等于當(dāng)前節(jié)點(diǎn)的值，在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中插入，插入后如果左子節(jié)點(diǎn)的優(yōu)先級(jí)小于當(dāng)前節(jié)點(diǎn)的優(yōu)先級(jí)，對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行右旋；
3. 如果要插入的值大于當(dāng)前節(jié)點(diǎn)的值，在當(dāng)前節(jié)點(diǎn)的右子樹(shù)中插入，插入后如果右子節(jié)點(diǎn)的優(yōu)先級(jí)小于當(dāng)前節(jié)點(diǎn)的優(yōu)先級(jí)，對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行左旋；
4. 如果當(dāng)前節(jié)點(diǎn)為空節(jié)點(diǎn)，在此建立新的節(jié)點(diǎn)，該節(jié)點(diǎn)的值為要插入的值，左右子樹(shù)為空，插入成功。

Treap_Node *root;
 
void Treap_Insert(Treap_Node *&P,int value) //節(jié)點(diǎn)指針一定要傳遞引用
 
{
 
 if (!P) //找到位置，建立節(jié)點(diǎn)
 
 {
 
  P=new Treap_Node;
 
  P->value=value;
 
  P->fix=rand();//生成隨機(jī)的修正值
 
 }
 
 else if (value <= P->value)
 
 {
 
  Treap_Insert(P->left,r);
 
  if (P->left->fix < P->fix)
 
   Treap_Right_Rotate(P);//左子節(jié)點(diǎn)修正值小于當(dāng)前節(jié)點(diǎn)修正值，右旋當(dāng)前節(jié)點(diǎn)
 
 }
 
 else
 
 {
 
  Treap_Insert(P->right,r);
 
  if (P->right->fix < P->fix)
 
   Treap_Left_Rotate(P);//右子節(jié)點(diǎn)修正值小于當(dāng)前節(jié)點(diǎn)修正值，左旋當(dāng)前節(jié)點(diǎn)
 
 }
 
}

3.3   刪除

與BST 一樣，在Treap 中刪除元素要考慮多種情況。我們可以按照在BST 中刪除元素同樣的方法來(lái)刪除Treap 中的元素，即用它的后繼(或前驅(qū))節(jié)點(diǎn)的值代替它，然后刪除它的后繼(或前驅(qū))節(jié)點(diǎn)。

上述方法期望時(shí)間復(fù)雜度為O(logN)，但是這種方法并沒(méi)有充分利用Treap 已有的隨機(jī)性質(zhì)，而是重新得隨機(jī)選取代替節(jié)點(diǎn)。我們給出一種更為通用的刪除方法，這種方法是基于旋轉(zhuǎn)調(diào)整的。首先要在Treap 樹(shù)中找到待刪除節(jié)點(diǎn)的位置，然后分情況討論：

情況一，該節(jié)點(diǎn)為葉節(jié)點(diǎn)或鏈節(jié)點(diǎn)，則該節(jié)點(diǎn)是可以直接刪除的節(jié)點(diǎn)。若該節(jié)點(diǎn)有非空子節(jié)點(diǎn)，用非空子節(jié)點(diǎn)代替該節(jié)點(diǎn)的，否則用空節(jié)點(diǎn)代替該節(jié)點(diǎn)，然后刪除該節(jié)點(diǎn)。

情況二，該節(jié)點(diǎn)有兩個(gè)非空子節(jié)點(diǎn)。我們的策略是通過(guò)旋轉(zhuǎn)，使該節(jié)點(diǎn)變?yōu)榭梢灾苯觿h除的節(jié)點(diǎn)。如果該節(jié)點(diǎn)的左子節(jié)點(diǎn)的優(yōu)先級(jí)小于右子節(jié)點(diǎn)的優(yōu)先級(jí)，右旋該節(jié)點(diǎn)，使該節(jié)點(diǎn)降為右子樹(shù)的根節(jié)點(diǎn)，然后訪問(wèn)右子樹(shù)的根節(jié)點(diǎn)，繼續(xù)討論；反之，左旋該節(jié)點(diǎn)，使該節(jié)點(diǎn)降為左子樹(shù)的根節(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)的根節(jié)點(diǎn)，這樣繼續(xù)下去，直到變成可以直接刪除的節(jié)點(diǎn)。

BST_Node *root;
 
void Treap_Delete(Treap_Node *&P,int *value) //節(jié)點(diǎn)指針要傳遞引用
 
{
 
 if (value==P->value) //找到要?jiǎng)h除的節(jié)點(diǎn) 對(duì)其刪除
 
 {
 
  if (!P->right || !P->left) //情況一，該節(jié)點(diǎn)可以直接被刪除
 
  {
 
   Treap_Node *t=P;
 
   if (!P->right)
 
    P=P->left; //用左子節(jié)點(diǎn)代替它
 
   else
 
    P=P->right; //用右子節(jié)點(diǎn)代替它
 
   delete t; //刪除該節(jié)點(diǎn)
 
  }
 
  else //情況二
 
  {
 
   if (P->left->fix < P->right->fix) //左子節(jié)點(diǎn)修正值較小，右旋
 
   {
 
    Treap_Right_Rotate(P);
 
    Treap_Delete(P->right,r);
 
   }
 
   else //左子節(jié)點(diǎn)修正值較小，左旋
 
   {
 
    Treap_Left_Rotate(P);
 
     Treap_Delete(P->left,r);
 
   }
 
  }
 
 }
 
 else if (value < P->value)
 
  Treap_Delete(P->left,r); //在左子樹(shù)查找要?jiǎng)h除的節(jié)點(diǎn)
 
 else
 
  Treap_Delete(P->right,r); //在右子樹(shù)查找要?jiǎng)h除的節(jié)點(diǎn)
 
}

4. Treap應(yīng)用
Treap可以解決splay tree可以解決的所有問(wèn)題，具體參見(jiàn)另一篇文章：《數(shù)據(jù)結(jié)構(gòu)之伸展樹(shù)詳解》

可以這樣定義結(jié)構(gòu)體：

struct Treap_Node
 
{
 
 Treap_Node *left,*right; //節(jié)點(diǎn)的左右子樹(shù)的指針
 
 int value,fix,weight,size; //節(jié)點(diǎn)的值，優(yōu)先級(jí)，重復(fù)計(jì)數(shù)（記錄相同節(jié)點(diǎn)個(gè)數(shù)，節(jié)省空間），子樹(shù)大小
 
 inline int lsize(){ return left ?left->size ?0; } //返回左子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
 
 inline int rsize(){ return right?right->size?0; } //返回右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
 
};

5. 總結(jié)

Treap 作為一種簡(jiǎn)潔高效的有序數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)科學(xué)和技術(shù)應(yīng)用中有著重要的地位。它可以用來(lái)實(shí)現(xiàn)集合、多重集合、字典等容器型數(shù)據(jù)結(jié)構(gòu)，也可以用來(lái)設(shè)計(jì)動(dòng)態(tài)統(tǒng)計(jì)數(shù)據(jù)結(jié)構(gòu)。

6. 參考資料

（1）Treap：http://www.nocow.cn/index.php/Treap
（2）隨機(jī)平衡二叉查找樹(shù)Treap 的分析與應(yīng)用：http://www.byvoid.com/blog/wp-content/uploads/2010/12/treap-analysis-and-application.pdf