Splay Tree 介绍-程序员宅基地

技术标签: 数据结构与算法  

MiYu原创, 转帖请注明 : 转载自     

 

伸展树(Splay Tree)是一种二叉排序树,它能在Olog n内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
查找树的相关知识
  各种查找树存在不足。比如:对于一个有n个节点的平衡树,虽然最坏情况下每次查找的时间复杂度不会超过Ologn,但是如果访问模式不均匀,平衡树的效率就会受到影响。此外,它们还需要额外的空间来存储平衡信息。 
  这些查找树的设计目标都是减少最坏情况下单次操作时间,但是查找树的典型应用经常需要执行一系列的查找操作,此时更关心的性能指标是所有这些操作总共需要多少时间。对于此类应用,更好的目标就是降低操作的摊平时间,此处的摊平时间是指在一系列最坏情况的操作序列中单次操作的平均时间。获得摊平效率的一种方法 就是使用“自调整”的数据结构。 
  和平衡的或是其它对结构有明确限制的数据结构比起来,自调整数据结构有以下几个优点:、从摊平角度而言,它们忽略常量因子,因此绝对不会比有明确限制的数据结构差。而且由于它们可以根据使用情况进行调整,于是在使用模式不均匀的情况下更加有效。、由于无需存储平衡或者其它的限制信息,它们所需的空间更小。、它们的查找和更新算法概念简单,易于实现。 
  当然,自调整结构也有潜在的缺点:、它们需要更多的局部调整,尤其是在查找期间。(那些有明确限制的数据结构仅需在更新期间进行调整,查找期间则不用)、一系列查找操作中的某一个可能会耗时较长,这在实时应用程序中可能是个不足之处。
伸展树存在的意义
  假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法, 在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。
已知重构方法与伸展树的重构方法
  先前,已经存在两种重构方法:、单旋:在查找完位于节点x中的条目i之后,旋转链接x和其父节点的边。(除非x就是树根)、搬移至树根:在查找完位于节点x中的条目i之后,旋转链接x和其父节点的边,然后重复这个操作直至x成为树根。 
  splay tree的重构方法和搬移至树根的方法相似,它也会沿着查找路径做自底向上的旋转,将被查找条目移至树根。但不同的是,它的旋转是成对进行的,顺序取决于查找路径的结构。为了在节点x处对树进行splay操作,我们需要重复下面的步骤,直至x成为树根为止:、第一种情况:如果x的父节点px是树根,则旋转连接x和px的边。(这种情况是最后一步)、第二种情况:如果px不是树根,而且x和px本身都是左孩子或者都是右孩子,则先旋转连接px和x的祖父节点gx的边,然后再旋转连接x和px的边。、第三种情况:如果px不是树根,而且x是左孩子,px是右孩子,或者相反,则先旋转连接x和px的边,再旋转连接x和新的px的边。 
  在节点x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树根,而且还把查找路径上的每个节点的深度都大致减掉了一半。
伸展树(Splay Tree)支持的操作
  具体操作包括:、accessit如果i在树t中,则返回指向它的指针,否则返回空指针。为了实现accessit,可以从树t的根部向下查找i。如果 查找操作遇到了一个含有i的节点x,就在x处进行splay操作,并返回指向x的指针,访问结束。如果遇到了空指针,表示i不在树中,此时就在最后一个非 空节点处进行splay操作,然后返回空指针。如果树是空的,将忽略掉splay操作。、insertit将条目i插入树t中(假设其尚不存在)。为了实现insertit,首先执行splitit,然后把t换成一个由新的包含有i的根节点组成的树,这个根节点的左右子树分别是split返回的树t1和t2。、it从树t中删除条目i(假设其已经存在)。为了实现it,首先执行accessit,然后把t换成其左子树和右子树join之后的新树。、joint1t2将树t1和t2合并成一棵树,其中包含之前两棵树的所有条目,并返回合并之后的树。这个操作假设t1中的所有条目都小于t2 中的条目,操作完成之后会销毁t1和t2。为了实现joint1t2,首先访问t1中最大的条目i。访问结束之后,t1的根节点中包含的就是i,它 的右孩子显然为空。于是把t2作为这个根节点的右子树并返回完成之后的新树即可实现join操作。、splitit构建并返回两棵树t1和t2,其中t1包含t中所有小于等于i的条目,t2包含t中所有大于i的条目。操作完成之后销毁t。为 了实现splitit,首先执行accessit,然后根据新根节点中的值是大于还是小于等于i来切断这个根节点的左链接或右链接,并返回形 成的两棵树。 
  另外insert和方法有更好的实现,时间复杂度更小:、inserti t查找i,把遇到的空指针替换成一个含有i的新节点,然后再在新节点处对树进行splay操作。、i t查找含有i的节点,设此节点为x,其父节点为y。把x的左右子树合并之后替换掉x,然后再从y处进行splay操作。
伸展树的优势
  由于Splay Tree仅仅是不断调整,并没有引入额外的标记,因而树结构与标准BST没有任何不同,从空间角度来看,它比Treap、RedBlack Tree、AVL要高效得多。因为结构不变,因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响,因而它也提供了BST中最丰富的功能,包括快速的拆分和合并(这里指的是将原树拆分成两棵子树,其中一棵子树所有节点都比另一子树小,以及它的逆过程),并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定,和Treap基本相当

转载于:https://www.cnblogs.com/MiYu/archive/2010/11/12/1875490.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30718391/article/details/99143926

智能推荐

c#中用循环语句输出九九乘法表_c# 通过for循环输出10 20 30-程序员宅基地

文章浏览阅读5.2k次,点赞3次,收藏5次。 一些基础的逻辑运算,自己也是初学者,记录一下,全是自己的一些见解,大神请轻喷输出结果:代码:public void ChengFaBiao(){ for (int a = 1;a<=9;a++){ for (int b = 1; b <= a; b++) { Console.Write (b + "*" + a + "=" + a * b+" "); ..._c# 通过for循环输出10 20 30

AGPBI: {"kind":"error","text":"Cannot fit requested classes in a single dex file (# methods: 67300 >-程序员宅基地

文章浏览阅读2.8k次。错误信息 AGPBI: {"kind":"error","text":"Cannot fit requested classes in a single dex file (# methods: 67300 > 65536)","sources":[{}],"tool":"D8"}com.android.builder.dexing.DexArchiveMergerExce..._agpbi: {"kind":"error","text":"cannot fit requested classes in a single dex

python之windrose风向玫瑰图的用法_windroseaxes.from_ax-程序员宅基地

文章浏览阅读2w次,点赞4次,收藏47次。1.安装A package is available and can be downloaded from PyPi and installed using:$ pip install windroseInstall latest development version$ pip install git+https://github.com/python-windrose/wi..._windroseaxes.from_ax

pxe linux 配置文件,(六)PXE技术篇--pxelinux 的配置文件-程序员宅基地

文章浏览阅读1k次。pxe 启动引导器pxelinux.0 在 syslinux 包中, 把它拷贝到 /var/lib/tftpboot/ 下, 客户机会从此目录读取该文件安装yum -y install syslinux复制文件cp /usr/share/syslinux/pxelinux.0 /var/lib/tftpboot我们告诉客户端使用 vmlinuz 作为内核, 并且使用 initrd.img 作为初..._pxelinux.0文件在什么地方

图解:深度优先搜索与广度优先搜索及其六大应用_请叙述广度优先搜索和深度优先搜索的特点和使用场合-程序员宅基地

文章浏览阅读5.9k次,点赞13次,收藏46次。图算法第二篇 深度优先搜索与广度优先搜索及其应用约定:本文所有涉及的图均为无向图,有向图会在之后的文章涉及1.图的存储方式我们首先来回顾一下图的存储方式:邻接矩阵和邻接表。为了实现更好的性能,我们在实际应用中一般使用邻接表的方式来表示图。具体的实现代码为:package Graph;import java.util.LinkedList;public class Graph{ private final int V;//顶点数目 private int E;/.._请叙述广度优先搜索和深度优先搜索的特点和使用场合

Ubuntu登录界面输入正确密码依然无法登陆_ubuntu advantage token-程序员宅基地

文章浏览阅读1w次。Ubuntu登录界面输入正确密码依然无法登陆Ubuntu14出现了2次这样的情况,开机进入登录页面,输入正确的密码后,再次回到登录页面,一直这样无法进入Ubuntu桌面。 在网上找到了解决方案,按Ctrl+Alt+F1(F1~F6一共6个终端可用),删除home目录下的.Xauthor*文件即可。命令行下: reboot命令重启 startx可以启动图形桌面_ubuntu advantage token

随便推点

进程环境相关(APUE)_linux 进程 文件 apue-程序员宅基地

文章浏览阅读90次。就是一个main程序的运行开始到结束的一些介绍,运行环境的一些,比较简单的一章,里面那个setjmp和longjmp函数那里有点难懂,记得后面信号那里还出现了。mian函数背后进程(main函数)的开始进程的终止的方式(8种(其中5种正常))三个正常终止进程的函数:exit、_exit和_Exit,三者有什么不同,参数代表什么(终止状态)什么情况下终止状态是未定义的,什么情况下终止状态..._linux 进程 文件 apue

《Linux从0到99》七 进程地址空间_99在内存中的地址-程序员宅基地

文章浏览阅读108次。地址空间1. 什么是地址空间?2. 虚拟地址空间出现的原因3. 地址空间的工作方式4. 地址空间的三种管理方式01 分页式内存管理(提高内存利用率)02 分段式内存管理(便于管理)03 段页式内存管理(既提高了内存利用率,又便于内存管理)1. 什么是地址空间?地址空间(address space) 表示任何一个计算机实体所占用的内存大小。比如外设、文件、服务器或者一个网络计算机。地址空间包括物理空间以及虚拟空间。物理地址 (physical address): 放在寻址总线上的地址。放在寻址总线上_99在内存中的地址

php mysql 排名算法_PHP实现四种基础排序算法的运行时间比较(推荐)-程序员宅基地

文章浏览阅读120次。许多人都说算法是程序的核心,算法的好坏决定了程序的质量。作为一个初级phper,虽然很少接触到算法方面的东西。但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具。下面通过本文给大家介绍PHP实现四种基础排序算法的运行时间比较,一起看下吧。废话不多说了,直接给大家贴代码了。具体代码如下所示:/*** php四种基础排序算法的运行时间比较* @authors Jesse (jesse152@..._for($i=0;$i

YOLOV3代码详解_b, target_labels = target[:, :2].long().t()-程序员宅基地

文章浏览阅读7.5k次,点赞16次,收藏126次。代码分析:https://github.com/eriklindernoren/PyTorch-YOLOv3论文地址:https://pjreddie.com/media/files/papers/YOLOv3.pdf注:本次分析的代码是以上给出的网址,全部根据自己的理解写的,如有不足,还请指正。1、datasets.py因为所有模型都包括数据加载,模型载入,训练和测试等,所以先从数据的载..._b, target_labels = target[:, :2].long().t()

均衡技术matlab,无线通信均衡技术matlab仿真.doc-程序员宅基地

文章浏览阅读304次。无线通信均衡技术matlab仿真现给出迫零均衡(ZF)、最小均方误差均衡中的最小均方算法(LMS)的matlab程序,理解各程序,完成以下习题。将程序运行结果及各题目的解答写入word中:用matlab分别运行“main_zf.m”和“main_lms.m”(a)在程序中标注“注释”处加上注释(英文或中文)。(b)写出这两种算法实现的流程。(c)运行程序,会得到关于信号的一系列图形,包括信号序列图..._matlab信道均衡代码

Python 绘制散点密度图_c#计算二维散点的密度热度值-程序员宅基地

文章浏览阅读4.7k次,点赞8次,收藏81次。matplotlib、seaborn绘制散点密度图_c#计算二维散点的密度热度值

推荐文章

热门文章

相关标签