平衡二叉树如何旋转使自己保持平衡

为了排除动态查找表中不同的数据排列方式对算法性能的影响，需要考虑在不会破坏二叉排序树本身结构的前提下，将二叉排序树转化为平衡二叉树。
例如，使用上一节的算法在对查找表 {13，24，37，90，53}构建二叉排序树时
当插入13和24时，二叉排序树此时还是平衡二叉树:

当继续插入37时，生成的二叉排序树如下图(a)，平衡二叉树的结构被破坏，此时只需要对二叉排序树做旋转操作(如图3(b)) ,即整棵树以结点24为根结点，二叉排序树的结构没有破坏，同时将该树转化为了平衡二叉树:

当二叉排序树的平衡性被打破时，就如同扁担的两头出现了一头重一头轻的现象，如图上(a)所示，此时只需要改变扁担的支撑点(树的树根)，就能使其重新归为平衡。实际上图中的(b)是对(a)的二叉树做了一个向左逆时针旋转的操作。

继续插入90和53后，二叉排序树如下图(a)所示，导致二叉树中结点24和37的平衡因子的绝对值大于1，整棵树的平衡被打破。此时，需要做两步操作:

1. 如图(b)所示，将结点53和90整体向右顺时针旋转，使本该以90为根结点的子树改为以结点53为根结点;
2. 如图(c)所示，将以结点37为根结点的子树向左逆时针旋转，使本该以37为根结点的子树，改为以结点53为根结点;

做完以上操作，即完成了由不平衡的二叉排序树转变为平衡二叉树。
当平衡二叉树由于新增数据元素导致整棵树的平衡遭到破坏时，就需要根据实际情况做出适当的调整，假设距离插入结点最近的"不平衡因子"为a。则调整的规律可归纳为以下4种情况:

• 单向右旋平衡处理∶若由于结点a的左子树为根结点的左子树上插入结点，导致结点a的平衡因子由1增至2，致使以a为根结点的子树失去平衡，则只需进行一次向右的顺时针旋转，如下图这种情况:

• 单向左旋平衡处理∶如果由于结点a的右子树为根结点的右子树上插入结点，导致结点a的平衡因子由-1变为-2，则以a为根结点的子树需要进行一次向左的逆时针旋转，如下图这种情况∶

• 双向旋转（先左后右)平衡处理∶如果由于结点a的左子树为根结点的右子树上插入结点，导致结点a平衡因子由1增至2，致使以a为根结点的子树失去平衡，则需要进行两次旋转操作，如下图这种情况:

注意:上图中插入结点也可以为结点C的右孩子，则(b)中插入结点的位置还是结点C右孩子，(c)中插入结点的位置为结点A的左孩子。

• 双向旋转(先右后左)平衡处理:如果由于结点a的右子树为根结点的左子树上插入结点,导致结点a平衡因子由-1变为-2，致使以a为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作，如下图这种情况:

注意:上中插入结点也可以为结点c的右孩子，则(b)中插入结点的位置改为结点B的左孩子，(c)中插入结点的位置为结点B的左孩子。

在对查找表(13，24，37，90，53}构建平衡二叉楸时，由于符合第4条的规律，所以进行先右旋后左旋的处理，最终由不平衡的二叉排序树转变为平衡二叉树。