一、平衡二叉树

平衡二叉树，是一种二叉排序树，其中每一个结点的左子树和右子树的高度差最多等于 1

1. 概念

• 平衡因子（Balance Factor）

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子。
平衡二叉树上所有结点的平衡因子只可能是 -1、0、1。

平衡二叉树

2. 最小不平衡子树

距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，称为最小不平衡子树。

最小不平衡子树

如上图所示：新插入结点 37 时，距离他最近的平衡因子绝对值超过 1 的结点是 58（58 结点左子树高度是 3 右子树高度是 1），所以从 58 开始以下的子树为最小平衡子树

3. 平衡二叉树实现原理

举例：
用 [3,2,1,4,5,6,7,10,9,8] 这个数组组成一个平衡二叉树。

下图图1 中。已经插入 3 个数，此时发现根结点的平衡因子变为了 2。已经是最小不平衡子树了。所以需要右转（左子树 - 右子树 = 正数；顺势转旋转）。如下图图2。

然后插入 4 数字。如下图图3。此时的平衡因子是 -1 符合平衡二叉树。

继续插入 5 数字。如下图图4。此时平衡被打破。结点 3 是最小不平衡子树。所以需要向左转（左子树 - 右子树 = 负数：逆时针旋转）。如下图图5。

最简单的最小不平衡子树旋转

继续插入数字 6 这时候发现根结点的平衡因子变为了 -2 （左子树 1 - 右子树 3）。需要逆时针旋转（左子树 - 右子树 = 负数：逆时针旋转）。如下图图6

旋转后发现 2 结点要放到 4 结点左子树，然而 4 结点本身存在左子树。因为这个时候 4 结点的左子树肯定比 2 结点大。所以放在 2 结点的右边。如下图图 7

继续插入数字 7 在6 结点的右子树上。5 结点的平衡因子就变为了 -2 逆时针旋转（左子树 - 右子树 = 负数：逆时针旋转）。结果如下图图8

旋转后子树冲突

继续插入数字 10 。平衡没有被打破。

继续插入数字 9 。发现平衡被打破，最小平衡子树的节点是 7 结点，最小平衡因子是 -2。应该逆时针选择（左子树 - 右子树 = 负数：逆时针旋转）。但是逆时针旋转完会发现，它不符合排序树，右子树比上级结点小。如下图图9

错误旋转

如何旋转呢？

看 7 结点的平衡因子是 -2 ，而 10 结点的平衡因子是 1 。

前面的所有旋转平衡因子要不都是正数，要不都是负数，所以先要统一两个结点平衡因子的正负号。

先旋转 10 结点子树。因为平衡因子是 1 所以顺时针转，然后在旋转最小平衡子树。如下图图10 。

统一符号旋转

继续插入数字 8。如下图图11

会发现 6 结点的平衡因子是 -2，而 9 结点的平衡因子是 1。

先旋转 9 结点的子树。9 结点的平衡因子是 1 所以顺时针（左子树 - 右子树 = 正数；顺势转旋转）。如下图图11

旋转后因为 7 结点有右子树，9 结点也有右子树，所以 7 结点右子树，加入 9 结点左子树。

然后在 6 结点和 7结点符号相同，如下图图12。6 结点平衡因子是 -2 所以逆时针旋转（左子树 - 右子树 = 负数：逆时针旋转）最终如下图图13

统一符号旋转

4. 平衡二叉树 Python 算法

• 结点类

这里只是多加了一个 bf 平衡因子参数

class TreeNode(object):

    def __init__(self, val, lchild=None, rchild=None):
        self.val = val
        self.lchild = lchild
        self.rchild = rchild

        # 平衡因子，平衡二叉树用。默认 0 平衡
        self.bf = 0

    def __repr__(self):
        if self.val is None:
            return "None"
        return "{val: %s, l: %s, r: %s, bf: %s}" % (self.val, self.lchild, self.rchild, self.bf)

• 最简单的左旋和右旋（图 1 到 图 5）

这里只是旋转，不一定平衡

class AVLTree():

    def __init__(self):
        self.lh = 1  # 左高
        self.eh = 0  # 平等
        self.rh = -1  # 右高

    # 最小不平衡子树 右旋转 -- 顺时针 --- 平衡因子正数
    def right(self, tree):
        temp_node = copy.deepcopy(tree)

        # 取出树 tree 的左子树r
        l = temp_node.lchild
        # 将树 temp_node 左子树改为 l 的右子树
        temp_node.lchild = l.rchild
        # 在将 l 的右子树 赋值为 temp_node
        l.rchild = temp_node
        tree.val = l.val
        tree.lchild = l.lchild
        tree.rchild = l.rchild
        tree.bf = l.bf

    # 最小不平衡子树 左旋转 -- 逆时针 --- 平衡因子负数
    def left(self, tree):
        temp_node = copy.deepcopy(tree)

        r = temp_node.rchild
        temp_node.rchild = r.lchild
        r.lchild = temp_node

        tree.val = r.val
        tree.lchild = r.lchild
        tree.rchild = r.rchild
        tree.bf = r.bf

这里有解释一下 deepcopy 深拷贝。
因为在后面的插入时候使用递归的方法，不想 return。
这里想直接修改传进来的 tree 这个树对象。
如果这里使用 tree = r 实际上是修改的旋转函数的内部变量 tree， 而不是 tree 对象。
这里修改 tree 对象里面的内容，这样 python 认为你在修改 tree 对象。而不是函数它自己的参数。

下图是右旋的一个图示。图中标记变量的变化过程，和平衡因子的变化

右旋转

• 平衡旋转

左平衡旋转和右平衡旋转

    
    def left_balance(self, tree):

        # l 指向树的左子树根结点
        l = tree.lchild

        if l.bf == self.lh:
            # 新结点插入在树的左结点的左子树上，要右旋处理
            tree.bf = l.bf = self.eh
            self.right(tree)

        if l.bf == self.rh:
            # 新结点插入在树的左结点的右子树上，要两次旋转处理

            # lr 指向树的右结点的右结点
            lr = l.rchild
            if lr.bf == self.lh:
                tree.bf = self.rh
                l.bf = self.eh

            if lr.bf == self.eh:
                tree.bf = l.bf = self.eh

            if lr.bf == self.rh:
                tree.bf = self.eh
                l.bf = self.lh

            lr.bf = self.eh
            self.left(tree.lchild)
            self.right(tree)

    def right_balance(self, tree):

        r = tree.rchild
        if r.bf == self.rh:
            tree.bf = r.bf = self.eh
            self.left(tree)

        if r.bf == self.eh:
            tree.bf = r.bf = self.eh

        if r.bf == self.lh:
            rl = r.lchild

            if rl.bf == self.lh:
                tree.bf = self.eh
                r.bf = self.rh

            if rl.bf == self.eh:
                tree.bf = r.bf = self.eh

            if rl.bf == self.rh:
                tree.bf = self.lh
                r.bf = self.eh
            rl.bf = self.eh
            self.right(tree.rchild)
            self.left(tree)

下图是左平衡旋转变量和平衡因子的变化

下图是右平衡旋转变量和平衡因子的变化

• 插入结点

这里需要说的是在插入的递归过程中。会判断最小不平衡子树。然后根据最小不平衡子树的根结点进行旋转。

def insert(self, tree, val, taller=True):
        # taller 标记树是否有增高

        if tree.val is None:
            # 这里的 tree.lchild = TreeNode(None) 为什么是 TreeNode（None）
            # 因为在下次插入数据时如果 tree 是 None。直接修改 tree = TreeNode(val)
            # 这个时候的 tree 是函数内部变量。
            # 在这里是需要 tree 参数是传址。修改tree 就是在修改整个 tree 对象
            tree.val = val
            tree.lchild = TreeNode(None)
            tree.rchild = TreeNode(None)
            tree.bf = self.eh
            taller = True
        else:
            if val == tree.val:
                taller = False
                return False, taller
            if val < tree.val:

                res, taller = self.insert(tree.lchild, val, taller)

                if res is False:
                    return False, taller

                if taller:
                    if tree.bf == self.lh:
                        self.left_balance(tree)
                        taller = False
                    elif tree.bf == self.eh:
                        tree.bf = self.lh
                        taller = True

                    elif tree.bf == self.rh:
                        tree.bf = self.eh
                        taller = False
            else:
                res, taller = self.insert(tree.rchild, val, taller)
                if res is False:
                    return False, taller

                if taller:
                    if tree.bf == self.lh:
                        tree.bf = self.eh
                        taller = False
                    elif tree.bf == self.eh:
                        tree.bf = self.rh
                        taller = True
                    elif tree.bf == self.rh:
                        self.right_balance(tree)
                        taller = False
        return True, taller

• 完整代码

#! coding=utf8
import pysnooper
import copy
# import pdb; pdb.set_trace()


class TreeNode(object):

    def __init__(self, val, lchild=None, rchild=None):
        self.val = val
        self.lchild = lchild
        self.rchild = rchild

        # 平衡因子，平衡二叉树用。默认 0
        self.bf = 0

    def __repr__(self):
        if self.val is None:
            return "None"
        return "{val: %s, l: %s, r: %s, bf: %s}" % (self.val, self.lchild, self.rchild, self.bf)


class AVLTree():

    def __init__(self):
        self.lh = 1  # 左高
        self.eh = 0  # 平等
        self.rh = -1  # 右高

    # 最小不平衡子树 右旋转 -- 顺时针 --- 平衡因子正数
    def right(self, tree):
        temp_node = copy.deepcopy(tree)

        # 取出树 tree 的左子树r
        l = temp_node.lchild
        # 将树 temp_node 左子树改为 l 的右子树
        temp_node.lchild = l.rchild
        # 在将 l 的右子树 赋值为 temp_node
        l.rchild = temp_node
        tree.val = l.val
        tree.lchild = l.lchild
        tree.rchild = l.rchild
        tree.bf = l.bf

    # 最小不平衡子树 左旋转 -- 逆时针 --- 平衡因子负数
    def left(self, tree):
        temp_node = copy.deepcopy(tree)

        r = temp_node.rchild
        temp_node.rchild = r.lchild
        r.lchild = temp_node

        tree.val = r.val
        tree.lchild = r.lchild
        tree.rchild = r.rchild
        tree.bf = r.bf

    def left_balance(self, tree):

        # l 指向树的左子树根结点
        l = tree.lchild

        if l.bf == self.lh:
            # 新结点插入在树的左结点的左子树上，要右旋处理
            tree.bf = l.bf = self.eh
            self.right(tree)

        if l.bf == self.rh:
            # 新结点插入在树的左结点的右子树上，要两次旋转处理

            # lr 指向树的右结点的右结点
            lr = l.rchild
            if lr.bf == self.lh:
                tree.bf = self.rh
                l.bf = self.eh

            if lr.bf == self.eh:
                tree.bf = l.bf = self.eh

            if lr.bf == self.rh:
                tree.bf = self.eh
                l.bf = self.lh

            lr.bf = self.eh
            self.left(tree.lchild)
            self.right(tree)

    def right_balance(self, tree):

        r = tree.rchild
        if r.bf == self.rh:
            tree.bf = r.bf = self.eh
            self.left(tree)

        if r.bf == self.eh:
            tree.bf = r.bf = self.eh

        if r.bf == self.lh:
            rl = r.lchild

            if rl.bf == self.lh:
                tree.bf = self.eh
                r.bf = self.rh

            if rl.bf == self.eh:
                tree.bf = r.bf = self.eh

            if rl.bf == self.rh:
                tree.bf = self.lh
                r.bf = self.eh
            rl.bf = self.eh
            self.right(tree.rchild)
            self.left(tree)

    # @pysnooper.snoop()
    def insert(self, tree, val, taller=True):
        # taller 标记树是否有增高

        if tree.val is None:
            # 这里的 tree.lchild = TreeNode(None) 为什么是 TreeNode（None）
            # 因为在下次插入数据时如果 tree 是 None。直接修改 tree = TreeNode(val)
            # 这个时候的 tree 是函数内部变量。
            # 在这里是需要 tree 参数是传址。修改tree 就是在修改整个 tree 对象
            tree.val = val
            tree.lchild = TreeNode(None)
            tree.rchild = TreeNode(None)
            tree.bf = self.eh
            taller = True
        else:
            if val == tree.val:
                taller = False
                return False, taller
            if val < tree.val:

                res, taller = self.insert(tree.lchild, val, taller)

                if res is False:
                    return False, taller

                if taller:
                    if tree.bf == self.lh:
                        self.left_balance(tree)
                        taller = False
                    elif tree.bf == self.eh:
                        tree.bf = self.lh
                        taller = True

                    elif tree.bf == self.rh:
                        tree.bf = self.eh
                        taller = False
            else:
                res, taller = self.insert(tree.rchild, val, taller)
                if res is False:
                    return False, taller

                if taller:
                    if tree.bf == self.lh:
                        tree.bf = self.eh
                        taller = False
                    elif tree.bf == self.eh:
                        tree.bf = self.rh
                        taller = True
                    elif tree.bf == self.rh:
                        self.right_balance(tree)
                        taller = False
        return True, taller


t = AVLTree()
tree = TreeNode(3)
tree.lchild = TreeNode(None)
tree.rchild = TreeNode(None)

i = [2, 1, 4, 5, 6, 7, 10, 9, 8]
for a in i:
    t.insert(tree, a)
print tree