首页 > > 程序设计 > C/C++ >

伸展树（Splay树）的简要操作

2018-06-17 22:52:15来源：未知阅读 ()

　　伸展树（splay树），是二叉排序树的一种。【两个月之前写过，今天突然想写个博客。。。】

　　伸展树和一般的二叉排序树不同的是，在每次执行完插入、查询、删除等操作后，都会自动平衡这棵树。（说是自动，也就是多了一段代码，把这个节点提到根节点的位置上罢了）

　　伸展树的调整是基于两种旋转操作的【左旋右旋嘛】。

　　分别是这样的（对2号节点操作）：

　　（有点草率啊这个图）

　　对于这两个操作，只需要处理好指针为空的情况即可（我的splay树包含了father指针，可能比另一种写法更繁琐一些）

 1 void lec(nod x)
 2 {
 3     nod y=x->fa;
 4     y->rs=x->ls;
 5     if (x->ls!=NULL)
 6         x->ls->fa=y;
 7     x->ls=y;
 8     x->fa=y->fa;
 9     if (y->fa!=NULL)
10     {
11         if (y==y->fa->ls)
12             y->fa->ls=x;
13         else
14             y->fa->rs=x;
15     }
16     y->fa=x;
17 }
18 
19 void ric(nod x)
20 {
21     nod y=x->fa;
22     y->ls=x->rs;
23     if (x->rs!=NULL)
24         x->rs->fa=y;
25     x->rs=y;
26     x->fa=y->fa;
27     if (y->fa!=NULL)
28     {
29         if (y==y->fa->ls)
30             y->fa->ls=x;
31         else
32             y->fa->rs=x;
33     }
34     y->fa=x;
35 }

左旋右旋

　　这样的话，我们就可以怼出一个splay操作，每次把一个操作节点上移到根节点位置。

 1 void splay(nod x)
 2 {
 3     nod y;
 4     while (x->fa!=NULL)
 5     {
 6         y=x->fa;
 7         if (y->fa==NULL)
 8         {
 9             if (y->ls==x)
10                 ric(x);
11             else
12                 lec(x);
13             break;
14         }
15         if (x==y->ls)
16         {
17             if (y==y->fa->ls)
18                 ric(y),ric(x);
19             else
20                 ric(x),lec(x);
21         }
22         else
23         {
24             if (y==y->fa->ls)
25                 lec(x),ric(x);
26             else
27                 lec(y),lec(x);
28         }
29     }
30     s=x;
31 }