当前位置:天才代写 > tutorial > 大数据教程 > 数据结构之伸展树

数据结构之伸展树

2021-02-19 14:14 星期五 所属: 大数据教程 浏览:21

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所显示的子树。

运用区段实际操作我们可以完成线段树的一些作用,例如回应对区段的了解(最高值,极小值等)。实际能够那样完成,在每一个节点纪录有关以这一节点为根的子树的信息内容,随后了解时先获取区段,再立即载入子树的基本信息。还能够对区段开展总体改动,这还要采用与线段树相近的延迟时间标记技术,即针对每一个节点,附加纪录一个或好几个标识,表明以这一节点为根的子树是不是被开展了某类实际操作,而且这类实际操作危害他的儿子节点的信息内容值,当开展转动和别的一些实际操作时相对地将标识往下传送。

与线段树对比,屈伸树作用更强劲,它能处理下列2个线段树不可以处理的难题:

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

 

    关键字:

天才代写-代写联系方式