一、分析平衡二叉查找树有什么意义？
平衡二叉查找树是对二叉查找树的改进，那二叉查找树哪些地方是不尽人意的呢？
在分析二叉查找树的平均查找长度时，会发现：二叉查找树的平均查找长度与二叉查找树的形态有关系，最坏的情况是退化为链表，查找变为线性查找，平均查找长度为(n+1)/2。最好的情况就是树的形态与折半查找的判断树形式。平均查找长度为logN。
平衡二叉树就是为了保证树的形态向“树”的方向走。避免了二叉查找树退化为链表的可能。从而提高了查找效率。其实平衡二叉查找树与二叉查找树的区别并不是很大，平衡树在“改变”树的时候会维护树的形态，“改变”无非就两种，插入节点和删除节点，而树的查找只“读”了树，并没改变，所以树的查找，平衡树和查找树是一样的。
二、二叉查找树与平衡二叉查找树的比较：
例如：
现在我要使用24,12,53,28,45,90创建查找树。
如果创建的二叉查找树（如左图），则平均查找长度：(1 2 2 3 4 3)/6 = 15/6
如果创建的是平衡二叉查找树(如右图)，则平均查找长度：(2 3 2 3 1 3)/6 = 14/6.
平衡二叉树的查找效率要高
三、相关概念：
1. 平衡二叉查找树：
平衡二叉查找树又称为平衡二叉排序树，又称为AVL树，是二叉查找树的改进。
定义（满足如下三个条件）：
(1),是二叉查找树。
(2),左子树与右子树的深度之差的绝对值小于或等于1.
(3),左右子树也是平衡二叉查找树。
2. 什么是平衡因子？
平衡二叉查找树的每个结点都要描述一个属性，就是平衡因子，它表示结点的左子树深度与右子树深度之差。该概念的引入也是为了更好地描述什么是平衡二叉查找树。有了这概念后.我们可以重新对二叉查找树下个定义。
如果某个二叉查找树的所有节点的平衡因子只有-1,0,1则说明其实平衡的，否则说明是不平衡的。
四、平衡二叉树的插入：
插入一个新的节点，只有该节点的祖先节点的平衡因子会变化，其他节点的平衡因子都不会变化。
从插入点开始遍历祖先节点，最近的失衡的点，即为A节点。B节点即为该祖先节点的A节点的下一个节点。
这两个特殊的点很重要，因为后面的失衡类型就是根据这两个点的平衡因子来判断的。
现在将非平衡的情况分为四种，每种情况都有自己的调整方法。
1. LL型。（B节点在A节点的左子树上，在B点的左子树上插入新的节点） 在A节点的左子树的左子树上插入节点。
如果失衡类型是LL型，这调整算法如下：
调整方法：以B点为轴，将A节点做顺时针旋转，然后将B的右子树作为A的左子树。
算法的代码实现如下：（可结合上面的图看）
- case LL:
- B = A->lchild;//该类型B节点所在的位置
- A->lchild = B->rchild;//将B节点的右子树交给A，作为A的左子树。
- B->rchild = A;//把A作为B的右子树。
- A->bf = B->bf = 0;//更新A，B节点的平衡因子的值。
- if (father_A == NULL) *root = B;//如果A是根，则现在把B节点设置为根节点。
- else if (A == father_A->lchild) father_A->lchild = B;//如果原来A是father_A的
- //左孩子，则现在把B，作为father_A的左孩子。否则，作为father_A的右孩子，就是用B的取代A原来的位置。
- else father_A->rchild = B;
- break;
该算法的过程实现起来并不难，主要还是有人家的理论在这儿放着。详细的过程看代码注释。
2. RR型。（在A节点的右子树的右子树上插入节点）
如果失衡类型是RR型，这调整算法如下：
调整方法：以B节点为轴，将A节点作逆时针旋转，然后，把B的左子树给A，作为A的右子树。
算法的代码实现如下：
- case RR:
- B = A->rchild;//该类型B节点所在的位置
- A->rchild = B->lchild;//把B的左子树给A，充当A的右子树。
- B->lchild = A;//将A充当B的左子树，完成了逆时针旋转。
- A->bf = B->bf = 0;//重新设置平衡因子。
- if (father_A == NULL) *root = B;//看原来A在整个树中的位置，现在将B取代A的位置
- else if (A == father_A->lchild) father_A->lchild = B;
- else father_A->rchild = B;
- break;
3. LR型。（在A节点的左子树的右子树上插入节点）
该类型又引入了一个特殊节点C。该节点很好判断，和判断B节点一样，插入节点的“祖先节点”那一线上，A的下一个是B，B的下一个就是C节点。
如果失衡类型是LR型，这调整算法如下：
调整方法：以C节点为中心，先左转，再右转。C节点为最后的最上层节点。即将C节点的左子树作为节点B的右子树，C节点作为A节点的左子树；再将C节点的右子树作为A节点的左子树，C节点作为最后的最上层节点。
算法的实现代码分析：
- case LR:
- B = A->lchild;//该类型B节点的位置
- C = B->rchild;//该类型C节点的位置
- B->rchild = C->lchild;//C节点的左子树交给B，作为B的右子树。
- A->lchild = C->rchild;//C节点的右子树交给A，作为A的左子树。
- C->lchild = B;//B作为C的左子树
- C->rchild = A;//A作为A的右子树
- if (s->key < C->key) {//根据插入节点与C节点的位置来更新平衡因子的值
- A->bf = -1;B->bf = 0;C->bf = 0;
- } else if (s->key > C->key) {
- A->bf =0;B->bf = 1;C->bf = 0;
- } else {
- A->bf = 0;B->bf = 0;
- }
- if (father_A == NULL) *root = C;//用C节点来取代A节点的位置。
- else if (A == father_A->lchild) father_A->lchild = C;
- else father_A->rchild = C;
- break;