首页 > 代码库 > Splay伸展树学习笔记

Splay伸展树学习笔记

Splay伸展树

有篇Splay入门必看文章 —— CSDN链接

 

经典引文

 

空间效率:O(n)
时间效率:O(log n)插入、查找、删除
创造者:Daniel Sleator 和 Robert Tarjan
优点:每次查询会调整树的结构,使被查询频率高的条目更靠近树根。

Tree Rotation


技术分享
 
树的旋转是splay的基础,对于二叉查找树来说,树的旋转不破坏查找树的结构。
 

Splaying

 
Splaying是Splay Tree中的基本操作,为了让被查询的条目更接近树根,Splay Tree使用了树的旋转操作,同时保证二叉排序树的性质不变。
Splaying的操作受以下三种因素影响:
  • 节点x是父节点p的左孩子还是右孩子
  • 节点p是不是根节点,如果不是
  • 节点p是父节点g的左孩子还是右孩子
同时有三种基本操作:
 

Zig Step

技术分享

当p为根节点时,进行zip step操作。
当x是p的左孩子时,对x右旋;
当x是p的右孩子时,对x左旋。
 

Zig-Zig Step

技术分享
当p不是根节点,且x和p同为左孩子或右孩子时进行Zig-Zig操作。
当x和p同为左孩子时,依次将p和x右旋;
当x和p同为右孩子时,依次将p和x左旋。
 
 

Zig-Zag Step

技术分享
当p不是根节点,且x和p不同为左孩子或右孩子时,进行Zig-Zag操作。
当p为左孩子,x为右孩子时,将x左旋后再右旋。
当p为右孩子,x为左孩子时,将x右旋后再左旋。
 
 

应用

 
Splay Tree可以方便的解决一些区间问题,根据不同形状二叉树先序遍历结果不变的特性,可以将区间按顺序建二叉查找树。
每次自下而上的一套splay都可以将x移动到根节点的位置,利用这个特性,可以方便的利用Lazy的思想进行区间操作。
对于每个节点记录size,代表子树中节点的数目,这样就可以很方便地查找区间中的第k小或第k大元素。
对于一段要处理的区间[x, y],首先splay x-1到root,再splay y+1到root的右孩子,这时root的右孩子的左孩子对应子树就是整个区间。
这样,大部分区间问题都可以很方便的解决,操作同样也适用于一个或多个条目的添加或删除,和区间的移动。

 

自学笔记

 

今天开始自己动手写Splay。身边的小伙伴大多是用下标和数组来维系各个结点的联系,但是我还是一如既往的喜欢C++的指针(? ω ?)。

 

结点以一个struct结构体的形式存在。

struct node {    int value;    node *father;    node *son[2];        node (int v = 0, node *f = NULL) {        value = v;        father = f;        son[0] = NULL;        son[1] = NULL;    }};

其中,son[0]代表左儿子,son[1]代表右儿子。

 

用一个函数来判断子节点是父节点的哪个儿子

inline bool son(node *f, node *s) {    return f->son[1] == s;}

返回值就是son[]数组的下标,这个函数很方便。

 

最关键的是旋转操作,有别于常见的zig,zag旋转,我喜欢用一个函数实现其两者的功能,即rotate(x)代表将x旋转到其父节点的位置上。

inline void rotate(node *t) {    node *f = t->father;    node *g = f->father;    bool a = son(f, t), b = !a;    f->son[a] = t->son[b];    if (t->son[b] != NULL)        t->son[b]->father = f;    t->son[b] = f;    f->father = t;    t->father = g;    if (g != NULL)        g->son[son(g, f)] = t;    else        root = t;}

函数会自行判断x实在父节点的左儿子上还是右儿子上,并自动左旋或右旋。这里要注意改变祖父结点的儿子指针,以及结点的父亲指针,切忌马虎漏掉。同时还要事先做好特判,放止访问非法地址。这里用指针相较于用下标的一个好处就是,如果你不小心访问了NULL即空指针,也是下标党常用的0下标,指针写法一定会RE,而下标写法可能就不会崩溃,因而不易发现错误,导致一些较为复杂而智障的错误。

 

然后是核心函数——Splay函数,貌似也有人叫Spaly的样子,然而我并没有考证什么。Splay(x,y)用于将x结点旋转到y结点的某个儿子上。特别地,Splay(x,NIL)代表将x旋转到根节点的位置上。根节点的父亲一般是NIL或0。

inline void spaly(node *t, node *p) {    while (t->father != p) {        node *f = t->father;        node *g = f->father;        if (g == p)            rotate(t);        else {            if (son(g, f) ^ son(f, t))                rotate(t), rotate(t);            else                rotate(f), rotate(t);        }    }}

这里值得注意的是两种双旋。如果t(该节点),f(父亲节点),g(祖父节点)形成了一条单向的链,即[右→右]或[左→左]这样子,那么就先对父亲结点进行rotate操作,再对该节点进行rotate操作;否则就对该节点连续进行两次rotate操作。据称单旋无神犇,双旋O(logN),这句话我也没有考证,个人表示不想做什么太多的探究,毕竟Splay的复杂度本来就挺玄学的了,而且专门卡单旋Splay的题也没怎么听说过。对了,这个双旋操作和AVL的双旋是不是有那么几分相似啊,虽然还是不太一样的吧,好吧其实也不怎么像╮(╯-╰)╭。

 

接下来谈谈插入操作。插入操作就和普通的二叉搜索树类似,先找到合适的叶子结点,然后在空着的son[]上新建结点,把值放入。不同的是需要把新建的结点Splay到根节点位置,复杂度需要,不要问为什么。

inline void insert(int val) {    if (root == NULL)        root = new node(val, NULL);    for (node *t = root; t; t = t->son[val >= t->value]) {        if (t->value =http://www.mamicode.com/= val) { spaly(t, NULL); return; }        if (t->son[val >= t->value] == NULL)            t->son[val >= t->value] = new node(val, t);    }}

注意,这个插入函数实现的是非重集合。

 

与之对应的就是删除操作,相对的复杂一些。删除一个元素,需要先在树中找到这个结点,然后把这个结点Splay到根节点位置,开始分类讨论。如果这个结点没有左儿子(左子树),直接把右儿子放在根的位置上即可;否则的话就需要想方设法合并左右子树:在左子树种找到最靠右(最大)的结点,把它旋转到根节点的儿子上,此时它一定没有右儿子,因为根节点的左子树中不存在任何一个元素比它更大,那么把根节点的右子树接在这个结点的右儿子上即可。

inline void erase(int val) {    node *t = root;    for ( ; t; ) {        if (t->value =http://www.mamicode.com/= val)            break;        t = t->son[val > t->value];    }    if (t != NULL) {        spaly(t, NULL);        if (t->son[0] == NULL) {            root = t->son[1];            if (root != NULL)                root->father = NULL;        }        else {            node *p = t->son[0];            while (p->son[1] != NULL)                p = p->son[1];            spaly(p, t); root = p;            root->father = NULL;            p->son[1] = t->son[1];            if (p->son[1] != NULL)                p->son[1]->father = p;        }    }}

相较于insert()确实复杂了不少。

 

以上就是Splay的框架了,是Splay必不可少的部分,在此基础上可以加入许多新的功能。

 

@Author: YouSiki

Splay伸展树学习笔记