`
阅读更多

伸展树(Splay Tree)尽收眼底

 

 

本文内容框架:

§1 伸展树定义

§2 伸展树自底向上伸展

  §3 伸展树自顶向下伸展

§4 伸展树基本操作,实现以及应用

§5 小结

 

 

 

§1 伸展树定义

 

伸展树的定义

假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

伸展树并并不利用任何明确的规则来保证它的平衡,而是在每次访问之后,利用一种称为伸展操作将当前访问的结点移动到根,来维持查找树的平和。在插入,删除,甚至查找过程中,在到达的最底部的结点X上执行伸展操作。

为了将当前被访问节点旋转到树根,我们通常将节点自底向上旋转,直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系(指中序遍历结果是全序的)情况下,所有基本操作的平摊复杂度仍为O(log n)。

伸展树根据伸展的方式不同分为:自底向上伸展和自顶向下伸展,下面分别介绍。

 

 

§2 伸展树自底向上伸展  

 

自底向上伸展树

伸展树主要有三种旋转操作,分别为单旋转,一字形旋转和之字形旋转。为了便于解释,假设当前被访问节点为X,X的父亲节点为Y(如果X的父亲节点存在),X的祖父节点为Z(如果X的祖父节点存在)。

(1) 单旋转

节点X的父节点Y是根节点。这时,如果X是Y的左孩子,我们进行一次右旋操作;如果X 是Y 的右孩子,则我们进行一次左旋操作。经过旋转,X成为二叉查找树T的根节点,调整结束。

注:这张图有误,单旋之后应该A和B应该对调。

 (2) 一字型旋转

节点X 的父节点Y不是根节点,Y 的父节点为Z,且X与Y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时,我们进行一次左左旋转操作或者右右旋转操作。

(3) 之字形旋转

节点X的父节点Y不是根节点,Y的父节点为Z,X与Y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时,我们进行一次左右旋转操作或者右左旋转操作。

 


 

 

§3 伸展树自顶向下伸展

 

自顶向下伸展树

 

自顶向下伸展操作将伸展树分为三部分: 

   左树:包含所有已经知道比待查节点 X小的节点。 

   右树:包含所有已经知道比待查节点 X大的节点。 

   中树:包含所有其它节点。 

在中树自根向下进行节点查找(每次向下比较两个节点),根据查找情况将中树中的节 点移动(此处的移动是指将节点和中树的连接断开,而将节点连接到左或右树的适当位置。)到左树或右树(如有必要则会先对中树进行旋转再进行节点移动)。 

初始状态时,左树和右树都为空,而中树为整个原伸展树。随着查找的进行,左树和右 

树会因节点的逐渐移入变大,中树会因节点的逐渐移出变小。最后查找结束(找到或遇到空 

节点)时组合左中右树并是伸展树自顶向下伸展方法的最终结果。 

 

有四种情况: 

1,孩子即为要查找的点,只需要一次连接操作即可. 

 

2,孙子为要查找的点,且左右孩子一致.需要首先旋转父亲和祖父节点,然后连接操作. 

 

3,孙子为要查找的点,且左右孩子不一致.需要两次连接操作. 

 

4,合并 

 

 

 

 

§4 伸展树基本操作,实现以及应用

 

 

伸展树基本操作

1、插入:

    当一个节点插入时,伸展操作将执行。因此,新插入的节点在根上。

2、查找:

    如果查找成功(找到),那么由于伸展操作,被查找的节点成为树的新根。

如果查找失败(没有),那么在查找遇到NULL之前的那个节点成为新的根。也就是,如果查找的节点在树中,那么,此时根上的节点就是距离这个节点最近的节点。

3、查找最大最小:

        查找之后执行伸展。

4、删除最大最小:

a)删除最小:

     首先执行查找最小的操作。

这时,要删除的节点就在根上。根据二叉查找树的特点,根没有左子节点。

使用根的右子结点作为新的根,删除旧的包含最小值的根。

b)删除最大:

首先执行查找最大的操作。

删除根,并把被删除的根的左子结点作为新的根。

5、删除:

        将要删除的节点移至根。

        删除根,剩下两个子树L(左子树)和R(右子树)。

        使用DeleteMax查找L的最大节点,此时,L的根没有右子树。

        使R成为L的根的右子树。

 

伸展树的实现

 

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node 
{
        int data;
        struct node *parent;
        struct node *left;
        struct node *right;
};
int data_print(struct node *x);
struct node *rightrotation(struct node *p,struct node *root);
struct node *leftrotation(struct node *p,struct node *root);
void splay (struct node *x, struct node *root);
struct node *insert(struct node *p,int value);
struct node *inorder(struct node *p);
struct node *delete(struct node *p,int value);
struct node *successor(struct node *x);
struct node *lookup(struct node *p,int value);
 
void splay (struct node *x, struct node *root)
{
        struct node *p,*g;
        /*check if node x is the root node*/
        if(x==root)
                return;
        /*Performs Zig step*/
        else if(x->parent==root)
        {
                if(x==x->parent->left)
                        root=rightrotation(root,root);
                else
                        root=leftrotation(root,root);
        }
        else
        {
                p=x->parent; /*now points to parent of x*/
                g=p->parent; /*now points to parent of x's parent*/
                /*Performs the Zig-zig step when x is left and x's parent is left*/
                if(x==p->left&&p==g->left)
                {
                        root=rightrotation(g,root);
                        root=rightrotation(p,root);
                }
                /*Performs the Zig-zig step when x is right and x's parent is right*/
                else if(x==p->right&&p==g->right)
                {
                        root=leftrotation(g,root);
                        root=leftrotation(p,root);
                }
                /*Performs the Zig-zag step when x's is right and x's parent is left*/
                else if(x==p->right&&p==g->left)
                {
                        root=leftrotation(p,root);
                        root=rightrotation(g,root);
                }
                /*Performs the Zig-zag step when x's is left and x's parent is right*/
                else if(x==p->left&&p==g->right)
                {
                        root=rightrotation(p,root);
                        root=leftrotation(g,root);
                }
                splay(x, root);
        }
}
struct node *rightrotation(struct node *p,struct node *root)
{
        struct node *x;
        x = p->left;
        p->left = x->right;
        if (x->right!=NULL) x->right->parent = p;
        x->right = p;
        if (p->parent!=NULL)
                if(p==p->parent->right) p->parent->right=x;
                else
                         p->parent->left=x;
        x->parent = p->parent;
        p->parent = x;
        if (p==root)
                return x;
        else 
                return root;
}
struct node *leftrotation(struct node *p,struct node *root)
{
        struct node *x;
        x = p->right;
        p->right = x->left;
        if (x->left!=NULL) x->left->parent = p;
        x->left = p;
        if (p->parent!=NULL)
                if (p==p->parent->left) p->parent->left=x;
                else
                         p->parent->right=x;
        x->parent = p->parent;
        p->parent = x;
        if(p==root) 
                return x;
        else
                return root;
}
struct node *insert(struct node *p,int value)
{
        struct node *temp1,*temp2,*par,*x;
        if(p == NULL)
        {
                p=(struct node *)malloc(sizeof(struct node));
                if(p != NULL)
                {
                        p->data = value;
                        p->parent = NULL;
                        p->left = NULL;
                        p->right = NULL;
                }
                else
                {
                        printf("No memory is allocated\n");
                        exit(0);
                }
                return(p);
        } //the case 2 says that we must splay newly inserted node to root
        else
        {
                        temp2 = p;
                        while(temp2 != NULL)
                        {
                                temp1 = temp2;
                                if(temp2->data > value)
                                        temp2 = temp2->left;
                                else if(temp2->data < value)
                                        temp2 = temp2->right;
                                else
                                        if(temp2->data == value)
                                                return temp2;
                        }
                        if(temp1->data > value)
                        {
                                par = temp1;//temp1 having the parent address,so that's it 
                                temp1->left = (struct node *)malloc(sizeof(struct node));
                                temp1= temp1->left;
                                if(temp1 != NULL)
                                {
                                        temp1->data = value;
                                        temp1->parent = par;//store the parent address.
                                        temp1->left = NULL;
                                        temp1->right = NULL;
                                }
                                else
                                {
                                        printf("No memory is allocated\n");
                                        exit(0);
                                }
                        }
                        else
                        {
                                par = temp1;//temp1 having the parent node address.
                                temp1->right = (struct node *)malloc(sizeof(struct node));
                                temp1 = temp1->right;
                                if(temp1 != NULL)
                                {
                                        temp1->data = value;
                                        temp1->parent = par;//store the parent address
                                        temp1->left = NULL;
                                        temp1->right = NULL;
                                }
                                else
                                {
                                        printf("No memory is allocated\n");
                                        exit(0);
                                }
                        }
        }
        splay(temp1,p);//temp1 will be new root after splaying
        return (temp1);
}
struct node *inorder(struct node *p)
{
        if(p != NULL)
        {
                inorder(p->left);
                printf("CURRENT %d\t",p->data);
                printf("LEFT %d\t",data_print(p->left));
                printf("PARENT %d\t",data_print(p->parent));
                printf("RIGHT %d\t\n",data_print(p->right));
                inorder(p->right);
        }
}
struct node *delete(struct node *p,int value)
{
        struct node *x,*y,*p1;
        struct node *root;
        struct node *s;
        root = p;
        x = lookup(p,value);
        if(x->data == value)
        {       //if the deleted element is leaf
                if((x->left == NULL) && (x->right == NULL))
                {
                        y = x->parent;
                        if(x ==(x->parent->right)) 
                                y->right = NULL;
                        else 
                                y->left = NULL;
                        free(x);
                }
                //if deleted element having left child only
                else if((x->left != NULL) &&(x->right == NULL))
                {
                        if(x == (x->parent->left))
                        {
                                y = x->parent;
                                x->left->parent = y;
                                y->left = x->left;
                                free(x);
                        }
                        else
                        {
                                y = x->parent;
                                x->left->parent = y;
                                y->right = x->left;
                                free(x);
                        }
                }
                //if deleted element having right child only
                else if((x->left == NULL) && (x->right != NULL))
                {
                        if(x == (x->parent->left))
                        {
                                y = x->parent;
                                x->right->parent = y;
                                y->left = x->right;
                                free(x);
                        }
                        else
                        {
                                y = x->parent;
                                x->right->parent = y;
                                y->right = x->right;
                                free(x);
                        }
                }
                //if the deleted element having two children
                else if((x->left != NULL) && (x->right != NULL))
                {
                        if(x == (x->parent->left))
                        {
                                s = successor(x);
                                if(s != x->right)
                                {
                                        y = s->parent;
                                        if(s->right != NULL)
                                        {
                                                s->right->parent = y;
                                                y->left = s->right;
                                        }
                                        else y->left = NULL;
                                        s->parent = x->parent;
                                        x->right->parent = s;
                                        x->left->parent = s;
                                        s->right = x->right;
                                        s->left = x->left;
                                        x->parent->left = s;
                                }
                                else
                                {
                                        y = s;
                                        s->parent = x->parent;
                                        x->left->parent = s;
                                        s->left = x->left;
                                        x->parent->left = s;
                                }
                                free(x);
                        }
                        else if(x == (x->parent->right))
                        {
                                s = successor(x);
                                if(s != x->right)
                                {
                                        y = s->parent;
                                        if(s->right != NULL)
                                        {
                                                s->right->parent = y;
                                                y->left = s->right;
                                        }
                                        else y->left = NULL;
                                        s->parent = x->parent;
                                        x->right->parent = s;
                                        x->left->parent = s;
                                        s->right = x->right;
                                        s->left = x->left;
                                        x->parent->right = s;
                                }
                                else
                                {
                                        y = s;
                                        s->parent = x->parent;
                                        x->left->parent = s;
                                        s->left = x->left;
                                        x->parent->right = s;
                                }
                                free(x);
                        }
 
                }
                splay(y,root);
        }
        else
        {
                splay(x,root);
        }
}
struct node *successor(struct node *x)
{
        struct node *temp,*temp2;
        temp=temp2=x->right;
        while(temp != NULL)
        {
                temp2 = temp;
                temp = temp->left;
        }
        return temp2;
}
//p is a root element of the tree
struct node *lookup(struct node *p,int value)
{
        struct node *temp1,*temp2;
        if(p != NULL)
        {
                temp1 = p;
                while(temp1 != NULL)
                {
                        temp2 = temp1;
                        if(temp1->data > value)
                                temp1 = temp1->left;
                        else if(temp1->data < value)
                                temp1 = temp1->right;
                        else
                                        return temp1;
                }
                return temp2;
        }
        else
        {
                printf("NO element in the tree\n");
                exit(0);
        }
}
struct node *search(struct node *p,int value)
{
        struct node *x,*root;
        root = p;
        x = lookup(p,value);
        if(x->data == value)
        {
                printf("Inside search if\n");
                splay(x,root);
        }
        else
        {
                printf("Inside search else\n");
                splay(x,root);
        }
}
main()
{
        struct node *root;//the root element
        struct node *x;//x is which element will come to root.
        int i;
        root = NULL;
        int choice = 0;
        int ele;
        while(1)
        {
                printf("\n\n 1.Insert");
                printf("\n\n 2.Delete");
                printf("\n\n 3.Search");
                printf("\n\n 4.Display\n");
                printf("\n\n Enter your choice:");
                scanf("%d",&choice);
                if(choice==5)
                        exit(0);
                switch(choice)
                {
                        case 1:
                                printf("\n\n Enter the element to be inserted:");
                                scanf("%d",&ele);
                                x = insert(root,ele);
                                if(root != NULL)
                                {
                                        splay(x,root);
                                }
                                root = x;
                                break;
                        case 2:
                                if(root == NULL)
                                {
                                        printf("\n Empty tree...");
                                        continue;
                                }
                                printf("\n\n Enter the element to be delete:");
                                scanf("%d",&ele);
                                root = delete(root,ele);
                                break;
                        case 3:
                                printf("Enter the element to be search\n");
                                scanf("%d",&ele);
                                x = lookup(root,ele);
                                        splay(x,root);
                                root = x;
                                break;
                        case 4:
                                printf("The elements are\n");
                                inorder(root);
                                break;
                        default:
                                printf("Wrong choice\n");
                                break;
                }
        }
}
int data_print(struct node *x)
{
        if ( x==NULL )
                return 0;
        else
                return x->data;
}
/*some suggestion this code is not fully functional for example 
if you have inserted some elements then try to delete root then it may not work 
because we are calling right and left child of a null value(parent of root) 
which is not allowed and will give segmentation fault
 
Also for inserting second element because of splaying twice(once in insert and one in main) 
will give error So I have made those changes but mainly in my cpp( c plus plus file) file, 
but I guess wiki will itself look into this and made  these changes */

 

伸展树应用

(1)     数列维护问题

题目:维护一个数列,支持以下几种操作:

1. 插入:在当前数列第posi 个数字后面插入tot 个数字;若在数列首位插入,则posi 为0。

2. 删除:从当前数列第posi 个数字开始连续删除tot 个数字。

3. 修改:从当前数列第posi 个数字开始连续tot 个数字统一修改为c 。

4. 翻转:取出从当前数列第posi 个数字开始的tot 个数字,翻转后放入原来的位置。

5. 求和:计算从当前数列第posi 个数字开始连续tot 个数字的和并输出。

6. 求和最大子序列:求出当前数列中和最大的一段子序列,并输出最大和。

(2)     轻量级web服务器lighttpd中用到数据结构splay tree. 

 

 

 

§5 小结

这篇博文非常详尽了讲解了伸展树的定义,伸展过程,基本操作以及实现等内容,学完基本可以掌握的伸展树的特点。如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。

 

 

参考:

kernel@hcy http://www.cnblogs.com/kernel_hcy/archive/2010/03/17/1688360.html

董的博客 http://dongxicheng.org/structure/splay-tree/

kmplayer: http://kmplayer.iteye.com/blog/566937

④维基百科: http://en.wikipedia.org/wiki/Splay_tree#Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    伸展树(Splay tree)图解与实现(2020.10.22).pdf

    ### 伸展树(Splay Tree)概述 伸展树(Splay Tree)是一种自调整的二叉搜索树,由Daniel Sleator和Robert Tarjan在1985年提出。其核心思想是在每次访问节点后,通过一系列的旋转操作将被访问的节点调整到树根的位置...

    伸展树(Splay Tree)

    ### 伸展树(Splay Tree)详解 #### 一、伸展树简介 **伸展树**(Splay Tree)是一种特殊的二叉搜索树(Binary Search Tree),它能够在平均情况下达到 O(log n) 的时间复杂度,对于插入、查找和删除操作均适用。...

    splay tree C# code 伸展树的C#代码实现

    - 考虑到C#的面向对象特性,可以设计一个`SplayTree`类,包含树的根节点,并提供`Insert`, `Delete`, `Find`等公共方法。 5. **性能分析**:伸展树的平均性能优于普通的二叉搜索树。虽然最坏情况下的性能与普通BST...

    数据结构伸展树splay.rar

    伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。 [1] 在伸展树上...

    splaytree.zip

    展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

    伸展树的基本操作与应用

    伸展树,又称Splay Tree,是由Daniel Sleator和Robert Tarjan在1985年提出的自调整二叉搜索树。与传统二叉搜索树相比,伸展树的显著特点是其能够通过一系列的旋转操作自动调整树的形状,以优化后续操作的效率。尽管...

    splay 伸展树.ppt

    splay 伸展树.ppt

    top_down_splay_tree

    top_down splay_tree 伸展树

    Splay Tree

    伸展树的主要特点:每次访问某个节点时,都把此节点旋转到根部。保证从空树开始任意M次操作最多花费O(MlogN)的时间,也就是说它的摊还时间为O(F(N))。 伸展数的主要难点:展开函数的实现。 基本操作插入、删除、...

    Algorithm-splay_tree.zip

    **算法与自平衡二叉查找树:Splay Tree** 在计算机科学中,算法是一组精心设计的步骤,用于解决特定问题或执行特定任务。它们是编程的基础,通过优化数据结构和逻辑来提高程序效率。本压缩包“Algorithm-splay_tree...

    伸展树 C++ 源代码 数据结构

    伸展树,又称Splay Tree,是一种自调整的二叉搜索树。它的设计目标是通过局部操作优化查找、插入和删除等操作的时间复杂度,使得常用的数据更容易访问,从而提高整体性能。在C++中实现伸展树,可以极大地利用其模板...

    Splay(C++)示例代码

    伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。伸展树是一种自...

    splay-tree:快速的splay-tree数据结构

    快速八叉树 :(非递归)和简单(&lt;1000行代码)实现是直接从Wikipedia改编而成的,使用与相同的API来针对其他树运行基准测试。 该树基于D.Sleator自上而下的展开...S splaytree import SplayTree from 'splaytree'

    cpp-数据结构伸展树原理及C实现自顶向下实现

    伸展树,又称为自平衡二叉查找树...在`SplayTree-master`这个压缩包中,应该包含了这样的C语言实现代码,可以作为学习和研究伸展树的一个实例。通过阅读和理解这些代码,可以更深入地了解伸展树的工作原理和实现细节。

    BTree、AVLTree、RBTree、BinarySearchTree和SPlayTree的C++源码实现

    在给定的标题和描述中,我们涉及到了五种特定的树型数据结构,它们是BTree(B树)、AVLTree(AVL树)、RBTree(红黑树)、BinarySearchTree(二叉搜索树)以及SPlayTree(自旋搜索树),并且这些数据结构的C++源码...

    erl-splay-tree:Erlang中的splay-tree实现

    1. **二叉搜索树**:Splay Tree是基于二叉搜索树构建的,其中每个节点都包含一个键值,左子树的所有节点的键值小于当前节点,右子树的所有节点的键值大于当前节点。 2. **自调整**:Splay Tree通过执行特定的旋转...

    C++伸展树实现.zip

    伸展树(Splay Tree)是一种自调整的二叉搜索树,由Daniel Sleator和Robert Tarjan在1985年提出。它通过特定的旋转操作(如左旋、右旋和双旋)来重新组织树,使得最近访问的节点更靠近根部,从而在连续的访问中提高...

Global site tag (gtag.js) - Google Analytics