平衡二叉树(Balancedbinary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskiiand Landis)于1962年首先提出的，所以又称为AVL树。
定义：平衡二叉树或为空树,或为如下性质的二叉排序树:
（1）左右子树深度之差的绝对值不超过1;
（2）左右子树仍然为平衡二叉树.
平衡二叉树可以避免排序二叉树深度上的极度恶化，使树的高度维持在O（logn）来提高检索效率。
因为插入节点导致整个二叉树失去平衡分成如下的四种情况：
假设由于在二叉排序树上插入节点而失去平衡的最小子数根节点的指针为a（即a是离插入节点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行调整的规律如下：
1.如上图LL单向右旋处理：由于在*a的左子树根节点的左子树上插入节点，*a的平衡因子由1增至2，致使以*a为根节点的子树失去平衡，则需要进行一次向右的顺时针旋转操作。
2.如上图RR单向左旋处理：由于在*a的右子树根节点的右子树上插入节点， *a的平衡因子有-1变为-2，致使以*a为根节点的子树失去平衡，则学要进行一次向左的逆时针旋转操作。
3.如上图LR双向旋转（先左后右）处理：由于在*a的左子树根节点的右子树插入节点，*a的平衡因子有1增至2，致使以*a为根节点的子树失去平衡，则需要进行两次旋转（先左旋后右旋）操作。
4.如上图RL双向旋转（先右后左）处理：由于在*a的右子树根节点的左子树上插入节点，*a的平衡因子由-1变为-2，致使以*a为根节点的子树失去平衡，则需要进行两次旋转（先左旋后右旋）操作。
本文来自博客园，作者：胡峻峥，转载请注明原文链接：https://www.cnblogs.com/hujunzheng/p/4665451.html