AVL树为二叉查找树的变种，其定义为在二叉查找树的基础上保证所有节点的左子树与右子树的高度差最大不超过1。
10 10
8 12 8 12
5 11 13 5 11 13
3
（AVL树） （插入节点3后，变为普通查找二叉树，8的左右子树高度差2）
上例为一个AVL树，10的左子树高为3，右子树高为虎作2，高度差为1。其子节点也满足左右高度相差不超过1的定义。
如果上图中再插入一个节点3，则左右子树的高度将相差为2（不平衡），此时不符合AVL树的定义。这时为了在插入新节点时仍能保持为一棵AVL树，需要在树不平衡时对节点进行旋转，所谓的旋转即新插入新节点的父节点与其祖父节点进行位置交换，旋转后，不平衡的树将成为一棵新的AVL树。
对于旋转，有两个规则：
1、若插入节点比其父节点小（插入树左边）或比其父节点大（插入树的右边）时，只需进行一次旋转（右旋或左旋）。
2、若插入节点后使树不平衡，并且其值处于其父节点及祖父节点之间，则需进行两次旋转，称这为双旋（之所以双旋是因为一次旋转已不能将非AVL树转换为AVL树，如下插入节点1再插入节点2的情况）。
10
5 12
3 8 11 13
（插入3后，右单旋，5与8交换）
此时，插入节点1后再插入节点2，则3的左子树高为2，右子树高为0，不平衡。
根据规则2，2造成树不平衡，并且其值处于1－3之间，需进行一次双旋（此时若只进行一次单旋并不能改变10的左子树高度），先将2与1交换，然后2与3交换。
10
5 12
3 8 11 13
1
2
（插入1后再插入2，不平衡）
10
5 12
3 8 11 13
2
1
（双旋，先进行一次左单旋，1与2交换）
10
5 12
2 8 11 13
1 3
（双旋，再进行一次右单旋，2与3交换，树平衡）
AVL树的实现，其实现与查找二叉树一致，只是在查找二叉树的基础上添加了一个高度信息。
#ifndef AVLTREE_H
#define AVLTREE_H
#include <iostream>
#include <queue>
template<class T>
class AVLTree
{
//定义树节点，包括一个数据，两个指针，一个高度
struct AVLNode
{
AVLNode(T dat, AVLNode* l, AVLNode* r, int h=0) : data(dat), left(l), right(r), height(h){};
T data;
AVLNode *left, *right;
int height;
}* root;
//插入一个节点
void Insert(const T& data, AVLNode*& p)
{
if(p == 0)
{
p = new AVLNode(data, 0, 0);
std::cout << data << ",";
}
else if(data < p->data)
{
//插入数据小于父节点数据，插入左子树
Insert(data, p->left);
//左右子树高度相差2，不平衡，需进行旋转
if(Height(p->left) - Height(p->right) == 2)
{
//插入数据比节点左子节点数据小，只需进行一次右旋
if(data < p->left->data)
{
RightRotate(p);
}
else
{
//插入数据处于节点与左子节点数据之间，需进行一次左-右双旋
LRDoubleRotate(p);
}
}
}
else if(data > p->data)
{
//插入数据小于父节点数据，插入右子树
Insert(data, p->right);
//左右子树高度相差2，不平衡，需进行旋转
if(Height(p->right) - Height(p->left) == 2)
{
//插入数据比节点右边数据小，只需进行一次左旋
if(data > p->right->data)
{
LeftRotate(p);
}
else
{
//插入数据处于节点与节点右边数据之间，需进行一次右-左双旋
RLDoubleRotate(p);
}
}
}
p->height = MaxHeight(Height(p->left), Height(p->right)) + 1;
}
void RightRotate(AVLNode*& p)
{
AVLNode* k = p->left;
p->left = k->right;
k->right = p;
p->height = MaxHeight(Height(p->left), Height(p->right)) + 1;
k->height = MaxHeight(Height(k->left), p->height) + 1;
p = k;
}
void LRDoubleRotate(AVLNode*& p)
{
LeftRotate(p->left);
RightRotate(p);
}
void LeftRotate(AVLNode*& p)
{
AVLNode* k = p->right;
p->right = k->left;
k->left = p;
p->height = MaxHeight(Height(p->left), Height(p->right)) + 1;
k->height = MaxHeight(Height(k->right), p->height) + 1;
p = k;
}
void RLDoubleRotate(AVLNode*& p)
{
RightRotate(p->right);
LeftRotate(p);
}
//先序遍历
void PreOrder (AVLNode* p)
{
if(p != 0)
{
Print(p);
PreOrder (p->left);
PreOrder (p->right);
}
}
//中序遍历
void InOrder (AVLNode* p)
{
if(p != 0)
{
InOrder (p->left);
Print(p);
InOrder (p->right);
}
}
//后序遍历
void PostOrder (AVLNode* p)
{
if(p != 0)
{
PostOrder (p->left);
PostOrder (p->right);
Print(p);
}
}
//查找节点
bool Find(const T& data, AVLNode* p)
{
if(p != 0)
{
if(data == p->data)
{
return true;
}
else if(data < p->data)
{
return Find(data, p->left);
}
else
{
return Find(data, p->right);
}
}
else
{
return false;
}
}
//删除整棵树
void MakeEmpty(AVLNode* p)
{
if(p != 0)
{
MakeEmpty(p->left);
MakeEmpty(p->right);
std::cout << "del " << p->data << ",";
delete p;
}
}
int Height(const AVLNode*& p)
{
return (p == 0) ? -1 : p->height;
}
int MaxHeight(const int& a, const int& b)
{
return (a > b) ? a : b;
}
public:
AVLTree() : root(0){}
~AVLTree()
{
MakeEmpty(root);
}
void Insert(const T& data)
{
Insert(data, root);
}
void PreOrder()
{
//递归，前序遍历
PreOrder(root);
}
void InOrder()
{
//递归，中序遍历
InOrder(root);
}
void PostOrder()
{
//递归，后序遍历
PostOrder(root);
}
//层次遍历，使用队列的特性实现树的非递归遍历
void LevelOrder ()
{
queue<AVLNode*> q;
AVLNode* p = root;
while(p)
{
Print(p);
if(p->left != 0)
{
q.push(p->left);
}
if(p->right != 0)
{
q.push(p->right);
}
if (q.empty())
{
break;
}
p = q.front();
q.pop();
}
}
//打印一个节点值
void Print(AVLNode* p)
{
if(p != 0)
{
std::cout << p->data << ",";
}
}
//递归查找一个节点
bool Find(const T& data)
{
return Find(data, root);
}
};
#endif