數(shù)據(jù)結構之Treap詳解
1. 概述
同splay tree一樣，treap也是一個平衡二叉樹，不過Treap會記錄一個額外的數(shù)據(jù)，即優(yōu)先級。Treap在以關鍵碼構成二叉搜索樹的同時，還按優(yōu)先級來滿足堆的性質。因而，Treap=tree+heap。這里需要注意的是，Treap并不是二叉堆，二叉堆必須是完全二叉樹，而Treap可以并不一定是。
2. Treap基本操作
為了使Treap 中的節(jié)點同時滿足BST性質和最小堆性質，不可避免地要對其結構進行調整，調整方式被稱為旋轉。在維護Treap 的過程中，只有兩種旋轉，分別是左旋轉(簡稱左旋)和右旋轉(簡稱右旋)。
左旋一個子樹，會把它的根節(jié)點旋轉到根的左子樹位置，同時根節(jié)點的右子節(jié)點成為子樹的根；右旋一個子樹，會把它的根節(jié)點旋轉到根的右子樹位置，同時根節(jié)點的左子節(jié)點成為子樹的根。
struct Treap_Node
{
Treap_Node *left,*right; //節(jié)點的左右子樹的指針
int value,fix; //節(jié)點的值和優(yōu)先級
};
void Treap_Left_Rotate(Treap_Node *&a) //左旋 節(jié)點指針一定要傳遞引用
{
Treap_Node *b=a->right;
a->right=b->left;
b->left=a;
a=b;
}
void Treap_Right_Rotate(Treap_Node *&a) //右旋 節(jié)點指針一定要傳遞引用
{
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 中插入方法相似。首先找到合適的插入位置，然后建立新的節(jié)點，存儲元素。但是要注意新的節(jié)點會有一個優(yōu)先級屬性，該值可能會破壞堆序，因此我們要根據(jù)需要進行恰當?shù)男D。具體方法如下：
1. 從根節(jié)點開始插入；
2. 如果要插入的值小于等于當前節(jié)點的值，在當前節(jié)點的左子樹中插入，插入后如果左子節(jié)點的優(yōu)先級小于當前節(jié)點的優(yōu)先級，對當前節(jié)點進行右旋；
3. 如果要插入的值大于當前節(jié)點的值，在當前節(jié)點的右子樹中插入，插入后如果右子節(jié)點的優(yōu)先級小于當前節(jié)點的優(yōu)先級，對當前節(jié)點進行左旋；
4. 如果當前節(jié)點為空節(jié)點，在此建立新的節(jié)點，該節(jié)點的值為要插入的值，左右子樹為空，插入成功。
Treap_Node *root;
void Treap_Insert(Treap_Node *&P,int value) //節(jié)點指針一定要傳遞引用
{
if (!P) //找到位置，建立節(jié)點
{
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);//左子節(jié)點修正值小于當前節(jié)點修正值，右旋當前節(jié)點
}
else
{
Treap_Insert(P->right,r);
if (P->right->fix < P->fix)
Treap_Left_Rotate(P);//右子節(jié)點修正值小于當前節(jié)點修正值，左旋當前節(jié)點
}
}
3.3 刪除
與BST 一樣，在Treap 中刪除元素要考慮多種情況。我們可以按照在BST 中刪除元素同樣的方法來刪除Treap 中的元素，即用它的后繼(或前驅)節(jié)點的值代替它，然后刪除它的后繼(或前驅)節(jié)點。
上述方法期望時間復雜度為O(logN)，但是這種方法并沒有充分利用Treap 已有的隨機性質，而是重新得隨機選取代替節(jié)點。我們給出一種更為通用的刪除方法，這種方法是基于旋轉調整的。首先要在Treap 樹中找到待刪除節(jié)點的位置，然后分情況討論：
情況一，該節(jié)點為葉節(jié)點或鏈節(jié)點，則該節(jié)點是可以直接刪除的節(jié)點。若該節(jié)點有非空子節(jié)點，用非空子節(jié)點代替該節(jié)點的，否則用空節(jié)點代替該節(jié)點，然后刪除該節(jié)點。
情況二，該節(jié)點有兩個非空子節(jié)點。我們的策略是通過旋轉，使該節(jié)點變?yōu)榭梢灾苯觿h除的節(jié)點。如果該節(jié)點的左子節(jié)點的優(yōu)先級小于右子節(jié)點的優(yōu)先級，右旋該節(jié)點，使該節(jié)點降為右子樹的根節(jié)點，然后訪問右子樹的根節(jié)點，繼續(xù)討論；反之，左旋該節(jié)點，使該節(jié)點降為左子樹的根節(jié)點，然后訪問左子樹的根節(jié)點，這樣繼續(xù)下去，直到變成可以直接刪除的節(jié)點。
BST_Node *root;
void Treap_Delete(Treap_Node *&P,int *value) //節(jié)點指針要傳遞引用
{
if (value==P->value) //找到要刪除的節(jié)點 對其刪除
{
if (!P->right || !P->left) //情況一，該節(jié)點可以直接被刪除
{
Treap_Node *t=P;
if (!P->right)
P=P->left; //用左子節(jié)點代替它
else
P=P->right; //用右子節(jié)點代替它
delete t; //刪除該節(jié)點
}
else //情況二
{
if (P->left->fix < P->right->fix) //左子節(jié)點修正值較小，右旋
{
Treap_Right_Rotate(P);
Treap_Delete(P->right,r);
}
else //左子節(jié)點修正值較小，左旋
{
Treap_Left_Rotate(P);
Treap_Delete(P->left,r);
}
}
}
else if (value < P->value)
Treap_Delete(P->left,r); //在左子樹查找要刪除的節(jié)點
else
Treap_Delete(P->right,r); //在右子樹查找要刪除的節(jié)點
}
4. Treap應用
Treap可以解決splay tree可以解決的所有問題，具體參見另一篇文章：《數(shù)據(jù)結構之伸展樹詳解》
可以這樣定義結構體：
struct Treap_Node
{
Treap_Node *left,*right; //節(jié)點的左右子樹的指針
int value,fix,weight,size; //節(jié)點的值，優(yōu)先級，重復計數(shù)（記錄相同節(jié)點個數(shù)，節(jié)省空間），子樹大小
inline int lsize(){ return left ?left->size ?0; } //返回左子樹的節(jié)點個數(shù)
inline int rsize(){ return right?right->size?0; } //返回右子樹的節(jié)點個數(shù)
};
5. 總結
Treap 作為一種簡潔高效的有序數(shù)據(jù)結構，在計算機科學和技術應用中有著重要的地位。它可以用來實現(xiàn)集合、多重集合、字典等容器型數(shù)據(jù)結構，也可以用來設計動態(tài)統(tǒng)計數(shù)據(jù)結構。
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
相關文章
這篇文章主要為大家詳細介紹了QDialog中exec與open的區(qū)別，文中的示例代碼講解詳細，對我們學習Qt有一定的幫助，需要的可以參考一下2023-03-03
C語言中的const和C++中的const是有區(qū)別的，而且在使用VS編譯測試的時候，如果是C的話，請一定要建立一個后綴為C的文件，不要是CPP的文件。因為，兩個編譯器會有差別的。下面通過本文給大家分享C語言中的const和free用法，感興趣的朋友一起看看吧2017-04-04
這篇文章主要介紹了C語言實現(xiàn)字符串操作函數(shù)的實例的相關資料,開發(fā)程序的時候經(jīng)常使用到一些字符串函數(shù)，例如求字符串長度，拷貝字符串……，需要的朋友可以參考下2021-09-09
這個命令是我查看Linux/Unix最喜愛的命令，一個是Linux/Unix都支持，二是相比top，我可以看到整個機器的CPU,內(nèi)存,IO的使用情況，而不是單單看到各個進程的CPU使用率和內(nèi)存使用率(使用場景不一樣)2013-09-09
C++11 線程同步接口std::condition_variable和std::future的簡單使用示例詳
本文介紹了std::condition_variable和std::future在C++中的應用,用于線程間的同步和異步執(zhí)行,通過示例代碼,展示了如何使用std::condition_variable的wait和notify接口進行線程間同步2024-09-09
const定義的全局數(shù)據(jù)變量，其基本作用和define相同，但又在define的基礎上增加了好多功能2013-10-10
C語言中運算符和表達式數(shù)量之多， 在高級語言中是少見的。正是豐富的運算符和表達式使C語言功能十分完善。 這也是C語言的主要特點之一。今天我們來看看加法運算2017-10-10
這篇文章主要介紹了C語言格式化輸出函數(shù)printf詳解，printf函數(shù)中用到的格式字符與printf函數(shù)中用到的格式修飾符，感興趣的小伙伴可以借鑒一下2023-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)三子棋游戲，棋盤可變，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要介紹了C語言冒泡排序法的實現(xiàn)（升序排序法），文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-07-07