伸展树

引用:http://digital.cs.usu.edu/~allan/DS/Notes/Ch22.pdf

一、简介:
伸展树,或者叫自适应查找树,是一种用于保存有序集合的简单高效的数据结构。伸展树实质上是一个二叉查找树。允许查找,插入,删除,删除最小,删除最大,分割,合并等许多操作,这些操作的时间复杂度为O(logN)。由于伸展树可以适应需求序列,因此他们的性能在实际应用中更优秀。
伸展树支持所有的二叉树操作。伸展树不保证最坏情况下的时间复杂度为O(logN)。伸展树的时间复杂度边界是均摊的。尽管一个单独的操作可能很耗时,但对于一个任意的操作序列,时间复杂度可以保证为O(logN)。
二、自调整和均摊分析:
    平衡查找树的一些限制:
1、平衡查找树每个节点都需要保存额外的信息。
2、难于实现,因此插入和删除操作复杂度高,且是潜在的错误点。
3、对于简单的输入,性能并没有什么提高。
    平衡查找树可以考虑提高性能的地方:
1、平衡查找树在最差、平均和最坏情况下的时间复杂度在本质上是相同的。
2、对一个节点的访问,如果第二次访问的时间小于第一次访问,将是非常好的事情。
3、90-10法则。在实际情况中,90%的访问发生在10%的数据上。
4、处理好那90%的情况就很好了。
三、均摊时间边界:
在一颗二叉树中访问一个节点的时间复杂度是这个节点的深度。因此,我们可以重构树的结构,使得被经常访问的节点朝树根的方向移动。尽管这会引入额外的操作,但是经常被访问的节点被移动到了靠近根的位置,因此,对于这部分节点,我们可以很快的访问。根据上面的90-10法则,这样做可以提高性能。
为了达到上面的目的,我们需要使用一种策略──旋转到根(rotate-to-root)。具体实现如下:
旋转分为左旋和右旋,这两个是对称的。图示:
 
为了叙述的方便,上图的右旋叫做X绕Y右旋,左旋叫做Y绕X左旋。
下图展示了将节点3旋转到根:
 
                            图1
首先节点3绕2左旋,然后3绕节点4右旋。
注意:所查找的数据必须符合上面的90-10法则,否则性能上不升反降!!
四、基本的自底向上伸展树:
    应用伸展(splaying)技术,可以得到对数均摊边界的时间复杂度。
    在旋转的时候,可以分为三种情况:
1、zig情况。
    X是查找路径上我们需要旋转的一个非根节点。
    如果X的父节点是根,那么我们用下图所示的方法旋转X到根:
     
                                图2
    这和一个普通的单旋转相同。
2、zig-zag情况。
在这种情况中,X有一个父节点P和祖父节点G(P的父节点)。X是右子节点,P是左子节点,或者反过来。这个就是双旋转。
先是X绕P左旋转,再接着X绕G右旋转。
如图所示:
 
                            图三
3、zig-zig情况。
    这和前一个旋转不同。在这种情况中,X和P都是左子节点或右子节点。
    先是P绕G右旋转,接着X绕P右旋转。
    如图所示:
     
                                    图四
    下面是splay的伪代码:
    P(X) : 获得X的父节点,G(X) : 获得X的祖父节点(=P(P(X)))。
    Function Buttom-up-splay:
        Do
            If X 是 P(X) 的左子结点 Then
                If G(X) 为空 Then
                    X 绕 P(X)右旋
                Else If P(X)是G(X)的左子结点
                    P(X) 绕G(X)右旋
                    X 绕P(X)右旋
                Else
                    X绕P(X)右旋
                    X绕P(X)左旋 (P(X)和上面一句的不同,是原来的G(X))
                Endif
            Else If X 是 P(X) 的右子结点 Then
                If G(X) 为空 Then
                    X 绕 P(X)左旋
                Else If P(X)是G(X)的右子结点
                    P(X) 绕G(X)左旋
                    X 绕P(X)左旋
                Else
                    X绕P(X)左旋
                    X绕P(X)右旋 (P(X)和上面一句的不同,是原来的G(X))
                Endif 
            Endif
        While (P(X) != NULL)
    EndFunction
    仔细分析zig-zag,可以发现,其实zig-zag就是两次zig。因此上面的代码可以简化:
    Function Buttom-up-splay:
        Do
            If X 是 P(X) 的左子结点 Then
                If P(X)是G(X)的左子结点
                    P(X) 绕G(X)右旋
                Endif
                X 绕P(X)右旋
            Else If X 是 P(X) 的右子结点 Then
                If P(X)是G(X)的右子结点
                    P(X) 绕G(X)左旋
                Endif 
                X 绕P(X)左旋
            Endif
        While (P(X) != NULL)
    EndFunction
    下面是一个例子,旋转节点c到根上。 
 
                                    图五
五、基本伸展树操作:
1、插入:
    当一个节点插入时,伸展操作将执行。因此,新插入的节点在根上。
2、查找:
    如果查找成功(找到),那么由于伸展操作,被查找的节点成为树的新根。
如果查找失败(没有),那么在查找遇到NULL之前的那个节点成为新的根。也就是,如果查找的节点在树中,那么,此时根上的节点就是距离这个节点最近的节点。
3、查找最大最小:
        查找之后执行伸展。
4、删除最大最小:
a)删除最小:
    首先执行查找最小的操作。
这时,要删除的节点就在根上。根据二叉查找树的特点,根没有左子节点。
使用根的右子结点作为新的根,删除旧的包含最小值的根。
b)删除最大:
首先执行查找最大的操作。
删除根,并把被删除的根的左子结点作为新的根。
5、删除:
        将要删除的节点移至根。
        删除根,剩下两个子树L(左子树)和R(右子树)。
        使用DeleteMax查找L的最大节点,此时,L的根没有右子树。
        使R成为L的根的右子树。
        如下图示:
         
                                图六
六、自顶向下的伸展树:
    在自底向上的伸展树中,我们需要求一个节点的父节点和祖父节点,因此这种伸展树难以实现。因此,我们可以构建自顶向下的伸展树。
    当我们沿着树向下搜索某个节点X的时候,我们将搜索路径上的节点及其子树移走。我们构建两棵临时的树──左树和右树。没有被移走的节点构成的树称作中树。在伸展操作的过程中:
1、当前节点X是中树的根。
2、左树L保存小于X的节点。
3、右树R保存大于X的节点。
开始时候,X是树T的根,左右树L和R都是空的。和前面的自下而上相同,自上而下也分三种情况:
1、zig:
 
                                图七
    如上图,在搜索到X的时候,所查找的节点比X小,将Y旋转到中树的树根。旋转之后,X及其右子树被移动到右树上。很显然,右树上的节点都大于所要查找的节点。注意X被放置在右树的最小的位置,也就是X及其子树比原先的右树中所有的节点都要小。这是由于越是在路径前面被移动到右树的节点,其值越大。读者可以分析一下树的结构,原因很简单。
2、zig-zig:
 
                                图八
    在这种情况下,所查找的节点在Z的子树中,也就是,所查找的节点比X和Y都小。所以要将X,Y及其右子树都移动到右树中。首先是Y绕X右旋,然后Z绕Y右旋,最后将Z的右子树(此时Z的右子节点为Y)移动到右树中。注意右树中挂载点的位置。
3、zig-zag:
 
                            图九
    在这种情况中,首先将Y右旋到根。这和Zig的情况是一样的。然后变成上图右边所示的形状。接着,对Z进行左旋,将Y及其左子树移动到左树上。这样,这种情况就被分成了两个Zig情况。这样,在编程的时候就会简化,但是操作的数目增加(相当于两次Zig情况)。
    最后,在查找到节点后,将三棵树合并。如图:
 
                                图十
    将中树的左右子树分别连接到左树的右子树和右树的左子树上。将左右树作为X的左右子树。重新最成了一所查找的节点为根的树。
    下面给出伪代码:
    右连接:将当前根及其右子树连接到右树上。左子结点作为新根。
    左连接:将当前根及其左子树连接到左树上。右子结点作为新根。
    T : 当前的根节点。
Function Top-Down-Splay 
     Do 
          If X 小于 T Then 
               If X 等于 T 的左子结点 Then  
                 右连接 
               ElseIf X 小于 T 的左子结点 Then 
                 T的左子节点绕T右旋 
                 右连接 
               Else X大于 T 的左子结点 Then 
                 右连接 
                 左连接 
               EndIf    
          ElseIf X大于 T Then 
               IF X 等于 T 的右子结点 Then 
                 左连接 
               ElseIf X 大于 T 的右子结点 Then 
                 T的右子节点绕T左旋 
                 左连接 
               Else X小于 T 的右子结点‘ Then 
                 左连接 
                 右连接 
               EndIf 
          EndIf 
     While  !(找到 X或遇到空节点) 
      组合左中右树 
EndFunction

 

    同样,上面的三种情况也可以简化:
    Function Top-Down-Splay
        Do 
              If X 小于 T Then 
                   If X 小于 T 的左孩子 Then 
                     T的左子节点绕T右旋 
                   EndIf    
                右连接 
              Else If X大于 T Then 
                   If X 大于 T 的右孩子 Then 
                     T的右子节点绕T左旋
                   EndIf 
左连接 
         EndIf 
While  !(找到 X或遇到空节点) 
组合左中右树 
    EndFuntion

    下面是一个查找节点19的例子:
    在例子中,树中并没有节点19,最后,距离节点最近的节点18被旋转到了根作为新的根。节点20也是距离节点19最近的节点,但是节点20没有成为新根,这和节点20在原来树中的位置有关系。
 
    这个例子是查找节点c:
 
最后,给一个用C语言实现的例子:

 

/*
                An implementation of top-down splaying
                    D. Sleator <sleator@cs.cmu.edu>
                             March 1992
 */
#include <stdlib.h>
#include <stdio.h>
 int size;  /* number of nodes in the tree */
           /* Not actually needed for any of the operations */
typedef struct tree_node Tree;
 struct tree_node
{
    Tree * left, * right;
    int item;
};

Tree * splay (int i, Tree * t)
{
 /* Simple top down splay, not requiring i to be in the tree t.  */
 /* What it does is described above.                             */
    Tree N, *l, *r, *y;
    if (t == NULL)
        return t;
    N.left = N.right = NULL;
    l = r = &N;
    for (;;)
    {
        if (i < t->item)
        {
            if (t->left == NULL)
            {
                break;
            }
            if (i < t->left->item)
            {
                y = t->left;                           /* rotate right */
                t->left = y->right;
                y->right = t;
                t = y;
                if (t->left == NULL)
                {
                    break;
                }
            }
            r->left = t;                               /* link right */
            r = t;
            t = t->left;
        }
        else if (i > t->item)
        {
            if (t->right == NULL)
            {
                break;
            }
            if (i > t->right->item)
            {
                y = t->right;                          /* rotate left */
                t->right = y->left;
                y->left = t;
                t = y;
                if (t->right == NULL)
                {
                    break;
                }
            }
            l->right = t;                              /* link left */
            l = t;
            t = t->right;
        }
        else
        {
            break;
        }
    }
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;
    return t;
}
 /* Here is how sedgewick would have written this.                    */
/* It does the same thing.                                           */
Tree * sedgewickized_splay (int i, Tree * t)
{
    Tree N, *l, *r, *y;
    if (t == NULL)
    {
        return t;
    }
    N.left = N.right = NULL;
    l = r = &N;
    for (;;)
    {
        if (i < t->item)
        {
            if (t->left != NULL && i < t->left->item)
            {
                y = t->left;
                t->left = y->right;
                y->right = t;
                t = y;
            }
            if (t->left == NULL)
            {
                break;
            }
            r->left = t;
            r = t;
            t = t->left;
        }
        else if (i > t->item)
        {
            if (t->right != NULL && i > t->right->item)
            {
                y = t->right;
                t->right = y->left;
                y->left = t;
                t = y;
            }
            if (t->right == NULL)
            {
                break;
            }
            l->right = t;
            l = t;
            t = t->right;
        }
        else
        {
            break;
        }
    }
    l->right=t->left;
    r->left=t->right;
    t->left=N.right;
    t->right=N.left;
    return t;
}

Tree * insert(int i, Tree * t)
{
/* Insert i into the tree t, unless it's already there.    */
/* Return a pointer to the resulting tree.                 */
    Tree * new1;

    new1 = (Tree *) malloc (sizeof (Tree));
    if (new1 == NULL)
    {
        printf("Ran out of space\n");
        exit(1);
    }
    new1->item = i;
    if (t == NULL)
    {
        new1->left = new1->right = NULL;
        size = 1;
        return new1;
    }
    t = splay(i,t);
    if (i < t->item)
    {
        new1->left = t->left;
        new1->right = t;
        t->left = NULL;
        size ++;
        return new1;
    }
    else if (i > t->item)
    {
        new1->right = t->right;
        new1->left = t;
        t->right = NULL;
        size++;
        return new1;
    }
    else
    {
        /* We get here if it's already in the tree */
        /* Don't add it again                      */
        free(new1);
        return t;
    }
}

Tree * delete1(int i, Tree * t)
{
/* Deletes i from the tree if it's there.               */
/* Return a pointer to the resulting tree.              */
    Tree * x;
    if (t==NULL)
    {
        return NULL;
    }
    t = splay(i,t);
    if (i == t->item)
    {               /* found it */
        if (t->left == NULL)
        {
            x = t->right;
        }
        else
        {
            x = splay(i, t->left);
            x->right = t->right;
        }
        size--;
        free(t);
        return x;
    }
    return t;                         /* It wasn't there */
}

int main(int argv, char *argc[])
{
/* A sample use of these functions.  Start with the empty tree,         */
/* insert some stuff into it, and then delete it                        */
    Tree * root;
    int i;
    root = NULL;              /* the empty tree */
    size = 0;
    for (i = 0; i < 1024; i++)
    {
        root = insert((541*i) & (1023), root);
    }
    printf("size = %d\n", size);
    for (i = 0; i < 1024; i++)
    {
        root = delete1((541*i) & (1023), root);
    }
    printf("size = %d\n", size);
}

 

时间: 2024-09-15 15:24:50

伸展树的相关文章

Java数据结构与算法解析(八)——伸展树

伸展树简介 伸展树(Splay Tree)是特殊的二叉查找树. 它的特殊是指,它除了本身是棵二叉查找树之外,它还具备一个特点: 当某个节点被访问时,伸展树会通过旋转使该节点成为树根.这样做的好处是,下次要访问该节点时,能够迅速的访问到该节点. 特性 和普通的二叉查找树相比,具有任何情况下.任何操作的平摊O(log2n)的复杂度,时间性能上更好 和一般的平衡二叉树比如 红黑树.AVL树相比,维护更少的节点额外信息,空间性能更优,同时编程复杂度更低 在很多情况下,对于查找操作,后面的查询和之前的查询

纸上谈兵: 伸展树 (splay tree)[转]

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明.谢谢!    我们讨论过,树的搜索效率与树的深度有关.二叉搜索树的深度可能为n,这种情况下,每次搜索的复杂度为n的量级.AVL树通过动态平衡树的深度,单次搜索的复杂度为log(n) (以上参考纸上谈兵 AVL树).我们下面看伸展树(splay tree),它对于m次连续搜索操作有很好的效率.   伸展树会在一次搜索后,对树进行一些特殊的操作.这些操作的理念与AVL树有些类似,即通过旋转,

6天通吃树结构—— 第四天 伸展树

        我们知道AVL树为了保持严格的平衡,所以在数据插入上会呈现过多的旋转,影响了插入和删除的性能,此时AVL的一个变种 伸展树(Splay)就应运而生了,我们知道万事万物都遵循一个"八二原则",也就是说80%的人只会用到20%的数据,比如说我们 的"QQ输入法",平常打的字也就那么多,或许还没有20%呢.   一:伸展树  1:思想     伸展树的原理就是这样的一个"八二原则",比如我要查询树中的"节点7",如果

【BBST 之伸展树 (Splay Tree)】

最近"hiho一下"出了平衡树专题,这周的Splay一直出现RE,应该删除操作指针没处理好,还没找出原因. 不过其他操作运行正常,尝试用它写了一道之前用set做的平衡树的题http://codeforces.com/problemset/problem/675/D,运行效果居然还挺好的,时间快了大概10%,内存少了大概30%. 1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4

数据结构基础 伸展树

问题描述 数据结构基础 伸展树 为什么我自己画出来的展开的树和书上的不一样呢,是哪步旋转错了么? 解决方案 数据结构 - 树(基础)数据结构基础(3)-------------树第六章数据结构基础之树部分 解决方案二: 图看不清,谁知道你问的啥.

数据结构之伸展树详解_C 语言

1. 概述 二叉查找树(Binary Search Tree,也叫二叉排序树,即Binary Sort Tree)能够支持多种动态集合操作,它可以用来表示有序集合.建立索引等,因而在实际应用中,二叉排序树是一种非常重要的数据结构. 从算法复杂度角度考虑,我们知道,作用于二叉查找树上的基本操作(如查找,插入等)的时间复杂度与树的高度成正比.对一个含n个节点的完全二叉树,这些操作的最坏情况运行时间为O(log n).但如果因为频繁的删除和插入操作,导致树退化成一个n个节点的线性链(此时即为一个单链表

纸上谈兵: 伸展树 (splay tree)

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明.谢谢!    我们讨论过,树的搜索效率与树的深度有关.二叉搜索树的深度可能为n,这种情况下,每次搜索的复杂度为n的量级.AVL树通过动态平衡树的深度,单次搜索的复杂度为log(n) (以上参考纸上谈兵 AVL树).我们下面看伸展树(splay tree),它对于m次连续搜索操作有很好的效率.   伸展树会在一次搜索后,对树进行一些特殊的操作.这些操作的理念与AVL树有些类似,即通过旋转,

伸展树——自顶向下

三种旋转    当我们沿着树向下搜索某个节点X的时候,我们将搜索路径上的节点及其子树移走.我们构建两棵临时的树──左树和右树. 没有被移走的节点构成的树称作中树.在伸展操作的过程中: 1.当前节点X是中树的根.2.左树L保存小于X的节点.3.右树R保存大于X的节点.开始时候,X是树T的根,左右树L和R都是空的.1.zig:                                     如上图,在搜索到X的时候,所查找的节点比X小,将Y旋转到中树的树根.旋转之后,X及其右子树被移动到右树

《程序设计解题策略》——第1章 利用树型数据关系的解题策略 1.1 利用划分树求解整数区间内第k大的值

第1章 利用树型数据关系的解题策略 树是一个具有层次结构的集合,一种限制前件数且没有回路的连通图.在现实生活和程序设计的竞赛试题中,许多问题的数据关系呈树型结构,因此有关树的概念.原理.操作方法和一些由树的数据结构支持的算法,一直受到编程者的重视,被广泛应用于解题过程.在本章里,我们将介绍利用树型数据关系解题的七种策略: 1) 利用划分树求解整数区间内第k大值. 2) 利用最小生成树及其扩展形式(最优比率生成树.最小k度生成树.次小生成树)计算有权连通无向图中边权和满足限制条件的最优生成树. 3