树堆

樹堆（英語：Treap），是有一個隨機附加域滿足堆的性質的二元搜尋樹，其結構相當於以隨機資料插入的二元搜尋樹。其基本操作的期望時間複雜度為。相對於其他的平衡二元搜尋樹，Treap的特點是實現簡單，且能基本實現隨機平衡的結構。

介紹

Treap=Tree+Heap。Treap本身是一棵二元搜尋樹，它的左子樹和右子樹也分別是一個Treap，和一般的二元搜尋樹不同的是，Treap紀錄一個額外的資料，就是優先級。Treap在以關鍵碼構成二元搜尋樹的同時，還滿足堆的性質。Treap維護堆性質的方法用到了旋轉，只需要兩種旋轉，編程複雜度比Splay要小一些。

插入

給節點隨機分配一個優先級，先和二元搜尋樹的插入一樣，先把要插入的點插入到一個葉子上，然後跟維護堆一樣，如果目前節點的優先級比根大就旋轉，如果目前節點是根的左兒子就右旋如果目前節點是根的右兒子就左旋。
由於旋轉是的，最多進行h次（h是樹的高度），插入的複雜度是的，在期望情況下，所以它的期望複雜度是。

刪除

因為Treap滿足堆性質，所以只需要把要刪除的節點旋轉到葉節點上，然後直接刪除就可以了。具體的方法就是每次找到優先級最大的兒子，向與其相反的方向旋轉，直到那個節點被旋轉到了葉節點，然後直接刪除。
刪除最多進行次旋轉，期望複雜度是。

尋找

和一般的二元搜尋樹一樣，但是由於Treap的隨機化結構，Treap中尋找的期望複雜度是。

演算法分析

二元搜尋樹有一個特性，就是每個子樹的形態在優先級唯一確定的情況下都是唯一的，不受其他因素影響，也就是說，左子樹的形態與樹中大於根節點的值無關，右子樹亦然。這是因為Treap滿足堆的性質，Treap的根節點是優先級最大的那個節點，考慮它的左子樹，樹根也是子樹裡面最大的一點，右子樹亦然。所以Treap相當於先把所有節點按照優先級排序，然後插入，實質上就相當於以隨機順序建立的二元搜尋樹，只不過它並不需要一次讀入所有資料，可以一個一個地插入。而當這個隨機順序確定的時候，這個樹是唯一的。因此在給定優先級的情況下，只要是用符合要求的操作，通過任何方式得出的Treap都是一樣的，所以不改變優先級的情況下，特殊的操作不會造成Treap結構的退化。而改變優先級可能會使Treap變得不夠隨機以致退化。
Treap的其它操作的期望複雜度同樣是。

Pascal

(*    Project: Amber Standard Sources Library [ASSL]    Author: Amber    Title: Treap    Category: Data Structure    Version: v1.0    Remark: XXXXXXXX    Tested Problems: N/A    Date: 2006-11-16 *)
 program ASSL_Treap(Input, Output);
 const
    Infinity = 65535;
 type
    TIndex = Longint;
    TKey = Longint;
    TPriority = Word;
    PTreapNode = ^TTreapNode;
    TTreapNode = record
        Left, Right: PTreapNode;
        Priority: TPriority;
        Key: TKey;
    end;
 var
    NullNode: PTreapNode;
 
 procedure Initalize;
 begin
    if NullNode = nil then
    begin
        New(NullNode);
        NullNode^.Left := NullNode;
        NullNode^.Right := NullNode;
        NullNode^.Priority := Infinity;
    end;
 end;
 
 function FindMax(T: PTreapNode): PTreapNode;
 begin
    if T <> NullNode then
        while T^.Right <> NullNode do
            T := T^.Right;
    Result := T;
 end;
 
 function FindMin(T: PTreapNode): PTreapNode;
 begin
    if T <> NullNode then
        while T^.Left <> NullNode do
            T := T^.Left;
    Result := T;
 end;
 
 function Find(T: PTreapNode; Key: TKey): PTreapNode;
 begin
    while T <> NullNode do
        if Key < T^.Key then
            T := T^.Left
        else if Key > T^.Key then
            T := T^.Right
        else
            Break;
    Result := T;
 end;
 
 function LeftRotate(T: PTreapNode): PTreapNode;
 begin
    Result := T^.Left;
    T^.Left := Result^.Right;
    Result^.Right := T;
 end;
 
 function RightRotate(T: PTreapNode): PTreapNode;
 begin
    Result := T^.Right;
    T^.Right := Result^.Left;
    Result^.Left := T;
 end;
 
 function InsertNode(Key: TKey; T: PTreapNode): PTreapNode;
 begin
    if T = NullNode then
    begin
        New(T);
        T^.Left := NullNode;
        T^.Right := NullNode;
        T^.Key := Key;
        T^.Priority := Random(65535);
    end
    else if Key < T^.Key then
    begin
        T^.Left := InsertNode(Key, T^.Left);
        if T^.Left^.Priority < T^.Priority then
            T := LeftRotate(T);
    end
    else if Key > T^.Key then
    begin
        T^.Right := InsertNode(Key, T^.Right);
        if T^.Right^.Priority < T^.Priority then
            T := RightRotate(T);
    end;
    Result := T;
 end;
 
 function DeleteNode(Key: TKey; T: PTreapNode): PTreapNode;
 begin
    if T <> NullNode then
        if Key < T^.Key then
            T^.Left := DeleteNode(Key, T^.Left)
        else if Key > T^.Key then
            T^.Right := DeleteNode(Key, T^.Right)
        else
        begin
            if T^.Left^.Priority < T^.Right^.Priority then
                T := LeftRotate(T)
            else
                T := RightRotate(T);
            if T <> NullNode then
                T := DeleteNode(Key, T)
            else //RightRotate
            begin
                Dispose(T^.Left);
                T^.Left := NullNode;
            end;
        end;
     Result := T;
 end;
 
 procedure Main;
 begin
     Initalize;
 end;
 begin
     Main;
 end.

C++

#include <iostream>#include <ctime>#include <cstdlib>#define MAX 100using namespace std;typedef struct{
int l,r,key,fix;} node;class treap{public:
node p[MAX];
int size,root;
treap()
{
srand(time(0));
size=-1;
root=-1;
}

void rot_l(int &x)
{
int y=p[x].r;
p[x].r=p[y].l;
p[y].l=x;
x=y;
}

void rot_r(int &x)
{
int y=p[x].l;
p[x].l=p[y].r;
p[y].r=x;
x=y;
}

void insert(int &k,int tkey)
{
if (k==-1)
{
k=++size;
p[k].l=p[k].r=-1;
p[k].key=tkey;
p[k].fix=rand();
}
else if (tkey<p[k].key)
{
insert(p[k].l,tkey);
if (p[ p[k].l ].fix>p[k].fix)
rot_r(k);
}
else
{
insert(p[k].r,tkey);
if (p[ p[k].r ].fix>p[k].fix)
rot_l(k);
}

}

void remove(int &k,int tkey)
{
if (k==-1) return;
if (tkey<p[k].key)
remove(p[k].l,tkey);
else if (tkey>p[k].key)
remove(p[k].r,tkey);
else
{
if (p[k].l==-1 && p[k].r==-1)
k=-1;
else if (p[k].l==-1)
k=p[k].r;
else if (p[k].r==-1)
k=p[k].l;
else if (p[ p[k].l ].fix < p[ p[k].r ].fix)
{
rot_l(k);
remove(p[k].l,tkey);
}
else
{
rot_r(k);
remove(p[k].r,tkey);
}
}
}

void print(int k)
{
if (k == -1) return ;
if (p[k].l!=-1)
print(p[k].l);
cout << p[k].key << " : " << p[k].fix << endl;
if (p[k].r!=-1)
print(p[k].r);
}};treap T;int main(void){

int i;
for (i = 3; i >= 1; i--)
T.insert(T.root,i);
T.print(T.root);
for (i = 3; i >= 1; i--)
{
cout << endl;
T.remove(T.root,i);
T.print(T.root);
}
return 0;}