首页 > 数据结构 > 伸展树的自底向上伸展(bottom-up splay)

伸展树的自底向上伸展(bottom-up splay)

2011年11月20日 发表评论 阅读评论 2,741 次浏览

假设在当前伸展树中的X节点处进行伸展,X的父亲节点为P(X)(如果X的父亲节点存在),X的祖父节点为G(X)(如果X的祖父节点存在)。伸展树的自底向上伸展伪码为:

FUNC bottom-up-splay
	DO
		IF X是P(X)的左孩子节点 THEN
			IF G(X)为空 THEN 
				右旋P(X)
			ELSEIF P(X)是G(X)的左孩子节点 THEN
				右旋G(X)
				右旋P(X)
			ELSE
				右旋P(X)
				左旋P(X)(注意:经过上一次右旋后此处的P(X)和上一个P(X)不一样)
			ENDIF			
		ELSE X是P(X)的右孩子节点 THEN
			IF G(X)为空 THEN 
				左旋P(X)
			ELSEIF P(X)是G(X)的右孩子节点 THEN
				左旋G(X)
				左旋P(X)
			ELSE
				左旋P(X)
				右旋P(X) (注意:经过上一次左旋后此处的P(X)和上一个P(X)不一样)
			ENDIF
		ENDIF
	WHILE P(X)不为空
ENDFUNC

仔细分析各种情况下的旋转,对于X、P、G成z字型排列的旋转情况(上面所说的三种情况中的第三种),其第二次旋转可以延后进行,这样就可以使得第三种情况和第一种情况统一起来而简化编程,从而得到简化后的伪代码,结果如下所示:

FUNC bottom-up-splay
	DO
		IF X是P(X)的左孩子节点 THEN
			IF P(X)是G(X)的左孩子节点 THEN
				右旋G(X)
			ENDIF
			右旋P(X)
		ELSE X是P(X)的右孩子节点 THEN
			IF P(X)是G(X)的右孩子节点 THEN
				左旋G(X)
			ENDIF
			左旋P(X)
		ENDIF
	WHILE P(X)不为空
ENDFUNC

对于伪码中的左旋和右旋操作,之前就已经图示过(虽然没有明说),如果还不是很清楚则请看下图示:

另外在单个的旋转过程中,如果G(X)还有父节点(假设为O)则先断开G(X)与O之间的连接即只考虑以G(X)为根节点的子树(假设为T),旋转完之后再连接节点X和节点O即X占据旋转前G(X)的位置(注意:旋转后X变成了T的根节点)。
最后,值得一说的是,两种伸展伪码虽然都可以对伸展树进行伸展操作,但是对于同一伸展树在同一节点开始伸展最后得到的伸展树结构不一定完全一致(接下来的实例讲解会看到这一情况),因为第二种伪码实现使得伸展树的旋转可能不再是成对进行。

转载请保留地址:http://www.lenky.info/archives/2011/11/210http://lenky.info/?p=210


备注:如无特殊说明,文章内容均出自Lenky个人的真实理解而并非存心妄自揣测来故意愚人耳目。由于个人水平有限,虽力求内容正确无误,但仍然难免出错,请勿见怪,如果可以则请留言告之,并欢迎来讨论。另外值得说明的是,Lenky的部分文章以及部分内容参考借鉴了网络上各位网友的热心分享,特别是一些带有完全参考的文章,其后附带的链接内容也许更直接、更丰富,而我只是做了一下归纳&转述,在此也一并表示感谢。关于本站的所有技术文章,欢迎转载,但请遵从CC创作共享协议,而一些私人性质较强的心情随笔,建议不要转载。

法律:根据最新颁布的《信息网络传播权保护条例》,如果您认为本文章的任何内容侵犯了您的权利,请以Email或书面等方式告知,本站将及时删除相关内容或链接。

分类: 数据结构 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.