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

1、 概述

二叉查找树(Binary Search Tree,也叫二叉排序树,即Binary Sort Tree)能够支持多种动态集合操作,它可以用来表示有序集合、建立索引等,因而在实际应用中,二叉排序树是一种非常重要的数据结构。

从算法复杂度角度考虑,我们知道,作用于二叉查找树上的基本操作(如查找,插入等)的时间复杂度与树的高度成正比。对一个含n个节点的完全二叉树,这些操作的最坏情况运行时间为O(log n)。但如果因为频繁的删除和插入操作,导致树退化成一个n个节点的线性链(此时即为一个单链表),则这些操作的最坏情况运行时间为O(n)。为了克服以上缺点,很多二叉查找树的变形出现了,如红黑树、AVL树,Treap树等。

本文介绍了二叉查找树的一种改进数据结构–伸展树(Splay Tree)。它的主要特点是不会保证树一直是平衡的,但各种操作的平摊时间复杂度是O(log n),因而,从平摊复杂度上看,二叉查找树也是一种平衡二叉树。另外,相比于其他树状数据结构(如红黑树,AVL树等),伸展树的空间要求与编程复杂度要小得多。

2、 基本操作

伸展树的出发点是这样的:考虑到局部性原理(刚被访问的内容下次可能仍会被访问,查找次数多的内容可能下一次会被访问),为了使整个查找时间更小,被查频率高的那些节点应当经常处于靠近树根的位置。这样,很容易得想到以下这个方案:每次查找节点之后对树进行重构,把被查找的节点搬移到树根,这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后,它均会通过旋转的方法把被访问节点旋转到树根的位置。

为了将当前被访问节点旋转到树根,我们通常将节点自底向上旋转,直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系(指中序遍历结果是全序的)情况下,所有基本操作的平摊复杂度仍为O(log n)。

伸展树主要有三种旋转操作,分别为单旋转,一字形旋转和之字形旋转。为了便于解释,我们假设当前被访问节点为X,X的父亲节点为Y(如果X的父亲节点存在),X的祖父节点为Z(如果X的祖父节点存在)。

(1)单旋转

节点X的父节点Y是根节点。这时,如果X是Y的左孩子,我们进行一次右旋操作;如果X 是Y 的右孩子,则我们进行一次左旋操作。经过旋转,X成为二叉查找树T的根节点,调整结束。

(2)一字型旋转

节点X 的父节点Y不是根节点,Y 的父节点为Z,且X与Y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时,我们进行一次左左旋转操作或者右右旋转操作。

(3)之字形旋转

节点X的父节点Y不是根节点,Y的父节点为Z,X与Y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时,我们进行一次左右旋转操作或者右左旋转操作。

3、伸展树区间操作

在实际应用中,伸展树的中序遍历即为我们维护的数列,这就引出一个问题,怎么在伸展树中表示某个区间?比如我们要提取区间[a,b],那么我们将a前面一个数对应的结点转到树根,将b 后面一个结点对应的结点转到树根的右边,那么根右边的左子树就对应了区间[a,b]。原因很简单,将a 前面一个数对应的结点转到树根后, a 及a 后面的数就在根的右子树上,然后又将b后面一个结点对应的结点转到树根的右边,那么[a,b]这个区间就是下图中B所示的子树。

利用区间操作我们可以实现线段树的一些功能,比如回答对区间的询问(最大值,最小值等)。具体可以这样实现,在每个结点记录关于以这个结点为根的子树的信息,然后询问时先提取区间,再直接读取子树的相关信息。还可以对区间进行整体修改,这也要用到与线段树类似的延迟标记技术,即对于每个结点,额外记录一个或多个标记,表示以这个结点为根的子树是否被进行了某种操作,并且这种操作影响其子结点的信息值,当进行旋转和其他一些操作时相应地将标记向下传递。
与线段树相比,伸展树功能更强大,它能解决以下两个线段树不能解决的问题:

(1) 在a后面插入一些数。方法是:首先利用要插入的数构造一棵伸展树,接着,将a 转到根,并将a 后面一个数对应的结点转到根结点的右边,最后将这棵新的子树挂到根右子结点的左子结点上。

(2)  删除区间[a,b]内的数。首先提取[a,b]区间,直接删除即可。

4、实现

代码全部来自【参考资料2】。

(1)旋转操作

// node 为结点类型,其中ch[0]表示左结点指针,ch[1]表示右结点指针

// pre 表示指向父亲的指针

// Rotate函数用于(左/右)旋转x->pre

void Rotate(node *x, int d) // 旋转操作,d=0 表示左旋,d=1 表示右旋

{

 node *y = x->pre;

 Push_Down(y), Push_Down(x);

 // 先将Y 结点的标记向下传递(因为Y 在上面),再把X 的标记向下传递

 y->ch[! d] = x->ch[d];

 if (x->ch[d] != Null) x->ch[d]->pre = y;

 x->pre = y->pre;

 if (y->pre != Null)

 if (y->pre->ch[0] == y) y->pre->ch[0] = x; else y->pre->ch[1] = x;

 x->ch[r] = y, y->pre = x, Update(y); // 维护Y 结点

 if (y == root) root = x; // root 表示整棵树的根结点

}

(2)splay操作

void Splay(node *x, node *f) // Splay 操作,表示把结点x 转到结点f 的下面

{

 for (Push_Down(x) ; x->pre != f; ) // 一开始就将X 的标记下传

 if (x->pre->pre == f) // 父结点的父亲即为f,执行单旋转

  if (x->pre->ch[0] == x) Rotate(x, 1); else Rotate(x, 0);

 else

 {

  node *y = x->pre, *z = y->pre;

  if (z->ch[0] == y)

   if (y->ch[0] == x)

    Rotate(y, 1), Rotate(x, 1); // 一字形旋转

   else

    Rotate(x, 0), Rotate(x, 1); // 之字形旋转

  else

   if (y->ch[1] == x)

    Rotate(y, 0), Rotate(x, 0); // 一字形旋转

   else

    Rotate(x, 1), Rotate(x, 0); // 之字形旋转

 }

 Update(x); // 最后再维护X 结点

}

(3)将第k个数转到要求的位置

// 找到处在中序遍历第k 个结点,并将其旋转到结点f 的下面

void Select(int k, node *f)

{

 int tmp;

 node *t;

 for (t = root; ; ) // 从根结点开始

 {

  Push_Down(t); // 由于要访问t 的子结点,将标记下传

  tmp = t->ch[0]->size; // 得到t 左子树的大小

  if (k == tmp + 1) break; // 得出t 即为查找结点,退出循环

  if (k <= tmp) // 第k 个结点在t 左边,向左走

   t = t->ch[0];

  else // 否则在右边,而且在右子树中,这个结点不再是第k 个

   k -= tmp + 1, t = t->ch[1];

 }

 Splay(t, f); // 执行旋转

}

5、 应用

(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.

6、 参考资料
(1)杨思雨《伸展树的基本操作与应用》
(2)Crash《运用伸展树解决数列维护问题》

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索数据结构
伸展树
c语言结构体详解、c语言file结构体详解、数据结构链表详解、数据结构详解、java数据结构详解,以便于您获取更多的相关知识。

时间: 2024-10-23 13:20:55

数据结构之伸展树详解_C 语言的相关文章

数据结构之AVL树详解_C 语言

1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树.AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis.AVL树种查找.插入和删除在平均和最坏情况下都是O(log n),增加和删除可能需要通过一次或多次树旋转来重新平衡这个树.本文介绍了AVL树的设计思想和基本操作. 2. 基本术语 有四种种情况可能导致二叉查找树不平衡,分别为: (1)LL:插入一个新节点到根节点的左子树(Left)的左子树

数据结构之红黑树详解_C 语言

1.简介 红黑树是一种自平衡二叉查找树.它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用.在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持).它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除等操作. 本文介绍了红黑树的基本性质和基本操作. 2.红黑树

数据结构之Treap详解_C 语言

1. 概述 同splay tree一样,treap也是一个平衡二叉树,不过Treap会记录一个额外的数据,即优先级.Treap在以关键码构成二叉搜索树的同时,还按优先级来满足堆的性质.因而,Treap=tree+heap.这里需要注意的是,Treap并不是二叉堆,二叉堆必须是完全二叉树,而Treap可以并不一定是. 2. Treap基本操作 为了使Treap 中的节点同时满足BST性质和最小堆性质,不可避免地要对其结构进行调整,调整方式被称为旋转.在维护Treap 的过程中,只有两种旋转,分别是

C语言 经典题目螺旋矩阵 实例详解_C 语言

C语言 经典题目螺旋矩阵 //N阶螺旋矩阵 #include <stdio.h> #include <stdlib.h> int main() { int N,i,j,n,num=1; int a[10][10]={0}; printf("输入你要输出的几阶中断:"); scanf("%d",&N); for(n=0;n<=N/2;n++) { for(j=n;j<=N-n-1;j++) a[n][j]=num++; fo

C迷途指针详解_C 语言

本文较为详尽的讲述了C语言的迷途指针,分析了其概念.原理与检测方法.分享给大家供大家参考.具体如下: 一般来说,在计算机编程领域中,迷途指针,或称悬空指针.野指针,指的是不指向任何合法的对象的指针. 当所指向的对象被释放或者收回,但是对该指针没有作任何的修改,以至于该指针仍旧指向已经回收的内存地址,此情况下该指针便称迷途指针.若操作系统将这部分已经释放的内存重新分配给另外一个进程,而原来的程序重新引用现在的迷途指针,则将产生无法预料的后果.因为此时迷途指针所指向的内存现在包含的已经完全是不同的数

C语言中操作进程信号的相关函数使用详解_C 语言

C语言signal()函数:设置信号处理方式头文件: #include <signal.h> 定义函数: void (*signal(int signum, void(* handler)(int)))(int); 函数说明:signal()会依参数signum 指定的信号编号来设置该信号的处理函数. 当指定的信号到达时就会跳转到参数handler 指定的函数执行. 如果参数handler 不是函数指针, 则必须是下列两个常数之一: 1.SIG_IGN 忽略参数signum 指定的信号. 2.

C++计数排序详解_C 语言

计数排序不同于比较排序,是基于计数的方式,对于计数排序,假设每一个输入都是介于0~k之间的整数.对于每一个输入元素x,确定出小于x的元素的个数.假如有17个元素小于x,则x就属于第18个输出位置. 计数排序涉及到三个数组A[0-..length-1],length为数组A的长度:数组B与数组A长度相等,存放最终排序的结果:C[0-..K]存放A中每个元素的个数,k为数组A中的最大值. int count_k(int A[],int length),此函数为了确定数组A中最大的元素,用来确定C数组

C++的get()函数与getline()函数使用详解_C 语言

C++ get()函数读入一个字符 get()函数是cin输入流对象的成员函数,它有3种形式:无参数的,有一个参数的,有3个参数的. 1) 不带参数的get函数 其调用形式为 cin.get() 用来从指定的输入流中提取一个字符(包括空白字符),函数的返回值就是读入的字符. 若遇到输入流中的文件结束符,则函数值返回文件结束标志EOF(End Of File),一般以-1代表EOF,用-1而不用0或正值,是考虑到不与字符的ASCII代码混淆,但不同的C ++系统所用的EOF值有可能不同. [例]

C++编程中的格式化输出详解_C 语言

在输出数据时,为简便起见,往往不指定输出的格式,由系统根据数据的类型采取默认的格式,但有时希望数据按指定的格式输出,如要求以十六进制或八进制形式输出一个 整数,对输出的小数只保留两位小数等.有两种方法可以达到此目的.一种是使用控制符的方法:第2种是使用流对象的有关成员函数.分别叙述如下. 使用控制符控制输出格式 控制格式的使用方法这里不再赘述,仅举例说明 [例] 用控制符控制输出格式. #include <iostream> #include <iomanip>//不要忘记包含此头