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

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

zig

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

zig-zag

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

zig-zig

zig-zig operation

Original

zig-zag (double rotation)

zig-zig

zig (single rotation at root)

### 伸展树的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;
}

/*
*
*/
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 欢迎转载，也请保留这段声明。谢谢！ 二叉搜索树的深度与搜索效率 我们在树, 二...

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

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

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

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

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

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

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

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

• ### 一起来学习用户活跃的方法

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

• ### 顺丰菜鸟之争平息，腾讯和阿里的战争才刚刚开始

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

• ### 省心运维，远程接入托管服务

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

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

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

• ### 成为 LiveEdu 项目创建者的 10 大好处

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