AVL樹為二叉查找樹的變種，其定義為在二叉查找樹的基礎(chǔ)上保證所有節(jié)點(diǎn)的左子樹與右子樹的高度差最大不超過1。
10 10
8 12 8 12
5 11 13 5 11 13
3
（AVL樹） （插入節(jié)點(diǎn)3后，變?yōu)槠胀ú檎叶鏄洌?的左右子樹高度差2）
上例為一個AVL樹，10的左子樹高為3，右子樹高為虎作2，高度差為1。其子節(jié)點(diǎn)也滿足左右高度相差不超過1的定義。
如果上圖中再插入一個節(jié)點(diǎn)3，則左右子樹的高度將相差為2（不平衡），此時不符合AVL樹的定義。這時為了在插入新節(jié)點(diǎn)時仍能保持為一棵AVL樹，需要在樹不平衡時對節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，所謂的旋轉(zhuǎn)即新插入新節(jié)點(diǎn)的父節(jié)點(diǎn)與其祖父節(jié)點(diǎn)進(jìn)行位置交換，旋轉(zhuǎn)后，不平衡的樹將成為一棵新的AVL樹。
對于旋轉(zhuǎn)，有兩個規(guī)則：
1、若插入節(jié)點(diǎn)比其父節(jié)點(diǎn)小（插入樹左邊）或比其父節(jié)點(diǎn)大（插入樹的右邊）時，只需進(jìn)行一次旋轉(zhuǎn)（右旋或左旋）。
2、若插入節(jié)點(diǎn)后使樹不平衡，并且其值處于其父節(jié)點(diǎn)及祖父節(jié)點(diǎn)之間，則需進(jìn)行兩次旋轉(zhuǎn)，稱這為雙旋（之所以雙旋是因為一次旋轉(zhuǎn)已不能將非AVL樹轉(zhuǎn)換為AVL樹，如下插入節(jié)點(diǎn)1再插入節(jié)點(diǎn)2的情況）。
10
5 12
3 8 11 13
（插入3后，右單旋，5與8交換）
此時，插入節(jié)點(diǎn)1后再插入節(jié)點(diǎn)2，則3的左子樹高為2，右子樹高為0，不平衡。
根據(jù)規(guī)則2，2造成樹不平衡，并且其值處于1－3之間，需進(jìn)行一次雙旋（此時若只進(jìn)行一次單旋并不能改變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
（雙旋，先進(jìn)行一次左單旋，1與2交換）
10
5 12
2 8 11 13
1 3
（雙旋，再進(jìn)行一次右單旋，2與3交換，樹平衡）
AVL樹的實(shí)現(xiàn)，其實(shí)現(xiàn)與查找二叉樹一致，只是在查找二叉樹的基礎(chǔ)上添加了一個高度信息。
#ifndef AVLTREE_H
#define AVLTREE_H
#include <iostream>
#include <queue>
template<class T>
class AVLTree
{
//定義樹節(jié)點(diǎn)，包括一個數(shù)據(jù)，兩個指針，一個高度
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;
//插入一個節(jié)點(diǎn)
void Insert(const T& data, AVLNode*& p)
{
if(p == 0)
{
p = new AVLNode(data, 0, 0);
std::cout << data << ",";
}
else if(data < p->data)
{
//插入數(shù)據(jù)小于父節(jié)點(diǎn)數(shù)據(jù)，插入左子樹
Insert(data, p->left);
//左右子樹高度相差2，不平衡，需進(jìn)行旋轉(zhuǎn)
if(Height(p->left) - Height(p->right) == 2)
{
//插入數(shù)據(jù)比節(jié)點(diǎn)左子節(jié)點(diǎn)數(shù)據(jù)小，只需進(jìn)行一次右旋
if(data < p->left->data)
{
RightRotate(p);
}
else
{
//插入數(shù)據(jù)處于節(jié)點(diǎn)與左子節(jié)點(diǎn)數(shù)據(jù)之間，需進(jìn)行一次左-右雙旋
LRDoubleRotate(p);
}
}
}
else if(data > p->data)
{
//插入數(shù)據(jù)小于父節(jié)點(diǎn)數(shù)據(jù)，插入右子樹
Insert(data, p->right);
//左右子樹高度相差2，不平衡，需進(jìn)行旋轉(zhuǎn)
if(Height(p->right) - Height(p->left) == 2)
{
//插入數(shù)據(jù)比節(jié)點(diǎn)右邊數(shù)據(jù)小，只需進(jìn)行一次左旋
if(data > p->right->data)
{
LeftRotate(p);
}
else
{
//插入數(shù)據(jù)處于節(jié)點(diǎn)與節(jié)點(diǎn)右邊數(shù)據(jù)之間，需進(jìn)行一次右-左雙旋
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);
}
}
//查找節(jié)點(diǎn)
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);
}
//層次遍歷，使用隊列的特性實(shí)現(xiàn)樹的非遞歸遍歷
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();
}
}
//打印一個節(jié)點(diǎn)值
void Print(AVLNode* p)
{
if(p != 0)
{
std::cout << p->data << ",";
}
}
//遞歸查找一個節(jié)點(diǎn)
bool Find(const T& data)
{
return Find(data, root);
}
};
#endif