- 浏览: 1409917 次
- 性别:
- 来自: 广州
-
文章分类
最新评论
-
sdgxxtc：
[quo[color=red]te][/color]
C#使用OleDb读取Excel，生成SQL语句 -
zcs302567601：
博主，你好，一直都有个问题没有搞明白，就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻：
感谢楼主！
有向强连通和网络流大讲堂——史无前例求解最大流（最小割）、最小费用最大流 -
cp1993518：
感谢！从你的博客里学到了很多
Unity日志工具——封装，跳转 -
cp1993518：
学习了~，话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
伸展树（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
发表评论
-
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3569在C# 调用Delegate.Create ... -
数组问题集结号
2012-12-06 22:01 0数组是最简单的数据结构，数组问题作为公司招聘的笔试和面试题目 ... -
算法问题分析笔记
2012-12-05 11:59 01.Crash Balloon Zhejiang Univer ... -
Java基础进阶整理
2012-11-26 09:59 2320Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2639《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法（BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4142尊重他人的劳动，支持原创 本篇博文，D.S.Q ... -
基本技术——贪心法、分治法、动态规划三大神兵
2012-11-03 19:30 0基本技术——贪心法、分治法、动态规划三大神兵 -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:12 35630优先队列三大利器——二项堆、斐波那契堆、Pairing ... -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:01 3优先队列三大利器——二项堆、斐波那契堆、Pairing 堆 ... -
排序算法群星豪华大汇演
2012-10-30 00:09 3138排序算法群星豪华大汇演 排序算法相对简单些，但是由于 ... -
分布排序（distribution sorts）算法大串讲
2012-10-29 15:33 4659分布排序（distribution sorts）算法大串讲 ... -
归并排序（merge sorts）算法大串讲
2012-10-29 10:04 8312归并排序（merge sorts）算法大串讲 ... -
交换排序（exchange sorts）算法大串讲
2012-10-29 00:22 4409交换排序（exchange sorts）算法大串讲 本 ... -
选择排序（selection sorts）算法大串讲
2012-10-28 12:55 3710选择排序（selection sorts）算法大串讲 本文内 ... -
插入排序（insertion sorts）算法大串讲
2012-10-28 11:30 2747插入排序（insertion sorts ... -
红黑树（Red-Black Tree）不在话下
2012-10-26 20:54 2233红黑树（Red-Black Tree） 红黑树定义 红黑树 ... -
平衡二叉树（AVL）原理透析和编码解密
2012-10-26 10:22 2995平衡二叉树（AVL）原理透析和编码解密 本文内容 ...
相关推荐
### 伸展树(Splay Tree)概述 伸展树（Splay Tree）是一种自调整的二叉搜索树，由Daniel Sleator和Robert Tarjan在1985年提出。其核心思想是在每次访问节点后，通过一系列的旋转操作将被访问的节点调整到树根的位置...
### 伸展树(Splay Tree)详解 #### 一、伸展树简介 **伸展树**（Splay Tree）是一种特殊的二叉搜索树（Binary Search Tree），它能够在平均情况下达到 O(log n) 的时间复杂度，对于插入、查找和删除操作均适用。...
- 考虑到C#的面向对象特性，可以设计一个`SplayTree`类，包含树的根节点，并提供`Insert`, `Delete`, `Find`等公共方法。 5. **性能分析**：伸展树的平均性能优于普通的二叉搜索树。虽然最坏情况下的性能与普通BST...
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。 [1] 在伸展树上...
### SplayTree（伸展树）详细解释 #### 基本概念 SplayTree，又称伸展树，是一种自调整的二叉搜索树。它虽然不像其他平衡二叉搜索树那样严格限制树的形状，但通过一种叫做伸展的操作，在访问节点后将其提升到根节点...
展树（Splay Tree）是一种二叉搜索树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
伸展树，又称Splay Tree，是由Daniel Sleator和Robert Tarjan在1985年提出的自调整二叉搜索树。与传统二叉搜索树相比，伸展树的显著特点是其能够通过一系列的旋转操作自动调整树的形状，以优化后续操作的效率。尽管...
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。伸展树是一种自...
splay 伸展树.ppt
top_down splay_tree 伸展树
伸展树的主要特点：每次访问某个节点时，都把此节点旋转到根部。保证从空树开始任意M次操作最多花费O(MlogN)的时间，也就是说它的摊还时间为O（F（N））。 伸展数的主要难点：展开函数的实现。 基本操作插入、删除、...
**算法与自平衡二叉查找树：Splay Tree** 在计算机科学中，算法是一组精心设计的步骤，用于解决特定问题或执行特定任务。它们是编程的基础，通过优化数据结构和逻辑来提高程序效率。本压缩包“Algorithm-splay_tree...
伸展树，又称Splay Tree，是一种自调整的二叉搜索树。它的设计目标是通过局部操作优化查找、插入和删除等操作的时间复杂度，使得常用的数据更容易访问，从而提高整体性能。在C++中实现伸展树，可以极大地利用其模板...
快速八叉树 ：（非递归）和简单（<1000行代码）实现是直接从Wikipedia改编而成的，使用与相同的API来针对其他树运行基准测试。 该树基于D.Sleator自上而下的展开...S splaytree import SplayTree from 'splaytree'
伸展树，又称为自平衡二叉查找树...在`SplayTree-master`这个压缩包中，应该包含了这样的C语言实现代码，可以作为学习和研究伸展树的一个实例。通过阅读和理解这些代码，可以更深入地了解伸展树的工作原理和实现细节。
在给定的标题和描述中，我们涉及到了五种特定的树型数据结构，它们是BTree（B树）、AVLTree（AVL树）、RBTree（红黑树）、BinarySearchTree（二叉搜索树）以及SPlayTree（自旋搜索树），并且这些数据结构的C++源码...
1. **二叉搜索树**：Splay Tree是基于二叉搜索树构建的，其中每个节点都包含一个键值，左子树的所有节点的键值小于当前节点，右子树的所有节点的键值大于当前节点。 2. **自调整**：Splay Tree通过执行特定的旋转...
伸展树（Splay Tree）是一种自调整的二叉搜索树，由Daniel Sleator和Robert Tarjan在1985年提出。它通过特定的旋转操作（如左旋、右旋和双旋）来重新组织树，使得最近访问的节点更靠近根部，从而在连续的访问中提高...