首先给AVL树下个定义：
一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的任意节点的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。

下面做简要分析：
(1)AVL树首先是个二叉搜索树，对任意节点a，比a数值小的节点在左子树上，比a数值大的节点在右子树上。
(2)AVL树高度平衡。每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子balance。根据AVL树的定义，任一结点的平衡因子只能取 -1，0、1。假设有N个节点，那么其高度可保持在O(log2n)，平均搜索长度也可保持在O(log2n)。
(3)添加节点导致不平衡时，需进行平衡化旋转。

平衡化旋转：

平衡化旋转有两类：
(1)单旋转 (左旋和右旋)
(2)双旋转 (左平衡和右平衡)

每插入一个新结点时，AVL树中相关结点的平衡状态可能会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。 如果在某一结点发现高度不平衡，停止回溯。

从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。此时分为两种情况：
(1)如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。
(2)如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。



假设以上三个节点从上至下分别为A、B、C，则有：
(1)右单旋转：
以节点B为轴，节点A顺时针旋转，成为节点B的右儿子，节点B原右子树成为节点A的左子树。
(2)左单旋转：
以节点B为轴，节点A逆时针旋转，成为节点B的左儿子，节点B原左子树成为节点A的右子树。
(3)左右双旋转：
节点C和节点B逆时针转动，C成为节点A的左儿子，B成为C的左儿子，且C的左子树成为B的右子树；然后再进行右单旋转。
(4)右左双旋转：
节点C和节点B顺时针转动，C成为节点A的右儿子，B成为C的右儿子，且C的右子树成为B的左子树；然后再进行左单旋转。

AVL树的插入

从一个空树开始，给定输入序列，要求建立AVL树，此时涉及到AVL树的插入问题。在插入时需要判断每个节点的平衡因子，并在失去平衡时用到之前所说的旋转平衡。

插入函数执行将值为x的新节点插入到AVL树的恰当位置，并做平衡处理的功能。
(1)先判断是否为空树，若是则为新节点动态分配存储空间，然后置success为1，再将taller置为1。如果不是，根据新节点与根节点的大小判断，分成左右子树两种情况讨论，做下述操作。
(2)算法从树的根结点开始，递归向下找插入位置。在找到插入位置(空指针)后，为新结点动态分配存储空间，将它作为叶结点插入，并置success为1，再将taller置为1，以表明插入成功。在退出递归沿插入路径向上返回时做必要的调整，即判断是否需要旋转平衡。

AVL树的删除

如果被删结点x最多只有一个子女，那么问题比较简单。如果被删结点x有两个子女，首先搜索x 在中序次序下的直接前驱 y (同样可以找直接后继)。再把结点y 的内容传送给结点x，现在问题转移到删除结点y。

将结点y从树中删去。因为结点y最多有一个子女，我们可以简单地把y的父亲结点中原来指向y的指针改指到这个子女结点；如果结点y没有子女，y父亲结点的相应指针置为NULL。然后将原来以结点y为根的子树的高度减1，必须沿x 通向根的路径反向追踪高度的变化对路径上各个结点的影响。


详细内容和源代码可以参看以下链接：
http://spec.cumtcs.net/%CA%FD%BE%DD%BD%E1%B9%B9(%D0%C2)/%CA%FD%BE%DD%BD%E1%B9%B9/lesson/ch07/0706.html