数据结构之伸展树详解

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《运用伸展树解决数列维护问题》

(0)

相关推荐

  • 数据结构之堆详解

    1. 概述 堆(也叫优先队列),是一棵完全二叉树,它的特点是父节点的值大于(小于)两个子节点的值(分别称为大顶堆和小顶堆).它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等. 2. 堆的基本操作 堆是一棵完全二叉树,高度为O(lg n),其基本操作至多与树的高度成正比.在介绍堆的基本操作之前,先介绍几个基本术语: A:用于表示堆的数组,下标从1开始,一直到n PARENT(t):节点t的父节点,即floor(t/2) RIGHT(t):节点t的左孩子节点,即:2*t LEFT(t

  • 数据结构之AVL树详解

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

  • 数据结构之Treap详解

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

  • 数据结构之伸展树详解

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

  • Java数据结构之线段树详解

    目录 介绍 代码实现 线段树构建 区间查询 更新 总结 介绍 线段树(又名区间树)也是一种二叉树,每个节点的值等于左右孩子节点值的和,线段树示例图如下 以求和为例,根节点表示区间0-5的和,左孩子表示区间0-2的和,右孩子表示区间3-5的和,依次类推. 代码实现 /** * 使用数组实现线段树 */ public class SegmentTree<E> { private Node[] data; private int size; private Merger<E> merge

  • 数据结构 红黑树的详解

    数据结构 红黑树的详解 红黑树是具有下列着色性质的二叉查找树: 1.每一个节点或者着红色,或者着黑色. 2.根是黑色的. 3.如果一个节点是红色的,那么它的子节点必须是黑色. 4.从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点. 下面是一棵红黑树. 1.自底向上插入 通常把新项作为树叶放到树中.如果我们把该项涂成黑色,那么违反条件4,因为将会建立一条更长的黑节点路径.因此这一项必须涂成红色.如果它的父节点是黑色的,插入完成.如果父节点是红色的,那么违反条件3.在这种情况下我们

  • Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

  • java 数据结构并查集详解

    目录 一.概述 二.实现 2.1 Quick Find实现 2.2 Quick Union实现 三.优化 3.1基于size的优化 3.2基于rank优化 3.2.1路径压缩(Path Compression ) 3.2.2路径分裂(Path Spliting) 3.2.3路径减半(Path Halving) 一.概述 并查集:一种树型数据结构,用于解决一些不相交集合的合并及查询问题.例如:有n个村庄,查询2个村庄之间是否有连接的路,连接2个村庄 两大核心: 查找 (Find) : 查找元素所在

  • Python数据结构之递归可视化详解

    目录 1.学习目标 2.递归的调用 3.递归可视化 3.1 turtle 库简介 3.1 递归绘图 1.学习目标 递归函数是直接调用自己或通过一系列语句间接调用自己的函数.递归在程序设计有着举足轻重的作用,在很多情况下,借助递归可以优雅的解决问题.虽然使用递归可以快速的解决一些难题,但由于递归的抽象性,使递归难以掌握.为了更好的理解递归函数背后的思想,本节主要通过可视化方式来了解递归函数的执行步骤. 通过本节学习,应掌握以下内容: 提高对递归的理解 利用可视化理解递归函数背后的思想 2.递归的调

  • Java数据结构之堆(优先队列)详解

    目录 堆的性质 堆的分类 堆的向下调整 堆的建立 堆得向上调整 堆的常用操作 入队列 出队列 获取队首元素 TopK 问题 例子 数组排序 堆的性质 堆逻辑上是一棵完全二叉树,堆物理上是保存在数组中 . 总结:一颗完全二叉树以层序遍历方式放入数组中存储,这种方式的主要用法就是堆的表示. 并且 如果已知父亲(parent) 的下标, 则: 左孩子(left) 下标 = 2 * parent + 1; 右孩子(right) 下标 = 2 * parent + 2; 已知孩子(不区分左右)(child

  • Java数据结构之KMP算法详解以及代码实现

    目录 暴力匹配算法(Brute-Force,BF) 概念和原理 next数组 KMP匹配 KMP全匹配 总结 我们此前学了前缀树Trie的实现原理以及Java代码的实现.Trie树很好,但是它只能基于前缀匹配实现功能.但是如果我们的需求是:一个已知字符串中查找子串,并且子串并不一定符合前缀匹配,那么此时Trie树就无能为力了. 实际上这种字符串匹配的需求,在开发中非常常见,例如判断一个字符串是否包括某些子串,然后进行分别的处理. 暴力匹配算法(Brute-Force,BF) 这是最常见的算法字符

  • ES6新增数据结构WeakSet的用法详解

    WeakSet和Set类似,同样是元素不重复的集合,它们的区别是WeakSet内的元素必须是对象,不能是其它类型. 特性: 1.元素必须是对象. 添加一个number类型的元素. const ws = new WeakSet() ws.add(1) 结果是报类型错误. TypeError: Invalid value used in weak set 添加一个对象. const ws = new WeakSet() var a = {p1:'1', p2:'2'} ws.add(a) conso

随机推荐