首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

AVL树的旋转!该如何处理

2012-02-26 
AVL树的旋转!我看书上写 AVL树 在平衡遭到破坏时,要进行旋转。看了半天还是没看出来它是怎么转的, 什么左转

AVL树的旋转!
我看书上写 AVL树 在平衡遭到破坏时,要进行旋转。 看了半天还是没看出来它是怎么转的, 什么左转90度,右转90度的,我怎么看它都没转,只看到它通过改变儿子节点跟父节点的关系,重新达到平衡。  
  大家跟我讲讲它真的转了吗?是怎么转的?(那个算法我可以看懂,可不清楚很多人为什么称它”旋转“)

[解决办法]
当然不是整棵树左转90度或者右转90度,不然成什么东西了?
这里说的“旋转”其实就是“通过改变儿子节点跟父节点的关系,重新达到平衡”,要说旋转也只是局部进行旋转。
算法看懂就无所谓了,这只是个习惯叫法。

下面这棵树是不平衡的:
3
/
2
 /
1
但是“扭转”之后,就变得平衡了:
2
 / \
1 3
说旋转还是挺形象的。

热点排行