专栏首页Vamei实验室纸上谈兵: 伸展树 (splay tree)

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

我们讨论过,树的搜索效率与树的深度有关。二叉搜索树的深度可能为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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 纸上谈兵: AVL树

    作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 二叉搜索树的深度与搜索效率 我们在树, 二...

    Vamei
  • Python标准库10 多进程初步 (multiprocessing包)

    我们已经见过了使用subprocess包来创建子进程,但这个包有两个很大的局限性:1) 我们总是让subprocess运行外部的程序,而不是运行一个Python...

    Vamei
  • 被解放的姜戈06 假作真时

    之前了解了: 创建Django项目 数据库 模板 表格提交 admin管理页面 上面的功能模块允许我们做出一个具有互动性的站点,但无法验证用户的身份。我们这次了...

    Vamei
  • 调研:深度解析IaaS行业的现状与趋势

    T客汇官网:tikehui.com 撰文:李哲 ? 移动信息化研究中心数据显示: 对于IaaS层的具体产品/服务,企业用户当前的选择主要集中在提供数据存储/灾备...

    人称T客
  • 「企业合规」开发符合GDPR标准的应用程序的15个步骤

    引入欧洲在线数据隐私法将对组织如何处理和管理其用户的个人数据产生重大影响。该法律于1月份通过,将于2018年全面颁布。对于定期处理为欧洲公民提供服务的客户或个人...

    首席架构师智库
  • 一起来学习用户活跃的方法

    本篇内容来源于图书《增长黑客》与文章《用户活跃计划分析》的学习整理。整篇内容在学习前辈的基础上进行改编,对前辈的一些理论选择性地写出来,并根据理论,配了自己平常...

    张俊红
  • 顺丰菜鸟之争平息,腾讯和阿里的战争才刚刚开始

    数据猿导读 云计算市场已经成为阿里和腾讯共同争夺的一大块蛋糕。在以云为核心的生态体系当中,物流是重中之重。 ? 作者 | 大文 本文长度为1800字,建议阅读4...

    数据猿
  • 省心运维,远程接入托管服务

    解决移动办公用户远程接入需求的方案很多,但无论是购买成熟商业产品还是使用开源软件,都需要自己运维。运营维护依赖人工,需要投入人力解决,这对于人力资源缺乏的企业是...

    Accesshub
  • 系列 | OpenVINO视觉加速库使用二

    OpenVINO中模型优化器(Model Optimizer)支持tensorflow/Caffe模型转换为OpenVINO的中间层表示IR(intermedi...

    OpenCV学堂
  • 成为 LiveEdu 项目创建者的 10 大好处

    LiveEdu 正在为我们的八大门类有偿招聘项目创建者:人工智能、加密货币与区块链、网络安全、数据科学、设计、游戏开发、编程和 VR / AR。下图是每个门类所...

    LiveEdu

扫码关注云+社区

领取腾讯云代金券