树堆
 |
| 树堆 | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 类型 | 隨機二元搜索樹 | ||||||||||||||||||||
| 用大O符号表示的时间复杂度 | |||||||||||||||||||||
| |||||||||||||||||||||
樹堆（英語：Treap），是計算機科學中術語。是有一个随机附加域满足堆的性质的二叉搜索树，其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度为。相對於其他的平衡二叉搜索樹，Treap的特点是實現簡單，且能基本實現隨機平衡的結構。属于弱平衡树。
介绍
[编辑]Treap一词由Tree和Heap二词合成而来。其本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap为每个节点记录优先级。Treap在以关键码构成二叉搜索树的同时，其节点优先级还满足堆的性质。Treap维护堆性质的方法用到了旋转，且只需要进行两种旋转操作，因此编程复杂度较Splay要小一些。
插入
[编辑]给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样進行以下操作：
- 如果当前节点的优先级比父節點大就進行2. 或3. 的操作
- 如果当前节点是父節點的左子葉就右旋
- 如果当前节点是父節點的右子葉就左旋。
由于旋转是的，最多进行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 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的演示 （页面存档备份，存于互联网档案馆）
- Randomized Search Trees(pdf)，有对Treap和它的加权形式的详尽介绍以及复杂度的严格证明