文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > BST拓展与伸展树(splay)一日通
侵权投诉

BST拓展与伸展树(splay)一日通

BST拓展与伸展树(splay)一日通 by zkw, May 17, 2009, 6:44 am

BST 是 OI 中一个常用的数据结构,主要支持的操作是动态维护一个有序表,从而支持字典,前驱,后继,中序遍历,优先队列等等多种操作。如果在域中维护了子树的 size,还可以支持查找第 k 大的数,询问名次等等附加功能。伸展树(Sleator and Tarjan, 1985)是 BST 的一个变种,可以自调整以维护平衡,并支持根据需要随时把任意节点旋转到根(称为 splay 操作),从而很好的支持了分裂合并等操作,从某种意义上(详见下文)也简化了思维和编程的复杂度。由于 splay 操作的迅速而优美,伸展树不仅可以维护有序表,还可以放弃关键字的有序性,像块状链表一样维护一个一般的序列(这是一般的 BST 甚至其他平衡二叉树难于做到的),支持块状链表的大多数方法,并拥有更低的理论复杂度和实际代码量。另外,splay 是唯一支持稳定排序的平衡二叉树,可以妥善处理关键字相同的元素(按照插入顺序有序),在输出时可以选择返回其中最近插入、最远插入的,或是直接返回整个区间。

1. 伸展树的基本操作与应用(参见国家集训队杨思雨前辈的论文或 The Magical Splay by sqybi)

这里有几个需要注意的地方:

(1) 自底向上的实现中可以很轻易的维护 size 等附加信息,操作实现也更像传统的 BST,只需在每次操作完成后额外执行一次 splay 操作,将对应的节点旋转到根即可。

(2) 只用 zig 和 zag 的确可以实现伸展树的所有操作,但这时 splay 会丧失自调整平衡的特性。(基本退化成 BST)但是可以证明 zig+zag=zigzag,所以只需要 zig, zag, zigzig, zagzag 就可以实现一个实用的伸展树了。考虑对称性就是两种操作:zig 和 zigzig,称之为单旋和双旋。

2. 自顶向下伸展树

不再拘泥于传统 BST 的操作方式(逐层向下查找),任何时刻正在访问或操作的节点都是整棵树的根。显然查找过程和 splay 过程已经合而为一了。

为了实现新的查找过程,我们维护两棵临时树,分别代表未来树根的左右子树,初始为空。这里左边的临时树又可以看成是一些没有右儿子的子树串成的链表,右边亦然。每次前进时比较两层关键字,前进方向一致(都是向左或都是向右)执行双旋,否则执行单旋。 单旋操作(以向左走为例):左儿子变成新的根,原来的根没有了左儿子,正好挂到右临时树下面。

双旋操作(以向左走为例):左孙子变成新的根,左儿子挂到右临时树下面,把它的右儿子送给根当左儿子,拿根来当它的右儿子。

当查找完成的时候,把左儿子挂到左临时树下面,右儿子挂到右临时树下面,拿临时树做新的儿子。

简约高效的插入、删除:先查找键值旋到根,然后……在根旁边插入元素……删除根……不用我说了吧,很简单(还不懂就看 code)

优点:简单(不存父亲指针),速度快(常数小一半以上),优美(整个结构中本质只有一种操作:splay,别的操作只是衍生产品),非递归(栈溢?不怕不怕啦)。

3. Code Trick

(1) 注意到 size 域本质上是需要自底向上的,自顶向下的实现中难以维护。如果像自

第1页

你可能喜欢

热门文档

相关文档

  • BST拓展与伸展树(splay)一日通

    BST拓展与伸展树(splay)一日通BST拓展与伸展树(splay)一日通隐藏>> BST拓展与伸展树(splay)一日通 BST 是 OI 中一个常用的数据结构,主要支持的操作是动态...

  • 算法总结 伸展树Splay

    算法总结 伸展树Splay_计算机软件及应用_IT/计算机_专业资料。伸展树(Splay ... BST 拓展与伸展树 (Spla... 5页 免费 Splay树及其应用 26页 免费 算法...

  • splay伸展树

    4.伸展树(Splay Tree)支持的操作伸展操作 Splay(x,S)是在保持伸展树有序性...因而树结构与标准 BST 没有任何 不同,从空间角度来看,它比 Treap、Red-Black...

  • 伸展树_splay_tree

    伸展操作Splay(x,S): 把x旋转到树根, 同时保持 树是一棵合法的BST splay作为一个二叉排序树所具有特点用一句来 概述就是“可以让你把指的结点放在树根的位 ...

  • Splay Tree – 伸展树

    Splay Tree – 伸展树 August 9, 2006 8:36 · Filed under SEO, 技术... BST 拓展与伸展树 (Spla... 5页 免费 第5章树(Tree)1 暂无评价 42页 ...

  • splay(伸展树)代码,自底向上实现

    BST拓展与伸展树(splay)... 4页 2下载券 【伸展树、splay】基本操... ... splay代码,自底向上实...

  • 伸展树 splay tree

    伸展树 splay tree_IT/计算机_专业资料。今日推荐 180份文档 ... splay(伸展树)代码,自底... 2页 免费 BST 拓展与伸展树 (Spla... 5页...

  • 伸展树的原理及应用

    一、伸展操作 Splay(x,S) 伸展操作 Splay(x,S)是在保持伸展树有序性的...(x:integer; var S:Tpoint):Tpoint; Var p:Tpoint; Begin p:=BST_...

  • 伸展树

    BST 拓展与伸展树 (Splay)... 5页 免费 伸展树操作详解 5页 2财富值...伸展树的自底向上伸展(bottom-up splay)伪码假设在当前伸展树中的 X 节点处...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email