数据结构——treap

bobpanda

treap是一种数据结构。首先treap是一个二叉搜索树，与二叉搜索树不同的是，treap的每一个节点都有一个随机值，这个随机值满足堆的一些性质。我们知道，如果输入数据是有序的，普通的二叉搜索树会退化成线性表，但是引入随机值以后，能够减少退化的几率，但是由于权值是随机的，仍然有一定可能不能达成平衡。treap与splay和avl树相比优点在于代码量更小，更容易理解，缺点在于有退化风险。以下是部分代码：

1. /*This is an implementation of a senior data structure called treap.
   
2. Treap is a binary search tree,so treap has all features of a binary search tree. The difference is that each node of treap has a random weight,so that treap also owns some heap features in terms of the random weight.
   
3. The random weight guarantees that the whole tree is almost balance, and prevents the tree from degenerating to linear structures. */
   
4. #include <iostream>
   
5. #include <stdlib.h>
   
6. using namespace std;
   
7. 
   
8. struct mynode
   
9. {
   
10.   mynode *ch[2];    //ch[0] means left child, and ch[1] means right child.
    
11.   int randweight;
    
12.   int value;
    
13.   int size;
    
14.   int cmp(int x) const
    
15.   {
    
16.     if (x==value) return 0;
    
17.     return x<value?0:1;
    
18.   }
    
19. 
    
20.   
    
21. };
    
22. 
    
23. mynode *tree=NULL;
    
24. 
    
25. /*the core part of treap,rotate. This function does a rotate operation like
    
26. AVL tree in order to maintain the balance of the tree. Many blogs on the internetuse two functions "zig" and "zag" to do the operation.However, using a simple variable "decision" could decide which side to rotate, combining two functions to one.Besides, "decision^1" means "1-decision." */
    
27. void rotate(mynode *&tree,int decision)
    
28. {
    
29.   mynode *k = tree->ch[decision^1];
    
30.   tree->ch[decision^1] = k->ch[decision];
    
31.   k->ch[decision] = tree;
    
32.   tree = k;
    
33. }
    
34. 
    
35. /*insert a certain number x.*/
    
36. void insert(mynode *&tree,int x)
    
37. {
    
38.   if (tree==NULL)
    
39.     {
    
40.       tree=new mynode();
    
41.       tree->ch[0]=NULL;
    
42.       tree->ch[1]=NULL;
    
43.       tree->value=x;
    
44.       tree->randweight=rand();
    
45.     }
    
46.   else
    
47.     {
    
48.       int decision = (x < tree->value ? 0 : 1);/*decide which side to insert,left,or right?*/
    
49.       insert(tree->ch[decision],x);
    
50.       if(tree->ch[decision]->randweight > tree->randweight)
    
51.         {
    
52.           rotate(tree,decision^1);
    
53.         }
    
54.    
    
55.     }
    
56. 
    
57. }
    
58. 
    
59. /*show the treap in mid order. Obviously the sequence is in a sorted order.*/
    
60. 
    
61. void showtree(mynode *tree)
    
62. {
    
63.   if (tree == NULL)
    
64.     return;
    
65.   showtree(tree->ch[0]);
    
66.   cout << tree->value << endl;
    
67.   showtree(tree->ch[1]);
    
68. }
    
69. 
    
70. 
    
71. /*judge whether a certain number x is in the treap or not.
    
72.   If x is in the treap,return 1.Otherwise,return 0.*/
    
73. int search (mynode *tree,int x)
    
74. {
    
75.   if (tree==NULL)
    
76.     return 0;
    
77.   if (tree->value==x)return 1;
    
78.   if (tree->value > x)
    
79.     return search(tree->ch[0],x);
    
80.   if(tree->value<x)
    
81.     return search(tree->ch[1],x);
    
82.   
    
83. }
    
84. /*find the pointer of a certain number x,if x is not in the treap,return NULL*/
    
85. mynode* BinaryTreeSearch(mynode* tree, int value)
    
86. {
    
87.   if(tree->value == value)
    
88.     {
    
89.       return tree;
    
90.     }
    
91.   else if(tree->value > value)
    
92.     {
    
93.       if(tree->ch[0] != NULL)
    
94.         {
    
95.           return  BinaryTreeSearch(tree->ch[0], value);
    
96.         }
    
97.       else{
    
98.         return NULL;
    
99.       }
    
100.     }else{
     
101.     if(tree->ch[1] != NULL)
     
102.       {
     
103.         return  BinaryTreeSearch(tree->ch[1], value);
     
104.       }else{
     
105.       return NULL;
     
106.     }
     
107.   }
     
108. }
     
109. 
     
110. 
     
111. int main()
     
112. {
     
113.   srand(time(NULL));
     
114.   int n,m;
     
115.   cin >> n;
     
116.   for (int i=1;i<=n;i++)
     
117.     {
     
118.       cin >> m;
     
119. 
     
120.       insert(tree,m);
     
121.     }
     
122. 
     
123.    showtree(tree);
     
124.   
     
125.   return 0;
     
126. }

复制代码