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