AVL树的实现

https://www.jianshu.com/p/65c90aa1236d

https://www.cnblogs.com/vamei/archive/2013/03/21/2964092.html

关于AVL树的实现，主要借鉴上面两篇文章

但需要指出一点是，这两篇文章在什么时候使用左单旋转，什么时候使用右单旋转上面的表述都不清晰。
虽然给出的代码没有问题，但是不知其所以然。

我想了很久，总算是得出了一个比较形象的理解。

关于往哪个方向旋转的问题。
如果是树的左边失衡，就往右边转。想象一个天平要保持平衡，左边重了，那就把左边的东西往右边放。右边重了，就把东西往右边放一放。

关于是单旋转还是双旋转的问题。
左旋转时，如果插入点在旋转点的子节点（左旋转看右边的子节点）的左子树上，那就双旋转，否则单旋转。
右旋转时，如果插入点在旋转点的子节点（右旋转看左边的子节点）的右子树上，那就双旋转，否则单旋转。

总结一下，可以这样说：同侧双，异侧单。

这个“旋转点的子节点”是在插入的叶节点向根节点回溯的路径上。

本文作者： 王炎杰
本文链接： https://www.jianshu.com/p/c62dfd013b38
版权声明： 转载请注明出处！