[那些你所不知道的鬼畜写法]平衡树学习笔记

treap: (Orz fhq 大神，我曾经以为我会了 treap ，就再也不会写 splay 了，然后我遇上了 lct )

 1 #include <cstdlib>
 2 const int sizeOfMemory=10000;
 3 template <class type> inline void swap(type & x, type & y) {type t=x; x=y; y=t;}
 4 
 5 namespace treap
 6 {
 7     struct node
 8     {
 9         int key, size;
10         short weight;
11         bool rev;
12         node * left, * right;
13         inline node():size(1), weight(0) {left=right=this;}
14         inline void maintain() {size=left->size+right->size+1;}
15         inline void pushdown() {if (rev) swap(left, right), left->rev^=1, right->rev^=1, rev=0;}
16     };
17     node * null=new node();
18     node memory[sizeOfMemory], * portOfMemory=memory;
19 
20     inline node * newnode(int key)
21     {
22         node * ret=portOfMemory++;
23         ret->key=key; ret->size=1;
24         ret->weight=rand();
25         ret->rev=0;
26         ret->left=ret->right=null;
27         return ret;
28     }
29     void splitBySize(node * t, int k, node *& l, node *& r)
30     {
31         if (t==null) l=r=null;
32         else
33         {
34             t->pushdown();
35             if (t->left->size<k)
36             {
37                 l=t;
38                 splitBySize(t->right, k-t->left->size-1, t->right, r);
39                 l->maintain();
40             }
41             else
42             {
43                 r=t;
44                 splitBySize(t->left, k, l, t->left);
45                 r->maintain();
46             }
47         }
48     }
49     void splitByKey(node * t, int k, node *& l, node *& r)
50     {
51         if (t==null) l=r=null;
52         else
53         {
54             t->pushdown();
55             if (t->key<k)
56             {
57                 l=t;
58                 splitByKey(t->right, k, t->right, r);
59                 l->maintain();
60             }
61             else
62             {
63                 r=t;
64                 splitByKey(t->left, k, l, t->left);
65                 r->maintain();
66             }
67         }
68     }
69     node * merge(node * l, node * r)
70     {
71         if (l==null) return r;
72         if (r==null) return l;
73         if (l->weight>r->weight)
74         {
75             l->pushdown();
76             l->right=merge(l->right, r);
77             l->maintain();
78             return l;
79         }
80         else
81         {
82             r->pushdown();
83             r->left=merge(l, r->left);
84             r->maintain();
85             return r;
86         }
87     }
88 }

本傻装B系列

splay: (我曾经以为我会了 treap ，就再也不会在 lct 外的地方写 splay 了，然后我遇上了自顶向下 splay )

等待完坑

AVL: ( fhq 大神说是为了解决人工实现 rope 时，treap 不能直接复制节点否则权重会痿掉的问题而搞出来的新产物，但 clj 大神似乎有更高明的做法)

等待完坑