数据结构平衡二叉树中的旋转

网上关于平衡二叉树的文章大多是摆几张图，然后就开始贴代码，很多具体的细节都没有说清楚，需要读者去试错。本篇文章试图说明这些细节，希望读者看了这篇文章之后，就能立马实现出来。
只说插入的情况，删除的情况和插入差不多，旋转的四个情况了解清楚了都好说。

Tree_Rebalancing.png

图片来自维基百科，作为参考讲解起来比较方便。

1. 左左情况
   注意，此时的左左情况是基于自下而上（从插入的新叶子节点往上查找）的第一个不平衡的节点。这个基准点很重要，所有的操作都与这个点有关，反而新插入的叶子节点不一定需要参与旋转。
   图中的root节点就是基准点。
   如果root的左子树pivot存在，并且pivot的左子树也存在，则满足左左情况，进行一次右旋操作，即可平衡。
   旋转实施起来比较简单，此文不再赘述。
2. 右右情况
   图中的root节点就是基准点（同上）。
   如果root的右子树pivot存在，并且pivot的右子树也存在，则满足右右情况，进行一次左旋操作，即可平衡。
3. 左右情况
   注意，此时的图有误导的可能，基准点不再是root节点，因为root节点是平衡的。
   现在的基准点是root节点的父节点，我们暂且称它为parent节点。
   如果parent的左子树root存在，并且root的右子树也存在，则满足左右情况，先进行一次左旋操作，变成第一种情况。基准点始终不变，再按第一种情况进行一次右旋操作，即可平衡。
4. 右左情况
   跟第三种情况类似，root节点的父节点parent为基准点。
   如果parent的右子树root存在，并且root的左子树也存在，则满足右左情况，先进行一次右旋操作，变成第二种情况。基准点始终不变，再按第二种情况进行一次左旋操作，即可平衡。

另外，给大家推荐一个可视化的工具，叫visualgo。
https://visualgo.net/zh/bst
如果具体怎么旋转的不好想出来和画出来，可以参考这个工具。每个值的插入都会以动画的形式呈现出来，右下角还有伪代码解释每一步操作，理解起来会很有帮助。