首页 > 数据结构 > 伸展树的自顶向下伸展伪码及实例

伸展树的自顶向下伸展伪码及实例

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

下面给出伸展树的自顶向下伸展的伪码,其中的L、R分别表示左树和右树且初始值为空,M为中树且初值为原伸展树;X为待查节点,T为M的根节点。

FUNC top-down-splay
	DO
		IF X小于T THEN
			IF X等于T的左孩子 THEN 
				右连接
			ELSEIF X小于T的左孩子 THEN
				右旋
				右连接
			ELSE X大于T的左孩子 THEN
				右连接
				左连接
			ENDIF			
		ELSE X大于T THEN
			IF X等于T的右孩子 THEN
				左连接
			ELSEIF X大于T的右孩子 THEN
				左旋
				左连接
			ELSE X小于T的右孩子 THEN
				左连接
				右连接
			ENDIF
		ENDIF
	WHILE 找到X或遇到空节点
	组合左中右树
ENDFUNC

和伸展树的自底向上伸展(bottom-up splay)伪码一样,同样可以简化上一个伪码得到如下形式:

FUNC top-down-splay
	DO
		IF X小于T THEN
			IF X小于T的左孩子 THEN
				右旋
			ENDIF			
			右连接
		ELSE X大于T THEN
			IF X大于T的右孩子 THEN
				左旋
			ENDIF
			左连接
		ENDIF
	WHILE 找到X或遇到空节点
	组合左中右树
ENDFUNC

伪码中的左旋和右旋操作之前已经讲解,对于左连接和右连接可以参看上一篇文章里的伸展树的自顶向下伸展示意图(表示的是右连接,左连接是对称的)。另外,两种伸展伪码对同一伸展树进行伸展后,得到的伸展树结构不一定完全一致。
伸展树的自顶向下伸展实例(以简化的伸展伪码来示例):

图示得很清晰,应该很好懂。有一点需要说明的是左连接和右连接的新加入进来的节点的连接点在哪儿,怎么理解?对于左连接,因为新连接进来的所有节点比左树中的所有节点都要大,所以连接点应该在左树的最右边,所以应该顺着左树根节点一直往右孩子节点向下搜索,直到为空节点就是我们要找的连接点。右链接对称处理。

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


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

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

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