伸展树
在上一篇博文中提到的伸展树(splay tree).其实自己也没怎么明白.在网上找了半天也没有看懂.最终找到了这个.这是加州大学伯克利分校的CS 61B数据结构的一个公开课视频.讲的清楚极了.现部分整理如下.
一.伸展树是一种平衡二叉搜索树.它可以快速的获得最近操作的项目.对于伸展树.最基本的策略是旋转(Rotation).旋转分为左旋和右旋.如下:
二.伸展树的基本操作:
1.查找(K):和普通的二叉树没什么区别.然后让查找结束的节点X成为根(splay)(不管是否找到目标K.)
2.伸展(splay X):有三种情况.
-
Zig-zag:
X是一个右节点的左节点.或者X是一个左节点的右节点.
旋转X两次.
-
Zig-zig:
X是一个左节点的左节点.或者X是一个右节点的右节点.
旋转两次.但和Zig-zag的旋转顺序有差异.先旋转X的父节点.在旋转X.
-
Zig:
X是根的子节点.
那么就是一次旋转
Zig-zag和Zig-zig都是对两层深度的操作.直到X成为根的子节点.就进行Zig操作.
下面是一个查找的例子.
首先.象普通的二叉搜索树一样.找到7.可见.7是一个右节点的右节点.那么就进行Zig-zig步骤.此时7是一个右节点的左节点.就进行Zig-zag步骤.再进行一个Zig步骤.一个查找7的操作就完成了.
3.插入(K):首先象普通的二叉搜索树一样将K插入.再将K伸展至根.
4.删除(K):象普通的二叉搜索树一样将K删除.然后将K的父节点X伸展至根.如果K没有在树内的话.那么就如同查找操作.即将最后一个访问的节点伸展至根.
这里有一个在线的示例:http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.html
另一小段功能不全的测试代码..只能打印树的深度...(摊手)(摇头)
def inorder(): d=dict() def inner_inorder(n,r): if n is None : return else: inner_inorder(n.left,r=r+1) if d.get(r) is None: d[r]=[n.key] else: d[r].append(n.key) inner_inorder(n.right,r=r+1) inner_inorder(t.root,0) return d def print_tree(): d=inorder() for i in d: print "%s"%d[i] t=SplayTree() for i in range(9): t.insert(i) print_tree(t)
2024年2月24日 15:05
Your site is truly cool and this is an extraordinary moving article