首页 > 数据结构 > 伸展树介绍

伸展树介绍

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

假想这么一种情况,我们想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更短,那些查频率比较高的节点就应该经常处于比较靠近树根的位置,于是最直观的想法就是将每次查找访问的节点都放到树根处,这样再次查找该节点时将会很快的找到该节点。在每次查找访问节点之后对该树进行重构,将被查找的节点搬移到树根,这种自调整型式的二叉查找树就是splay tree(伸展树),它会沿着从某个被访问节点到树根之间的路径,通过一系列的旋转把这个被访问节点搬移到树根。

伸展树通过一系列的旋转把当前被访问节点搬移到树根,以便下次再次访问该节点时速度极快(直接访问根节点就被命中或离树根很近的位置)。为了将当前被访问节点搬移到树根,我们需要沿着查找路径做自底向上的旋转,直至该节点成为树根为止(伸展树定义的旋转是成对进行的,伸展操作不单是把当前被访问节点搬移到树根,而且还把查找路径上的每个节点的深度都大致减掉一半。)。(假设当前被访问节点为X,X的父亲节点为P(如果X的父亲节点存在),X的祖父节点为G(如果X的祖父节点存在))
每一旋转步骤都是下列三种情况之一:
1.    第一种情况:如果P是树根,则旋转连接X和P的边(这种情况是最后一步)。(如果X是左儿子就右旋,如果X是右儿子就左旋)
2.    第二种情况:如果P不是树根,而且X和P本身都是左孩子或者都是右孩子,则先旋转连接P和G的边,然后再旋转连接X和P的边。
3.    第三种情况:如果P不是树根,而且X是左孩子,P是右孩子,或者相反,则先旋转连接X和P的边,再旋转连接X和新的P的边。

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


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

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

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