平衡二叉树
平衡二叉树又称AVL树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是
平衡二叉树，且左子树和右子树的深度之差绝对值不超过1.若将二叉树上节点的平衡因子BF(Balance Facter）
定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1，0和1。
只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
失去平衡后进行调整的规律可归纳为下列4种情况：
（1）单向右旋平衡处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为
根的子树失去平衡，则需要进行一次向右的顺时针旋转操作。
（2）单向左旋平衡处理：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为
根结点的子树失去平衡，则需要进行一次向左的逆时针旋转操作。
（3）双向旋转（先左后右）平衡处理：由于在*a的左子树根结点的右子树上插结点，*a的平衡因子由1增指2，致
使以*a为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作。
本文转自莫水千流博客园博客，原文链接：http://www.cnblogs.com/zhoug2020/p/4220347.html，如需转载请自行联系原作者
