AVL树的旋转!
我看书上写 AVL树 在平衡遭到破坏时,要进行旋转。 看了半天还是没看出来它是怎么转的, 什么左转90度,右转90度的,我怎么看它都没转,只看到它通过改变儿子节点跟父节点的关系,重新达到平衡。
大家跟我讲讲它真的转了吗?是怎么转的?(那个算法我可以看懂,可不清楚很多人为什么称它”旋转“)
[解决办法]
当然不是整棵树左转90度或者右转90度,不然成什么东西了?
这里说的“旋转”其实就是“通过改变儿子节点跟父节点的关系,重新达到平衡”,要说旋转也只是局部进行旋转。
算法看懂就无所谓了,这只是个习惯叫法。
下面这棵树是不平衡的:
3
/
2
/
1
但是“扭转”之后,就变得平衡了:
2
/ \
1 3
说旋转还是挺形象的。