# 树堆

Treap，是有一个随机附加域满足的性质的二叉搜索树，其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度$O(\log{n})$。相對於其他的平衡二叉搜索樹，Treap的特点是實現簡單，且能基本實現隨機平衡的結構。

## 介绍

Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉搜索树的同时，还满足的性质。Treap维护堆性质的方法用到了旋转，只需要两种旋转，编程复杂度比Splay要小一些。

## 算法分析

Treap的其它操作的期望复杂度同样是$O(\log{n})$

## 参考程序

### 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 100

using 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 (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;
}
```