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

作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！ 

 

我们讨论过，树的搜索效率与树的深度有关。二叉搜索树的深度可能为n，这种情况下，每次搜索的复杂度为n的量级。AVL树通过动态平衡树的深度，单次搜索的复杂度为log(n) (以上参考纸上谈兵 AVL树)。我们下面看伸展树(splay tree)，它对于m次连续搜索操作有很好的效率。

 

伸展树会在一次搜索后，对树进行一些特殊的操作。这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度。但伸展树并没有AVL的平衡要求，任意节点的左右子树可以相差任意深度。与二叉搜索树类似，伸展树的单次搜索也可能需要n次操作。但伸展树可以保证，m次的连续搜索操作的复杂度为mlog(n)的量级，而不是mn量级。

 

具体来说，在查询到目标节点后，伸展树会不断进行下面三种操作中的一个，直到目标节点成为根节点 （注意，祖父节点是指父节点的父节点）

1. zig: 当目标节点是根节点的左子节点或右子节点时，进行一次单旋转，将目标节点调整到根节点的位置。

zig

2. zig-zag: 当目标节点、父节点和祖父节点成"zig-zag"构型时，进行一次双旋转，将目标节点调整到祖父节点的位置。

zig-zag

3. zig-zig：当目标节点、父节点和祖父节点成"zig-zig"构型时，进行一次zig-zig操作，将目标节点调整到祖父节点的位置。

zig-zig

单旋转操作和双旋转操作见AVL树。下面是zig-zig操作的示意图:

zig-zig operation

在伸展树中，zig-zig操作(基本上)取代了AVL树中的单旋转。通常来说，如果上面的树是失衡的，那么A、B子树很可能深度比较大。相对于单旋转(想一下单旋转的效果)，zig-zig可以将A、B子树放在比较高的位置，从而减小树总的深度。

 

下面我们用一个具体的例子示范。我们将从树中搜索节点2：

Original

zig-zag (double rotation)

zig-zig

zig (single rotation at root)

上面的第一次查询需要n次操作。然而经过一次查询后，2节点成为了根节点，树的深度大减小。整体上看，树的大部分节点深度都减小。此后对各个节点的查询将更有效率。

伸展树的另一个好处是将最近搜索的节点放在最容易搜索的根节点的位置。在许多应用环境中，比如网络应用中，某些固定内容会被大量重复访问(比如江南style的MV)。伸展树可以让这种重复搜索以很高的效率完成。

 

伸展树的C实现

/* By Vamei */
/* Splay Tree */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

struct node {
    position parent;
    ElementTP element;
    position lchild;
    position rchild;
};

/* pointer => root node of the tree */
typedef struct node *TREE;

TREE find_value(TREE, ElementTP);
position insert_value(TREE, ElementTP);

static void splay_tree(TREE, position);
static position search_value(TREE, ElementTP);
static void with_grandpa(TREE, position);

static void insert_node_to_nonempty_tree(TREE, position);
static TREE left_single_rotate(TREE);
static TREE left_double_rotate(TREE);
static TREE right_single_rotate(TREE);
static TREE right_double_rotate(TREE);
static TREE left_zig_zig(TREE);
static TREE right_zig_zig(TREE);

void main(void)
{
    TREE tr;
    tr = NULL;
    tr = insert_value(tr, 6);
    tr = insert_value(tr, 5);
    tr = insert_value(tr, 4);
    tr = insert_value(tr, 3);
    tr = insert_value(tr, 1);
    tr = insert_value(tr, 2); 

    tr = find_value(tr, 2);
    printf("%d\n", tr->rchild->lchild->element);
}

/*
 * insert a value into the tree
 * return root address of the tree
 */
position insert_value(TREE tr, ElementTP value)
{
    position np;
    /* prepare the node */
    np = (position) malloc(sizeof(struct node));
    np->element = value;
    np->parent  = NULL;
    np->lchild  = NULL;
    np->rchild  = NULL;

    if (tr == NULL) tr = np;
    else {
        insert_node_to_nonempty_tree(tr, np);
    }
    return tr;
}

/*
 *
 * return NUll if not found
 */
TREE find_value(TREE tr, ElementTP value)
{
    position np;

    np = search_value(tr, value);
    if (np != NULL && np != tr) {
        splay_tree(tr, np);
    }
    return np;
}

/*
 * splaying the tree after search
 */
static void splay_tree(TREE tr, position np)
{
    while (tr->lchild != np && tr->rchild != np) {
        with_grandpa(tr, np);
    }
    if (tr->lchild == np) {
        right_single_rotate(tr);
    }
    else if (tr->rchild == np) {
        left_single_rotate(tr);
    }
}

/*
 * dealing cases with grandparent node
 */
static void with_grandpa(TREE tr, position np)
{
    position parent, grandPa;
    int i,j; 

    parent  = np->parent;
    grandPa = parent->parent;

    i = (grandPa->lchild == parent) ? -1 : 1;
    j = (parent->lchild == np) ? -1 : 1;
    if (i == -1 && j == 1) {
        right_double_rotate(grandPa);
    }
    else if (i == 1 && j == -1) {
        left_double_rotate(grandPa);
    }
    else if (i == -1 && j == -1) {
        right_zig_zig(grandPa);
    }
    else {
        left_zig_zig(grandPa);
    }
}

/*
 * search for value
 */
static position search_value(TREE tr, ElementTP value)
{
    if (tr == NULL) return NULL; 

    if (tr->element == value) {
        return tr;
    }
    else if (value < tr->element) {
        return search_value(tr->lchild, value);
    }
    else {
        return search_value(tr->rchild, value);
    }
}

/*
 * left single rotation
 * return the new root
 */
static TREE left_single_rotate(TREE tr)
{
    TREE newRoot, parent;
    parent  = tr->parent;
    newRoot = tr->rchild;
    /* detach & attach */
    if (newRoot->lchild != NULL) newRoot->lchild->parent = tr;
    tr->rchild = newRoot->lchild;

    /* raise new root node */
    newRoot->lchild = tr;
    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->lchild == tr) {
        parent->lchild = newRoot;
    }
    else {
        parent->rchild = newRoot;
    }
    }
    tr->parent = newRoot;
    return newRoot;
}

/*
 * right single rotation
 * return the new root
 */
static TREE right_single_rotate(TREE tr)
{
    TREE newRoot, parent;
    parent  = tr->parent;
    newRoot = tr->lchild;

    /* detach & attach */
    if (newRoot->rchild != NULL) newRoot->rchild->parent = tr;
    tr->lchild = newRoot->rchild;

    /* raise new root node */
    newRoot->rchild = tr;
    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->lchild == tr) {
        parent->lchild = newRoot;
    }
    else {
        parent->rchild = newRoot;
    }
    }
    tr->parent = newRoot;
    return newRoot;
}

/*
 * left double rotation
 * return
 */
static TREE left_double_rotate(TREE tr)
{
    right_single_rotate(tr->rchild);
    return left_single_rotate(tr);
}

/*
 * right double rotation
 * return
 */
static TREE right_double_rotate(TREE tr)
{
    left_single_rotate(tr->lchild);
    return right_single_rotate(tr);
}

/*
 * insert a node to a non-empty tree
 * called by insert_value()
 */
static void insert_node_to_nonempty_tree(TREE tr, position np)
{
    /* insert the node */
    if(np->element <= tr->element) {
        if (tr->lchild == NULL) {
            /* then tr->lchild is the proper place */
            tr->lchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->lchild, np);
        }
    }
    else if(np->element > tr->element) {
        if (tr->rchild == NULL) {
            tr->rchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->rchild, np);
        }
    }
}
/* * right zig-zig operation */
static TREE right_zig_zig(TREE tr)
{
    position parent,middle,newRoot;
    parent  = tr->parent;
    middle  = tr->lchild;
    newRoot = tr->lchild->lchild;

    tr->lchild = middle->rchild;
    if (middle->rchild != NULL) middle->rchild->parent = tr;

    middle->rchild = tr;
    tr->parent     = middle;

    middle->lchild = newRoot->rchild;
    if (newRoot->rchild != NULL) newRoot->rchild->parent = middle;

    newRoot->rchild = middle;
    middle->parent  = newRoot;

    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->lchild == tr) {
        parent->lchild = newRoot;
    }
    else {
        parent->rchild = newRoot;
    }
    }
    return newRoot;
}
/* * left zig-zig operation */
static TREE left_zig_zig(TREE tr)
{
    position parent,middle,newRoot;
    parent  = tr->parent;
    middle  = tr->rchild;
    newRoot = tr->rchild->rchild;

    tr->rchild = middle->lchild;
    if (middle->lchild != NULL) middle->lchild->parent = tr;

    middle->lchild = tr;
    tr->parent     = middle;

    middle->rchild = newRoot->lchild;
    if (newRoot->lchild != NULL) newRoot->lchild->parent = middle;

    newRoot->lchild = middle;
    middle->parent  = newRoot;

    newRoot->parent = parent;
    if (parent != NULL) {
        if (parent->rchild == tr) {
        parent->rchild = newRoot;
    }
    else {
        parent->lchild = newRoot;
    }
    }
    return newRoot;
}

运行结果:

4

 

总结

splay tree, m operations: mlog(n)

zig-zig

 

欢迎继续阅读“纸上谈兵: 算法与数据结构”系列。

 

时间： 2024-10-27 07:52:54

纸上谈兵: 伸展树 (splay tree)的相关文章

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

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

【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

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

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

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

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

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

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

伸展树

引用:http://digital.cs.usu.edu/~allan/DS/Notes/Ch22.pdf 一.简介:伸展树,或者叫自适应查找树,是一种用于保存有序集合的简单高效的数据结构.伸展树实质上是一个二叉查找树.允许查找,插入,删除,删除最小,删除最大,分割,合并等许多操作,这些操作的时间复杂度为O(logN).由于伸展树可以适应需求序列,因此他们的性能在实际应用中更优秀.伸展树支持所有的二叉树操作.伸展树不保证最坏情况下的时间复杂度为O(logN).伸展树的时间复杂度边界是均摊的.尽管

数据结构基础 伸展树

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

伸展树——自顶向下

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

纸上谈兵: AVL树

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明.谢谢!   二叉搜索树的深度与搜索效率 我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n.比如下面两个二叉树: 深度为n的二叉树 深度为log(n)的二叉树 这两个二叉树同时也是二叉搜索树(参考树, 二叉树, 二叉搜索树).注意,log以2为基底.log(n)是指深度的量级.根据我们对深度的定义,精确的最小深度为floor(log(