AVL树是最先发明的自平衡二叉查找树, 其增删查时间复杂度都是 O(logn), 是一种相当高效的数据结构。当面对需要频繁查找又经常增删这种情景时，AVL树就非常的适用。[ 博客地址：http://blog.csdn.net/thisinnocence ]

AVL树定义

• 若它的左子树不空，则左子树上所有的点的值均小于其根节点；
• 若它的右子树不空，则右子树上所有的点的值均大于其根节点；
• 它的左右子树分别为二叉查找树；

• 左子树和右子树的高度差(平衡因子)不能超过 1;
• 左子树和右子树都是 AVL树; 

AVL树与红黑树对比

• 红黑树对于数值随机插入性能更好，这种场景实际更常见，故应用更广泛；
• AVL 树对于顺序数据插入更有优势；
• 红黑树部分平衡，降低了旋转的要求；
• AVL 树高度平衡，查询操作更具优势；
• AVL 树代码更为简单易实现；

小实验(C实现)

1. LL 型，节点的左孩子的左子树上插入一个新的节点，单右旋；
2. LR 型， 节点的左孩子的右子树上插入一个新的节点，双旋，先左旋后右旋；
3. RR 型，节点的右孩子的右子树上插入一个新的节点，单左旋；
4. RL 型，节点的右孩子的左子树上插入一个新的节点，双旋，先右旋后左旋；

代码：

#include <stdlib.h>
#include <stdio.h>

typedef int bool;
#define true 1
#define false 0

typedef int dataType;
typedef struct BiTNode {
	dataType data;
	int balance;  // 平衡因子 = 左子树深度 - 右子树深度，平衡二叉树取：-1, 0, 1
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

/* 右插入，左旋 */
void leftRotate(BiTree *T) {
	BiTree rightTree = (*T)->rchild;
	(*T)->rchild = rightTree->lchild;
	rightTree->lchild = (*T);
	(*T) = rightTree;
}

/* 左插入，右旋 */
void rightRotate(BiTree *T) {
	BiTree leftTree = (*T)->lchild;
	(*T)->lchild = leftTree->rchild;
	leftTree->rchild = (*T);
	(*T) = leftTree;
}

/* 左子树高，左平衡 */
void leftBalance(BiTree *T) {
	BiTree leftTree = (*T)->lchild;
	BiTree leftTreeRight = leftTree->rchild;
	switch (leftTree->balance) {
	case 1:  // 左子树平衡因子为 1, (插入左孩子左子树), 单右旋
		(*T)->balance = 0;
		leftTree->balance = 0;
		rightRotate(T);
		break;
	case -1: //左子树平衡因子为 -1, (插入左孩子右子树), 双旋
		switch (leftTreeRight->balance) {
		case 1:
			(*T)->balance = -1;
			leftTree->balance = 0;
			break;
		case 0:
			(*T)->balance = 0;
			leftTree->balance = 0;
			break;
		case -1:
			(*T)->balance = 0;
			leftTree->balance = 1;
			break;
		}
		leftTreeRight->balance = 0;
		leftRotate(&((*T)->lchild));
		rightRotate(T);
	}
}

/* 右子树高，右平衡 */
void rightBalance(BiTree *T) {
	BiTree rightTree = (*T)->rchild;
	BiTree rightTreeLeft = rightTree->lchild;
	switch (rightTree->balance) {
	case -1:   //右子树平衡因子为 -1, (插入右孩子右子树), 单左旋
		(*T)->balance = 0;
		rightTree->balance = 0;
		leftRotate(T);
		break;
	case 1:  //右子树平衡因子为 1, (插入右孩子左子树), 双旋
		switch (rightTreeLeft->balance) {
		case -1:
			(*T)->balance = 1;
			rightTree->balance = 0;
			break;
		case 0:
			(*T)->balance = 0;
			rightTree->balance = 0;
			break;
		case 1:
			(*T)->balance = 0;
			rightTree->balance = -1;
			break;
		}
		rightTreeLeft->balance = 0;
		rightRotate(&((*T)->rchild));
		leftRotate(T);
	}
}

/* AVL 树插入, 先定位, 再插入, 然后维持自平衡*/
bool insertAVL(BiTree *T, int elem, bool *taller) {
	if (*T == NULL) {
		*T = (BiTree) malloc(sizeof(BiTNode));
		(*T)->data = http://www.mamicode.com/elem;>

算法学习笔记 平衡二叉树 AVL树