首页 > 数据结构 > 伸展树的自顶向下伸展(top-down splay)

伸展树的自顶向下伸展(top-down splay)

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

假设在当前伸展树中的X节点处进行伸展,X的父亲节点为P(X)(如果X的父亲节点存在),X的祖父节点为G(X)(如果X的祖父节点存在)。
从前面的讲述,我们知道自底向上伸展的方法是在完全查找完之后再进行的伸展操作(如果找到待查节点X,就在节点X处进行伸展操作;如果未找到待查节点X即遇到了空节点,就在最后一个非空节点处进行伸展操作),而自顶向下伸展将在节点查找的过程中就同时进行着伸展操作。
自顶向下伸展操作将伸展树分为三部分:
左树:包含所有已经知道比待查节点X小的节点。
右树:包含所有已经知道比待查节点X大的节点。
中树:包含所有其它节点。
在中树自根向下进行节点查找(每次向下比较两个节点),根据查找情况将中树中的节点移动(此处的移动是指将节点和中树的连接断开,而将节点连接到左或右树的适当位置。)到左树或右树(如有必要则会先对中树进行旋转再进行节点移动)。
初始状态时,左树和右树都为空,而中树为整个原伸展树。随着查找的进行,左树和右树会因节点的逐渐移入变大,中树会因节点的逐渐移出变小。最后查找结束(找到或遇到空节点)时组合左中右树并是伸展树自顶向下伸展方法的最终结果。

下图所给旋转为b的左右子树都存在时,并且图中只画出了待查节点比a小的情况,比a大的情况可由对称关系推出。伸展树的自顶向下伸展示意图:

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


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

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

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