树堆

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

树堆
类型	隨機二元搜索樹
用大O符号表示的时间复杂度
算法 平均 最差 空间 ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ 搜索 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 插入 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 删除 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$

三層的樹堆

介绍

Treap一词由Tree和Heap二词合成而来。其本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap为每个节点记录优先级。Treap在以关键码构成二叉搜索树的同时，其节点优先级还满足堆的性质。Treap维护堆性质的方法用到了旋转，且只需要进行两种旋转操作，因此编程复杂度较Splay要小一些。

插入

给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样進行以下操作：

1. 如果当前节点的优先级比父節點大就進行2. 或3. 的操作
2. 如果当前节点是父節點的左子葉就右旋
3. 如果当前节点是父節點的右子葉就左旋。

由于旋转是${\displaystyle O(1)}$ 的，最多进行h次（h是树的高度），插入的复杂度是${\displaystyle O(h)}$ 的，在期望情况下${\displaystyle h=O(\log {n})}$ ，所以它的期望复杂度是${\displaystyle O(\log {n})}$ 。

删除

因为Treap满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的子葉，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。

删除最多进行${\displaystyle O(h)}$ 次旋转，期望复杂度是${\displaystyle O(\log {n})}$ 。

查找

和一般的二叉搜索树一样，但是由于Treap的随机化结构，Treap中查找的期望复杂度是${\displaystyle O(\log {n})}$ 。

算法分析

二叉搜索树有一个特性，就是每个子树的形态在优先级唯一确定的情况下都是唯一的，不受其他因素影响，也就是说，左子树的形态与树中大于根节点的值无关，右子树亦然。这是因为Treap满足堆的性质，Treap的根节点是优先级最大的那个节点，考虑它的左子树，树根也是子树里面最大的一点，右子树亦然。所以Treap相当于先把所有节点按照优先级排序，然后插入，实质上就相当于以随机顺序建立的二叉搜索树，只不过它并不需要一次读入所有数据，可以一个一个地插入。而当这个随机顺序确定的时候，这个树是唯一的。因此在给定优先级的情况下，只要是用符合要求的操作，通过任何方式得出的Treap都是一样的，所以不改变优先级的情况下，特殊的操作不会造成Treap结构的退化。而改变优先级可能会使Treap变得不够随机以致退化。

Treap的其它操作的期望复杂度同样是${\displaystyle 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 (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; } 

与其他结构的比较

• AVL树
• 伸展树（Splay Tree）
• 线段树
• 红黑树
• Size Balanced Tree

外部链接

• 一个Treap的演示 （页面存档备份，存于互联网档案馆）

• ，有对Treap和它的加权形式的详尽介绍以及复杂度的严格证明