伸展树 Splay Tree

Splay Tree 是二叉查找树的一种，它与平衡二叉树、红黑树不同的是，Splay Tree从不强制地保持自身的平衡，每当查找到某个节点n的时候，在返回节点n的同时，Splay Tree会将节点n旋转到树根的位置，这样就使得Splay Tree天生有着一种类似缓存的能力，因为每次被查找到的节点都会被搬到树根的位置，所以当80%的情况下我们需要查找的元素都是某个固定的节点，或者是一部分特定的节点时，那么在很多时候，查找的效率会是O(1)的效率！当然如果查找的节点是很均匀地分布在不同的地方时，Splay Tree的性能就会变得很差了，但Splay Tree的期望的时间复杂度还是O（nlogn）的。

为了使访问的节点调到树根，必定要有像维护平衡二叉树那样的旋转操作，来维持二叉树节点间的偏序关系；与平衡二叉树类似，Splay有2种旋转操作（左旋zag、右旋zig）和4种旋转情况（LL，LR，RL，RR）；旋转操作要保持二叉查找树的性质，通过对访问点x的位置来判断旋转情况，对应的情况使用对应的旋转操作序列，就可以让x的所属层上升，循环对x操作就可以把x调到根节点的位置。

      /                               
      p                              x  
     /          Zig(x)             /   
    x  <>   ----------------->     <>  p  
   /                                 /   
  <> <>                              <> <>

       /                              
      x                              p 
     /          Zag(x)             /  
    p  <>   <-----------------     <>  x 
   /                                 /  
  <> <>                              <> <>

 1 struct node
 2 {
 3     int data;
 4     node *left,*right,*father;
 5     node(int d=0,node* a=NULL,node *b=NULL,node *c=NULL):data(d),left(a),right(b),father(c){}
 6 }*root;
 7 void zig(node *k)
 8 {
 9     node* fa=k->father;
10     fa->left=k->right;
11     if (k->right) k->right->father=fa;
12     k->right=fa;
13     k->father=fa->father;
14     fa->father=k;
15     if (!k->father) return;
16     if (k->father->data>k->data)
17         k->father->left=k;
18     else
19         k->father->right=k;
20 }
21 void zag(node *k)
22 {
23     node* fa=k->father;
24     fa->right=k->left;
25     if (k->left) k->left->father=fa;
26     k->left=fa;
27     k->father=fa->father;
28     fa->father=k;
29     if (!k->father) return;
30     if (k->father->data>k->data)
31         k->father->left=k;
32     else
33         k->father->right=k;
34 }
35 void splay(node *k,node *&root)
36 {
37     while (k->father)
38     {
39         node *fa=k->father;
40         if (fa->father==NULL)
41         {
42             if (k==fa->left) zig(k);
43                else zag(k);
44 
45         } else
46         {
47             node *gf=fa->father;
48             if (fa==gf->left && k==fa->left){zig(fa);zig(k);}
49             if (fa==gf->left && k==fa->right){zag(k);zig(k);}
50             if (fa==gf->right && k==fa->left){zig(k);zag(k);}
51             if (fa==gf->right && k==fa->right){zag(fa);zag(k);}
52         }
53     }
54     root=k;
55 }

Splay旋转调整代码

插入操作是先在二叉树中找到该插入的位置并插入节点，到这里和普通二叉查找树的操作是一样的，之后要对新插入的节点执行Splay()旋转调整操作。

 1 node* __insert(int data,node *&p)
 2 {
 3 
 4     if (p==NULL)
 5     {
 6         p=new node(data);
 7         return p;
 8     }
 9     if (data<p->data)
10     {
11         node *q=__insert(data,p->left);
12         p->left->father=p;
13         return q;
14     } else
15     {
16         if (data==p->data) return NULL; //Splay Tree中不允许出现相同的数据，否则在旋转是会出错，导致死循环
17         node *q=__insert(data,p->right);
18         p->right->father=p;
19         return q;
20     }
21 }
22 void insert(int data,node *&root)
23 {
24     node *t=__insert(data,root);
25     if (t)splay(t,root);
26 }

插入操作

查找操作也是和二叉树中的步骤类似，只是最后要对找到点执行Splay().

 1 node* __find(int data,node *root)
 2 {
 3     if (root==NULL) return NULL;
 4     if (data==root->data) return root;
 5     if (data<root->data) return __find(data,root->left);
 6     return __find(data,root->right);
 7 }
 8 node* find(int data,node *&root)
 9 {
10     node *q=__find(data,root);
11     if (q) splay(q,root);
12     return q;
13 }

查找操作

树的合并操作会比较麻烦些，先要用到求树的最大、最小操作，就是把树的最值提到树根，这样树根的左子树或是右子树就是一个空树，如果另一颗树最值操作后的树根满足条件，就可以直接连接上了。那如果不满足条件，就需要把另一树分为2棵树，其中一颗要满足条件，这样合并后还是两棵树，但有一棵树的大小会减少，这样循环下去最终就能和为一棵树了。
为了简单起见，下面我定义的合并函数只适用于同一根节点的两棵子树合并。

 1 node *findmax(node *&p) //最大操作
 2 {
 3     node *t=p;
 4     while (t->right) t=t->right;
 5     splay(t,p);
 6     return t;
 7 }
 8 node* join(node *a,node *b)  //a是左孩子  b是右孩子
 9 {
10      a->father=b->father=NULL;
11   if (!a || !b) return (node *)((int)a|(int)b);
12     node *t=findmax(a);
13     t->right=b;
14     b->father=t;
15     return t;
16 }

有条件的合并操作

要删除一个节点就把这个节点调到根节点，然后把左右孩子树合并，释放要删除节点就可以了。

 1 void remove(int data,node *&root)
 2 {
 3     node *q=find(data,root);
 4     if (q)
 5     {
 6         node *tem=root;
 7         root=join(root->left,root->right);
 8         delete tem;
 9     }
10 }

删除操作

可以见得Splay Tree 内存的访问次数是蛮高的