首页 > 编程语言 > 详细

数据结构与算法分析-c语言描述版 mark allen weiss

时间:2016-04-18 11:56:09      阅读:415      评论:0      收藏:0      [点我收藏+]

指出依序访问图4-61中的伸展树中关键字3,9,1,5后的结果。

技术分享

                                               图4-61

技术分享

1.原理


这里主要涉及到两种旋转方式:

1)之子型旋转

2)一字型旋转

这两种方式实际有一点差别:

之子型旋转是两次单旋转的组合,而且都可以看成是将目标节点父节点的选转(后面实例进行说明)

而一字型旋转时目标节点的祖父节点的的旋转后再加上父节点的旋转(后面实例进行说明)。

因此书中所指的标准AVL双旋转可以分解为两步进行。


2.习题旋转步骤:

1)3节点的访问

第一步:节点3-2-4 之字形 :父节点的旋转,因此 2-1 旋转

技术分享

技术分享

第二步:此处不能看成是3-4-10 一字节点,因为此处将标准的avl 旋转转边为了两部,因此执行上一个3-2-4 之字形的第二步:

3节点的父节点4 旋转。

技术分享

技术分享

第三步:此时只有3-10 节点,只需直接旋转父节点即可

技术分享

技术分享


2)9节点的访问

第一步:接上9-8-6 一字型,标准avl旋转后:

技术分享

技术分享

第二步:9-4-10 之字形 标准avl旋转后

技术分享

技术分享

第三步:只有父节点,没有祖父,直接旋转父节点即可

技术分享

技术分享

3)1节点的访问

第一步:1-2-3 一字型,标准avl旋转后

技术分享

技术分享

第二步:1-9 只有父节点,直接旋转父节点

技术分享

技术分享

4)5节点访问

第一步:5-6-8 一字型,标注avl旋转后:

技术分享

技术分享

第二步:5-4-3 一字型,标准avl旋转后

技术分享

技术分享

第三步:5-2-9 之字形,标准avl旋转后:

技术分享

技术分享

第四步:5-1,只有父节点

技术分享

技术分享


数据结构与算法分析-c语言描述版 mark allen weiss

原文:http://blog.csdn.net/c234jc/article/details/51177352

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!