伸展树(Splay树)的简要操作

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

新老客户大回馈,云服务器低至5折

  伸展树(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 }
splay操作

  然后只要在每次插入、查找等操作后,加上一句splay(当前结点指针)就好了。。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:动态规划 导弹拦截

下一篇:tarjan算法详解