Treap学习总结

 

    最近在研究平衡树，这里是我的treap学习笔记。

 

    Treap是一种用来排序的数据结构，编写比较容易，时间复杂度也很好。

 

Treap = Tree + Heap

为了解决查找树退化的问题，在所学的数据结构里，能保证树的层数尽量少，分布尽量均匀，我们最先想到的就是完全二叉树了。而具有完全二叉树性质的数据结构很明显，堆就是其中之一，所以我们可以试想一想，如果在满足二叉查找树的前提下，同时又能满足堆的性质，是不是就可以避免这个树的退化呢？

当然，如果都以权值作为标准的话，很明显是不可能做到的，但是我们可以再给每个节点添加一个修正值，让这个修正值构成堆，而原始值满足BST，这样就解决了二叉查找树的平衡问题了。

由于是一个学习总结，就不在描述treap的工作原理了，直接上代码了。

 

1，数据结构定义

1 struct node2 {3     int l,r;4     int key,kind,fix;5 }a[MaxN]; //Treap

 

2，左旋/右旋操作

1 //左旋 2 void turn_left(int &x) 3 { 4     int y=a[x].r; 5  6     a[y].size=a[x].size; 7     a[x].size-=a[a[rc].r].size+1; 8      9     a[x].r=a[y].l;10     a[y].l=x;11     x=y;12 }13 //右旋14 void turn_right(int &x)15 {16     int y=a[x].l;17 18     a[y].size=a[x].size;19     a[x].size-=a[a[lc].l].size+1;20     21     a[x].l=a[y].r;22     a[y].r=x;23     x=y;24 }25 26 //其中的size域存放的是以当前节点为根的子树上的节点个数，用来查找第K大值

 

3，插入操作

1 //插入 2 void insert(int &k,int tkey) 3 { 4     if (k==-1) 5     { 6         k=++tot; 7         a[k].key=tkey; 8         a[k].size=1; 9         //memcpy(a[k].name,name,sizeof(name));10         a[k].fix=rand();11     }12     else13     if (tkey
     
      a[k].fix)18             turn_right(k);19     }20     else21     {22         insert(a[k].r,tkey);23         a[k].size++;24         if (a[ a[k].r ].fix>a[k].fix)25             turn_left(k);26     }27     28 }
     

 

4，删除操作

1 void Delete(int &k,int tkey) 2 { 3     int lc=a[k].l; int rc=a[k].r; 4      5     if (tkey==a[k].key) //找到要删除的节点 对其删除 6     { 7         if (lc==-1 || rc==-1) //情况一，该节点可以直接被删除 8         { 9             if (rc==-1) k=lc;        //用左子节点代替它10             else k=rc;        //用右子节点代替它11             flag=true;12         }13         else //情况二14         {15             if (a[lc].fix > a[rc].fix) //左子节点修正值较大，右旋16             {17                 turn_right(k);18                 Delete(a[k].r,tkey); //修正子树19                 if (flag) a[k].size--;20             }21             else  //左子节点修正值较小，左旋22             {23                 turn_left(k);24                 Delete(a[k].l,tkey);25                 if (flag) a[k].size--;26             }27         }28     }29     else 30         if (tkey < a[k].key) {31             Delete(a[k].l,tkey);  //在左子树查找要删除的节点32             if (flag) a[k].size--;33         }34     else {35         Delete(a[k].r,tkey); //在右子树查找要删除的节点36         if (flag) a[k].size--;37     }38 }

 

5，查找操作[代码是用来查找第K大数的]

1 int Search(int &now,int k) 2 { 3     int lc=a[now].l; int rc=a[now].r; 4     if (k < a[lc].size + 1)  //左子树中查找排名第k的元素 5         return Search(a[now].l,k); 6     else if (k > a[lc].size + 1) //在右子树中查找排名第k-(a[lc]size+1)的元素 7         return Search(a[now].r,k-(a[lc].size + 1)); 8     else 9         return a[now].key; //返回当前节点10 }

 

 

 

 

Treap的应用方面还是比较广的,最基本的应用就是查找元素排名和查找第K大值，所以可以用来动态的统计数据以及优化动态规划。