AVL tree:稱為高度平衡的二叉搜尋樹（左右子樹的高度差不超過1），是1962年有俄羅斯的數學家G.M.Adel'son-Vel'skii和E.M.Landis提出來的。它能保持二叉樹的高度平衡，盡量降低二叉樹的高度，減少樹的平均搜尋長度。
AVL樹的性質: 1. 左子樹和右子樹的高度之差的絕對值不超過1
2. 樹中的每個左子樹和右子樹都是AVL樹
3. 每個節點都有一個平衡因子(balance factor--bf),任一節點的平衡因子是-1,0,1。(每個節點的平衡因子等于右子樹 高度減去左子樹的高度)
AVL樹是在二叉搜尋樹（每個節點的左子樹小于它的值，右子樹大于它的值）的基礎上建立出來的，我們都知道二叉搜尋樹增删查的時間複雜度為O(N)(最壞情況：每個節點隻有左子樹或者右子樹），例如：
這種極端的情況下樹是高度不平衡的。在二叉搜尋樹的基礎上，我們如果使左右子樹的高度差不超過1，即達到高度平衡的狀态，這時候增删查的時間複雜度就達到了O(logN)（注：在這裡我所提到的所有logN是以2為底數的），那麼這樣一顆高效的樹結構我們應該怎麼去實作呢？我們究竟怎樣控制它才能使它在插入删除的時候，繼續保持高度平衡的狀态呢？這是建構AVL樹的關鍵點。
為了讓它保持高度平衡的特性，我們引入了平衡因子，每個節點的平衡因子隻可能有三個取值-1（表示右子樹高度-左子樹高度=-1，即左子樹的的高度比右子樹的高度高1），0（左子樹和右子樹的高度相同），1（右子樹比左子樹高1）；每次插入/删除一個節點，我們都需要向上更新一下新增節點/删除節點的祖先的平衡因子，一旦發現某個祖先的平衡因子變為2或者-2，我們就需要進行旋轉來使這棵樹保持AVL樹的特性。
那麼，問題又來了，我們需要怎樣去旋轉呢？
我總結了下面幾種情況，我們先來考慮一下幾種比較簡單情況下的旋轉（以向樹中插入一個節點為例子）：
1.黃色方框表示我們要插入的元素有可能放的位置
可以看出如果我們要插入的元素的值小于10，那麼這棵樹依然是一顆平衡樹，不需要進行旋轉；假設現在我們想插入30這個元素，這個元素應該放在c這個位置處，這時候我們向上更新平衡因子，10的平衡因子達到了2，這時候我們需要進行旋轉了。旋轉過程如下：
這樣是不是就成功了，這種旋轉我們稱為左單旋
2.
此時，我們我們如果插入的元素比30大那沒有問題，如果我們想插入一個元素10呢？30的平衡因子就會變為-2，這時候樹又不平衡了，我們需要進行旋轉方式如下：
這種旋轉方式我們稱之為右單旋。
3.
我想插入50，現在我們要插入的值比10大但是比20小，是不是應該放在b處，這個時候我們的樹變成了這樣：
這個時候需要進行旋轉了。
先進行右單旋： 再左單旋：
這種旋轉方式我們稱為右左雙旋。
4.
現在我們想要插入元素25，即在b這個位置進行插入
需要進行旋轉，過程如下：
先進行左單旋： 再進行右單旋：
這種旋轉我們稱為左右雙旋。
将這幾種旋轉我們再來統一的捋一捋：
1.左單旋，将g作為10的右子樹，将以10為父節點的這顆子樹作為20的左子樹完成旋轉，△的節點表示可能存在亦可能不存在
2.右單旋，把節點f作為30的左子樹，然後将以30這個節點為父節點的子樹作為20的右子樹完成旋轉
3.右左雙旋，先以節點30進行右單旋，再以節點10進行左單旋
4.左右雙旋，先以節點10進行左單旋，再以節點30進行右單旋
我們現在已經知道了旋轉的過程，那麼怎樣來實作這顆AVL樹呢？
以插入一個節點為例，步驟如下：
1.先建構二叉搜尋樹
2.插入一個節點，更新平衡因子，判斷是否平衡
a)右邊增加一個節點，父親的平衡因子+1
b)左邊增加一0個節點，父親的平衡因子-1
如果父親的平衡因子等于，則不需要向上更新，說明樹的整體高度沒變
如果父親的平衡因子變為1或者-1，則需要向上進行更新，因為此時樹的變了
如果父親的平衡因子變為-2或者2，則需要根據具體情況進行相應旋轉
過程出來了，代碼怎麼實作呢？為了向上更新平衡因子，很顯然我們需要一個三叉鍊，即每個節點有三個指針：_left,_right,_parent,
下面我們來完成每種情況僞代碼的編寫。
對于左單旋的情況：
Node* ppNode=parent->_parent;
Node* subR=parent->_right;
Node* subRL=subR->_left;
parent->_right=subRL;//此處有大坑，如果subR不存在，需要将parent->_right置空
if(subRL)
{
subRL->_parent=parent;
}
subR->_left=parent;
parent->_parent=subR;
if(_root==parent)
{
_root=subR;
subR->_parent=NULL;
}
else
{
if(ppNode->_left==parent)
{
ppNode->_left=subR;
}
else
{
ppNode->_right=subR;
}
subR->_parent=ppNode;
}
subR->_bf=0;
parent->_bf=0;
對于右單旋的情況：
Node* subL=parent->_left;
Node* subLR=subL->_right;
Node* PPNode=parent->_parent;
parent->_left=subLR;
if(subLR)
{
subLR->_parent=parent;
}
subL->_right=parent;
parent->_parent=subL;
if(_root==parent)
{
_root=subL;
subL->_parent=NULL;
}
else
{
if(PPNode->_left==parent)
{
PPNode->_left=subL;
}
else
{
PPNode->_right=subL;
}
subL->_parent=PPNode;
}
subL->_bf=0;
parent->_bf=0;
對于右左雙旋就是右單旋和左單旋的結合，左右雙旋就是左單旋和右單旋的結合，這裡不在進行分析。
完整的代碼如下：
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K,class V>
struct AVLTreeNode{
K _k;
V _v;
AVLTreeNode<K,V>* _left;
AVLTreeNode<K,V>* _right;
AVLTreeNode<K,V>* _parent;
int _bf;
AVLTreeNode(const K& key,const V& val)
:_k(key)
,_v(val)
,_left(NULL)
,_right(NULL)
,_parent(NULL)
,_bf(0)
{}
};
template<class K,class V>
class MyAVL{
typedef AVLTreeNode<K,V> Node;
public:
MyAVL()
:_root(NULL)
{}
void _InOrder(Node* root)
{
if(root==NULL)
{
return;
}
_InOrder(root->_left);
cout<<root->_k<<" ";
_InOrder(root->_right);
}
void InOrder()
{
return _InOrder(_root);
}
bool Insert(const K& key,const V& val)
{
if(_root==NULL)
{
_root=new Node(key,val);
return true;
}
Node* cur=_root;
Node* parent=NULL;
while(cur!=NULL)
{
if(key<cur->_k)
{
parent=cur;
cur=cur->_left;
}
else if(key>cur->_k)
{
parent=cur;
cur=cur->_right;
}
else
{
return false;
}
}
cur=new Node(key,val);
if(parent->_k>key)
{
parent->_left=cur;
cur->_parent=parent;
}
else
{
parent->_right=cur;
cur->_parent=parent;
}
while(parent)
{
//如果插入節點為右節點，則父親的平衡因子+1
if(cur==parent->_right)
{
parent->_bf++;
}
else//為左節點，則父親的平衡因子-1
{
parent->_bf--;
}
//如果父節點的平衡因子變為0，說明原來是-1或者1，樹的高度沒變，不用向上更新平衡因子
if(parent->_bf==0)
{
break;
}
//如果父親的平衡因子變為-1或者1，說明原來的平衡因子為0，樹的高度變了，則需要向上更新
//平衡因子
else if(parent->_bf==-1||parent->_bf==1)
{
cur=parent;
parent=cur->_parent;
}
else//父親平衡因子變為-2或者2，子樹不再是AVL樹，需要進行旋轉來平衡
{
if(parent->_bf==2)
{
if(cur->_bf==1)
{
RotateL(parent);
}
else
{
RotateRL(parent);
}
}
else
{
if(cur->_bf==-1)
{
RotateR(parent);
}
else
{
RotateLR(parent);
}
}
break;
}
}
return true;
}
bool IsBlanceTree()
{
int height=0;
return _IsBlanceTree(_root,height);
}
bool _IsBlanceTree(Node* root,int& height)
{
if(root==NULL)
{
height=0;
return true;
}
int leftheight=0;
if(_IsBlanceTree(root->_left,leftheight)==false)
{
return false;
}
int rightheight=0;
if(_IsBlanceTree(root->_right,rightheight)==false)
{
return false;
}
if(rightheight-leftheight!=root->_bf)
{
cout<<"平衡因子異常"<<root->_k<<endl;
return false;
}
height=leftheight>rightheight?leftheight+1:rightheight+1;
return abs(leftheight-rightheight)<2;
}
void RotateR(Node* parent)
{
Node* subL=parent->_left;
Node* subLR=subL->_right;
Node* PPNode=parent->_parent;
parent->_left=subLR;
if(subLR)
{
subLR->_parent=parent;
}
subL->_right=parent;
parent->_parent=subL;
if(_root==parent)
{
_root=subL;
subL->_parent=NULL;
}
else
{
if(PPNode->_left==parent)
{
PPNode->_left=subL;
}
else
{
PPNode->_right=subL;
}
subL->_parent=PPNode;
}
subL->_bf=0;
parent->_bf=0;
}
void RotateL(Node* parent)
{
Node* ppNode=parent->_parent;
Node* subR=parent->_right;
Node* subRL=subR->_left;
parent->_right=subRL;//此處有大坑，如果subR不存在，需要将parent->_right置空
if(subRL)
{
subRL->_parent=parent;
}
subR->_left=parent;
parent->_parent=subR;
if(_root==parent)
{
_root=subR;
subR->_parent=NULL;
}
else
{
if(ppNode->_left==parent)
{
ppNode->_left=subR;
}
else
{
ppNode->_right=subR;
}
subR->_parent=ppNode;
}
subR->_bf=0;
parent->_bf=0;
}
void RotateRL(Node* parent)
{
Node* subR=parent->_right;
Node* subRL=subR->_left;
int bf=subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if(bf==0)
{
subRL->_bf=parent->_bf=subR->_bf=0;
}
else if(bf==1)
{
subRL->_bf=0;
parent->_bf=-1;
subR->_bf=0;
}
else if(bf==-1)
{
subRL->_bf=0;
parent->_bf=0;
subR->_bf=1;
}
else
{
assert(false);
}
}
void RotateLR(Node* parent)
{
Node* subL=parent->_left;
Node* subLR=subL->_right;
int bf=subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if(bf==0)
{
subL->_bf=subLR->_bf=parent->_bf=0;
}
else if(bf==1)
{
parent->_bf=0;
subLR->_bf=0;
subL->_bf=-1;
}
else if(bf==-1)
{
parent->_bf=1;
subL->_bf=0;
subLR->_bf=0;
}
else
{
assert(false);
}
}
private:
Node* _root;
};
void TestAVLTree()
{
MyAVL<int,int> t;
//int arr[]={4,2,6,1,3,5,15,7,16};
int arr[]={16,3,7,11,9,26,18,14,15};
for(int i=0; i<sizeof(arr)/sizeof(arr[0]); ++i)
{
t.Insert(arr[i],i);
cout<<arr[i]<<" bf:"<<t.IsBlanceTree()<<endl;
}
t.InOrder();
}
運作結果如下：
有沒有發現代碼中包含了一個常見的筆試題：判斷一顆二叉搜尋樹是否平衡？
思路很簡單，同時遞歸左右子樹并且記錄左右子樹的高度，一旦發現高度之差的絕對值大于1則說明這棵樹不是平衡樹。