平衡树（AVL算法）

在上面构造这棵树的时候，你要是很细心的话，你会注意到4，2，1三个节点的排列方式是：

你心里犯嘀咕了，如果我们给的数据序列是8,7,6,5,4,3,2,1，那这棵树岂不是越长越歪了？长成了一个一直生长而没有分支只有一边的瘸腿树。对！你注意到了上面办法的核心问题了。它严重依赖于输入的数据序列的次序，极端情况下，它退化成了一个线性序列。我们的本意不是这样的，我们希望它枝繁叶茂，让数据平均分布在多层级的分支上。
用技术的表达，我们需要一棵平衡的树。平衡二叉树（Balanced Binary Tree）有以下性质：它的左右两棵子树的高度差不超过1，并且左右两棵子树都是一棵平衡二叉树。平衡二叉树的高度h维持在数据总数n的对数级。所以查找插入删除这些操作都会有比较好的性能。
平衡二叉树有不同的实现方法，常见的有红黑树、AVL等。
我们下面以AVL为例。它是最先发明出来的平衡二叉树，后面的改进都是在AVL树的思想上继续前进的，比如Java中使用的红黑树，它对节点进行染色，规定一些性质使得树大体平衡，统计性能更好。
AVL树于1962年发布，得名于它的发明者G. M. Adelson-Velsky和E. M. Landis。他们两位科学家在发表的论文《An algorithm for the organization of information》当中提出。
为了平衡，先定义平衡因子BF = |左子树高度h - 右子树高度h|。
平衡因子不能大于1，大于则表示不平衡。如下面的树，B的高度为2，A和C的高度为1，各个节点平衡因子都是0，所以是平衡的：

再如下面的树，C的高度为3，B的高度为2，A的高度为1，平衡因子分别为2，1，0，所以不是平衡的：

数据的表示，我们要在节点中记录平衡因子和高度，修改树节点代码如下：

class TreeNode(object):
    def __init__(self,data=None):
        self.left = None
        self.right = None
        self.data = data
        self.height=1

增加了一个height属性，平衡因子不记录了，因为可以根据左右树的高度差计算出来。现在我们写一个函数计算一棵树的高度：

def treeheight(node):
    if node is None:
        return 0 
    i=0
    j=0
    if not node.left is None:
        i = treeheight(node.left)
    if not node.right is None:
        j = treeheight(node.right)
    return max(i,j)+1

高度也是通过左子树和右子树的高度加1实现的。
要让一棵树保持平衡，我们通过旋转的办法达到目的。可以左旋，也可以右旋。左旋将让整棵树的重心左移，右旋将让整棵树的重心右移。
具体分析如下：
因为二叉树只有左右两个分叉，所以新增加数据导致不平衡时只有四种情况：
LL，往左子树的左边分叉增加节点
如下图，本来右x，y两个节点，新增一个z，x的平衡因子成了2，平衡打破了，需要右旋。
把y节点提成起始节点，把x节点右旋称为y节点的右孩子，如下：

 

右旋的通用规则，让不平衡起始节点OldRoot的左孩子成为新的起始节点NewRoot，把不平衡起始节点OldRoot以及它的右子树整个成为新的起始节点NewRoot的右孩子，然后新的起始节点NewRoot以前的右孩子变成OldRoot的左孩子。
有一个直观表示旋转的图，我们看一下，如下：

红色节点增添加到左边的树之后，节点a的平衡因子由1变成2，平衡被打破，需要右旋。这个例子中，不平衡起始节点OldRoot就是节点a，我们先把它的左孩子节点b右旋提升为新的起始节点NewRoot，再将OldRoot及右子树节点右旋作为NewRoot的右子树，而NewRoot原来的右孩子节点d要作为OldRoot的左孩子。
代码如下：

def rotateLL(node):
    tmpnode = node.left
    node.left = tmpnode.right
    tmpnode.right=node
    node.height=treeheight(node)
    tmpnode.height=treeheight(tmpnode)    
    return tmpnode

这个函数，将最小失衡子树旋转后，返回的是这棵最小失衡子树的新的根。
RR，往右子树的右边分叉增加节点
这个情况根LL是对称的。需要左旋。
左旋的通用规则，让不平衡起始节点OldRoot的由孩子成为新的起始节点NewRoot，把不平衡起始节点OldRoot以及它的左子树整个成为新的起始节点NewRoot的左孩子，而新的起始节点NewRoot以前的左孩子变成OldRoot的右孩子。

def rotateRR(node):
    tmpnode = node.right
    node.right = tmpnode.left
    tmpnode.left=node
    node.height=treeheight(node)
    tmpnode.height=treeheight(tmpnode)
    return tmpnode

这个函数，将最小失衡子树旋转后，返回的是这棵最小失衡子树的新的根。
LR，往左子树的右边分叉增加节点
如下图，本来右x，y两个节点，新增一个z，x的平衡因子成了2，平衡打破了。

这个情况复杂一点，旋转一次仍然不能保持平衡，需要两次旋转。
第一次将y-z子树左旋：

然后将x-z-y右旋：

有一个直观表示旋转的图，我们看一下，如下：

代码如下：

def rotateLR(node):
    node.left=rotateLL(node.left)
    tmpnode=rotateRR(node)
    return tmpnode

有了左旋和右旋函数，这个LR就是组合一下。注意左旋的是本节点的左子树，右旋的是本节点的树。

RL，往右子树的左边分叉增加节点。
这个情况根LR是对称的，需要先右旋右子树，再左旋树。
代码如下：

def rotateRL(node):
    node.right=rotateRR(node.right)
    tmpnode=rotateLL(node)
    return tmpnode

有了这些基础准备，那么添加的过程跟二叉树类似，添加后重新计算高度，如果不平衡就旋转：

def inserttree(nodeobj,node):
    if node.data is None:
        node.data = nodeobj
        node.height = treeheight(node)
    elif nodeobj < node.data:
        if node.left is None:
            node.left = Tree.TreeNode()
        node.left=inserttree(nodeobj,node.left)
        node.height = treeheight(node)
        if abs(treeheight(node.left)-treeheight(node.right))==2:
            if nodeobj<node.left.data:
                node=rotateLL(node)
            elif nodeobj>node.left.data:
                node=rotateLR(node)
    elif nodeobj > node.data:
        if node.right is None:
            node.right = Tree.TreeNode()
        node.right=inserttree(nodeobj,node.right)
        node.height = treeheight(node)
        if abs(treeheight(node.left)-treeheight(node.right))==2:
            if nodeobj>node.right.data:
                node=rotateRR(node)
            elif nodeobj<node.right.data:
                node=rotateRL(node)
    return node

解释一下这个函数：
思路就是看这个节点的内容是不是空，如果是空就直接放入数据。返回该节点。
如果节点内容不为空，就比较大小，小就走左子树，大就走右子树。这是一个递归过程，代码表现为这一句：

        node.left=inserttree(nodeobj,node.left)

新节点加入后，要重新计算高度，并判断平衡因子(左右子树高度差)，代码为：

        node.height = treeheight(node)
if abs(treeheight(node.left)-treeheight(node.right))==2:

如果判断失衡，则进行旋转，代码为：

            if nodeobj<node.left.data:
                node=rotateLL(node)

这是比左边还要小的情况，定为LL型，进行旋转。注意旋转会返回一个node，这个node就是最小失衡子树的新根。
但是这个新根并不一定是添加过程最后返回的根，因为旋转返回的只是最小失衡子树的新根。但是添加过程是一个递归过程，所以又会按照以前从跟开始的路径一步一步往回返，最后的结果，这个添加函数会返回一个新的节点，即为新的根节点。
因为再平衡，添加过程中树的根节点可能会换掉，所以，在构建树的时候每一次添加后都要重新拿新的根：

def loadtree(arr,rootnode):
    for c in arr:
        rootnode=inserttree(NodeObject(c),rootnode)

我们用一个序列作为例子：

["9","8","7","6","5","4","3","2","1","0"]

故意给了一个倒序的列表，如果没有再平衡，树将退化成一个线性序列。
第一步拿到序列中的第一个数字9，初始的时候，树只有一个内容为空的节点，这个就是初始根节点，执行rootnode=inserttree(NodeObject(c),rootnode)。进到inserttree(nodeobj,node)，执行的是里面的这几句：

    if node.data is None:
        node.data = nodeobj
        node.height = treeheight(node)
... ...
return node

这样有了第一个数据节点9，高度为1，inserttree()返回了这个根节点。
第二步拿到序列中的第二个数字8，这个时候根节点为节点9，执行rootnode=inserttree(NodeObject(c),rootnode)。进到inserttree(nodeobj,node)，执行的是里面的这几句：

    elif nodeobj < node.data:
        if node.left is None:
            node.left = Tree.TreeNode()
        node.left=inserttree(nodeobj,node.left)

给节点9加一个左孩子，递归调用inserttree()，试图在新生成的节点9的左孩子这边添加，递归进入，执行的是里面的这几句：

    if node.data is None:
        node.data = nodeobj
        node.height = treeheight(node)
... ...
return node

这样有了第二个数据节点8，高度为1，inserttree()返回了这个新节点。
回到递归的上一层（节点9）断点处继续执行，

        node.height = treeheight(node)
        if abs(treeheight(node.left)-treeheight(node.right))==2:
... ...
return node

重新计算node9的高度，得到新高度为2，再判断是否失衡(代码通过高度差==2判断)，没有失衡，什么也不用做，最后返回本节点9。
递归结束。整个添加过程结束。返回根节点9。
至此添加进了第二个数字。
第三步拿到序列中的第三个数字7，这个时候根节点为节点9，执行rootnode=inserttree(NodeObject(c),rootnode)。进到inserttree(nodeobj,node)，执行的是里面的这几句：

elif nodeobj < node.data:
        if node.left is None:
            node.left = Tree.TreeNode()
        node.left=inserttree(nodeobj,node.left)

数据7小于节点9的数据，递归调用inserttree()，这次是在节点9的左孩子（即节点8）这边添加，递归进入，执行的是里面的这几句：

elif nodeobj < node.data:
        if node.left is None:
            node.left = Tree.TreeNode()
        node.left=inserttree(nodeobj,node.left)

数据7小于节点8的数据，而节点8又没有做孩子，于是给节点8加一个左孩子，再次递归调用inserttree()，试图在新生成的节点8的左孩子这边添加，递归进入，执行的是里面的这几句：

    if node.data is None:
        node.data = nodeobj
        node.height = treeheight(node)
... ...
return node

这样有了第三个数据节点7，高度为1，inserttree()返回了这个新节点。
回到递归的上一层（节点8）断点处继续执行，

        node.height = treeheight(node)
        if abs(treeheight(node.left)-treeheight(node.right))==2:
... ...
return node

重新计算node8的高度，得到新高度为2，再判断是否失衡(代码通过高度差==2判断)，没有失衡，什么也不用做，最后返回本节点8。
回到递归的再上一层（节点9）断点处继续执行，

        node.height = treeheight(node)
        if abs(treeheight(node.left)-treeheight(node.right))==2:
... ...
return node

重新计算node9的高度，得到新高度为3，再判断是否失衡(代码通过高度差==2判断)，现在失衡了。执行如下代码：

            if nodeobj<node.left.data:
                node=rotateLL(node)

以node9作为最小失衡子树的根进行旋转。执行rotateLL(node)：

def rotateLL(node):
    tmpnode = node.left
    node.left = tmpnode.right
    tmpnode.right=node
    node.height=treeheight(node)
    tmpnode.height=treeheight(tmpnode)    
    return tmpnode

旋转过程解析：
tmpnode先记录的是根节点9的左孩子，即节点8。然后把节点8的有孩子交给根节点9当左孩子。再之后，把根节点9当成节点8的右孩子（这个操作实现了节点8的提升和节点9的右旋）。重新计算高度。最后返回tmpnode，也就是失衡子树旋转后的新根。
函数执行完毕，node=rotateLL(node)，现在得到的返回值是新根节点8。
Inserttree()执行完，返回node，即节点8。
递归结束。整个添加过程结束。返回根节点8。
至此添加进了第三个数字7。
第四步拿到序列中的第三个数字6，这个时候根节点为节点8，执行rootnode=inserttree(NodeObject(c),rootnode)。省略。
这样一步一步地构建整棵AVL树。
最后AVL树构造成如下的样子：

到此，我们把树结构的基本知识就介绍了。相信你可以写出一个完整的树的实现类来了。