treap树模板

 1 ///treap树模板
 2 typedef struct Node    ///节点的结构体
 3 {
 4     Node *l,*r;
 5     int val,pri;      ///节点的值和优先级
 6     int sz;           ///节点子树的节点数
 7     Node(int x)       ///初始化节点
 8     {
 9         l=r=NULL;
10         val=x;
11         pri=rand();
12         sz=1;
13     }
14 }Node;
15 Node *root;
16 
17 int Tsize(Node *T)  ///计算子树的叶子节点
18 {
19     if (T==NULL) return 0;
20     return T->sz;
21 }
22 Node *L_rotate(Node *T)    ///右节点的优先级大于当前节点的优先级，进行左旋转
23 {
24     Node *A=T->r;         ///A表示有节点
25     T->r=A->l;
26     A->l=T;
27     A->sz-T->sz;         ///交换后A变成当前节点，所以它的子树的节点数等于原来节点的节点数
28     T->sz=Tsize(T->l)+Tsize(T->r)+1;
29     return A;
30 }
31 Node *R_rotate(Node *T)   ///左节点的优先级大于当前节点的优先级，进行右旋转
32 {
33     Node *A=T->l;
34     T->l=A->r;
35     A->r=T;
36     A->sz=T->sz;
37     T->sz=Tsize(T->l)+Tsize(T->r)+1;
38     return A;
39 }
40 
41 void inser(Node *&T,int val) ///插入函数,和二叉排序树差不多
42 {
43     if (T==NULL)            
44     {
45         T=new Node(val);
46         return ;
47     }
48     if (T->val>=val)
49     {
50         inser(T->l,val);
51         if ((T->l->pri)<(T->pri)) T=R_rotate(T); ///优先级比较，并旋转
52     }
53     else
54     {
55         inser(T->r,val);
56         if ((T->r->pri)<(T->pri)) T=L_rotate(T);
57     }
58     T->sz=Tsize(T->l)+Tsize(T->r)+1;   
59 }
60 
61 void Delete(Node *&T,int val)        ///删除函数
62 {
63     if (T->val>val) Delete(T->l,val);
64     else if (T->val<val) Delete(T->r,val);
65     else
66     {
67         if (T->l==NULL&&T->r==NULL) T=NULL;   ///左右节点都为空
68         else if (T->r==NULL) T=T->l;          ///右节点为空
69         else if(T->l==NULL) T=T->r;           ///左节点为空
70         else                                  ///左右都不空
71         {
72             if (T->l->pri<T->r->pri)          ///左节点优先级小于右边
73             {                                 ///右旋转，并向右子树删除
74                 T=R_rotate(T);                ///应为有旋转后，要删除的节点到有子树去了
75                 Delete(T->r,val);
76             }
77             else
78             {
79                 T=L_rotate(T);
80                 Delete(T->l,val);
81             }
82         }
83     }
84     if (T!=NULL)
85     {
86         T->sz=Tsize(T->l)+Tsize(T->r)+1;
87     }
88 }
89 
90 int Find(Node *T,int k)                      ///查找第k小的树
91 {
92     int temp=Tsize(T->l)+1;                  ///temp小于等于T->val数的个数
93     if (temp==k) return T->val;
94     if (temp>k) return Find(T->l,k);
95     return Find(T->r,k-temp);
96 }