Python数据结构与算法——第二十九课平衡二叉树的层数平衡法插入

　　节点数平衡法，相对来说，简单一些，但它不能操作全部的平衡二叉树，而且在添加和删除时，可能增加了不必要的调整操作。为此，从平衡二叉树的定义出发形成了层数平衡法。

　　首先，要理解什么是拓扑图。两个图形充分变形后可以重叠，那么它们是同一个拓扑图。如果下图，

三角形充分变形后可以与圆形重叠，所以三角形和圆形是同一个拓扑图形。这种变形就是拓扑变换。请看下面由三个节点组成的二叉树图，

二叉树的图形是拓扑图，经过拓扑变换消除了节点左右子树不平衡（层数相差绝对值超过1）的情况。

　　如果把空指针也认为是一个连线，那么二叉树的每个节点有三条连线（是一个奇点）分别是父母节点方向、左子树节点方向和右子树节点方向。受二叉树大小顺序的规定，左右子树方向不可以相互转化或替代，因此转化只有2种情况：

　　(1)父母节点（当前节点是父母节点的右子数节点）替代左子树，原来左子树（如果有的话）比替代后的节点大，因此是替代后的节点的右子树——实际就是父母节点方向和左子树方向调换了位置。在树的拓扑图上看，是节点（上一句话中的父母节点）的右子树绕着节点逆时针旋转到父母节点方向上——左旋。最简单的左旋如下图所示。

　　(2)父母节点（当前节点是父母节点的左子数节点）替代右子树，原来右子树（如果有的话）比替代后的节点小，因此是替代后的节点的左子树——实际就是父母节点方向和右子树方向调换了位置。在树的拓扑图上看，是节点（上一句话中的父母节点）的左子树绕着节点顺时针旋转到父母节点方向上——右旋。最简单的右旋如下图所示。

　　左旋或右旋中那个不动的节点是旋转根。

　　层数平衡法

　　每插人一个节点后，首先检查是否破坏了树的平衡性，如果因插人节点而破坏了二叉查找树的平衡，则找出离插入点最近的不平衡节点，将该不平衡节点为根的子树进行旋转操作，该不平衡节点被称为旋转根，以该旋转根为根的子树称为最小不平衡子树。旋转分为左旋、右旋，分别应对右侧层数超高和左侧层数超高。

　　较复杂些的左旋操作如下图所示。

　　左旋算法逻辑：

        (1)断开旋根右子树的左子树，
        (2)断开旋根右子树，
        (3)旋根右子树上升1层，
        (4)旋根下降1层，
        (5)连接(1)旋根右子树的左子树到(2)旋根右子树，
        (6)改变(1)旋根右子树的左子树的父母指针，
        (7)把(2)旋根右子树插到旋根与它的父母节点之间，
        (8)对比旋根与旋根右子树的层级大小，旋根右子树的层级取大者，
        (9)完成。

　　右旋与左旋是轴对称关系，把左变右，把右变左就行了。

　　右旋算法逻辑：

　　(1)断开旋根左子树的右子树，

　　(2)断开旋根左子树，

　　(3)旋根左子树上升1层，

　　(4)旋根下降1层，

　　(5)连接(1)旋根左子树的右子树到(2)旋根左子树，
　　(6)改变(1)旋根左子树的右子树的父母指针，
　　(7)把(2)旋根左子树插到旋根与它的父母节点之间，
　　(8)对比旋根与旋根左子树的层级大小，旋根左子树的层级取大者，

　　(9)完成。
　　有时形成的失衡，单纯的左旋和右旋都无法恢复平衡，如下图所示。

　　左旋后，原来位置的平衡因子从-2变为2，并没有达到消除不平衡的作用。究其原因，是因为旋根的右节点的平衡因子是1造成的。因为左旋不改变旋根的右节点的左节点层数，旋根的右节点的右节点层数减少1，这样就造成旋根原来位置的平衡因子变为2。解决办法就是预右旋——左旋之前，如果发现旋根的右节点的平衡因子是1，先以旋根的右节点为旋根右旋。