AVL樹是高度平衡的二叉搜索樹，按照二叉搜索樹（Binary Search Tree）的性質，AVL首先要滿足：
若它的左子樹不為空，則左子樹上所有結點的值均小於它的根結點的值； 若它的右子樹不為空，則右子樹上所有結點的值均大於它的根結點的值； 它的左、右子樹也分別為二叉搜索樹。
AVL樹的性質：
(每個節點的平衡因子bf 等於右子樹的高度減去左子樹的高度 )
//// AVL樹的節點類
template<class K,class V>
class AVLTreeNode
{
K _key;
V _value;
int _bf;//平衡因子 -1,0,1(每個節點的平衡因子等於右子樹的高度減去左子樹的高度)
AVLTreeNode<K, V>* _parent; //指向父節點的指針
AVLTreeNode<K, V>* _left; //指向左孩子的指針
AVLTreeNode<K, V>* _right; //指向右孩子的指針
AVLTreeNode(const K& key = K(), const V& value = V())
:_key(key)
, _value(value)
, _bf(0)
, _parent(NULL)
, _left(NULL)
, _right(NULL)
{}
};
插入數據以後，父節點的平衡因子必然會被改變！
首先判斷父節點的平衡因子是否滿足性質1（-1<= parent->_bf <=1），如果滿足，則要回溯向上檢查插入該節點是否影響了其它節點的平衡因子值！
旋轉的目的是為了降低高度
旋轉的一般形態：
旋轉至少涉及三層節點，所以至少要向上回溯一層 ，才會發現非法的平衡因子並進行旋轉
向上回溯校驗時，需要進行旋轉的幾種情況：
1. 當前節點的父節點的平衡因子等於2時，說明父節點的右樹比左樹高：
2. 當前節點的父節點的平衡因子等於-2時，說明父節點的右樹比左樹低：
// AVLTree插入算法
template<class K, class V>
bool AVLTree<K,V>::Insert(const K& key, const V& value)
{
//1.空樹
if (_root == NULL)
{
_root = new AVLTreeNode<K, V>(key, value);
return true;
}
//2.AVL樹不為NULL
AVLTreeNode<K, V>* parent = NULL;
AVLTreeNode<K, V>* cur = _root;
//找到數據插入位置
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//插入數據
cur = new AVLTreeNode<K, V>(key, value);
cur->_parent = parent;
if (parent->_key > key)
parent->_left = cur;
else
parent->_right = cur;
while (parent)
{
//更新平衡因子
if (cur == parent->_left)
parent->_bf--;
else if (cur == parent->_right)
parent->_bf++;
//檢驗平衡因子是否合法
if (parent->_bf == 0)
break;
else if (parent->_bf == -1 || parent->_bf == 1)
{ // 回溯上升 更新祖父節點的平衡因子並檢驗合法性
cur = parent;
parent = cur->_parent;
}
else // 2 -2 平衡因子不合法 需要進行旋轉 降低高度
{
if (parent->_bf == 2)
{
if (cur->_bf == 1)
_RotateL(parent);
else
_RotateRL(parent);
}
else if (parent->_bf == -2)
{
if (cur->_bf == -1)
_RotateR(parent);
else
_RotateLR(parent);
}
break;
}
}
}
左旋的兩種情況：
1.parent有兩個孩子：沒有插入節點c之前處於平衡狀態，插入c之後，平衡被破壞，向上回溯檢驗祖父節點的平衡因子，當其bf=2 時，以此節點為軸進行左旋
2.parent有一個孩子：沒有插入節點a之前處於平衡狀態，插入節點a之後，parent節點的平衡因子bf=2不滿足AVL樹的性質，要以parent為軸進行左旋
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33//左旋
template<class K, class V>
void AVLTree<K, V>::_RotateL(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* subR = parent->_right;
AVLTreeNode<K, V>* subRL = subR->_left;
AVLTreeNode<K, V>* ppNode = parent->_parent; //標記祖先節點
//1.構建parent子樹 鏈接parent和subRL
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
//2.構建subR子樹 鏈接parent和subR
subR->_left = parent;
parent->_parent = subR;
//3.鏈接祖先節點和subR節點
subR->_parent = ppNode;
if (ppNode== NULL)
{//如果祖先節點為NULL，說明目前的根節點為subR
_root = subR;
}
else
{ //將祖先節點和subR節點鏈接起來
if (parent == ppNode->_left)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
//4.重置平衡因子
parent->_bf = 0;
subR->_bf = 0;
//5.更新subR為當前父節點
parent = subR;
}
1. parent既有左孩子又有右孩子：插入c之前處於平衡態，插入c之後parent的平衡因子變為-2，這時要以parent為軸進行旋轉
2. parent只有一個孩子：插入a之前處於平衡狀態，插入之後subL與parent的平衡因子被改變，需要以parent為軸進行旋轉
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33///右旋
template<class K, class V>
void AVLTree<K, V>::_RotateR(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* subL = parent->_left;
AVLTreeNode<K, V>* subLR = subL->_right;
AVLTreeNode<K, V>* ppNode = parent->_parent; //標記祖先節點
//1.構建parent子樹 將parent和subLR鏈接起來
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
//2.構建subL子樹 將subL與parent鏈接起來
subL->_right = parent;
parent->_parent = subL;
//3.將祖先節點與sunL鏈接起來
if (ppNode == NULL)
{ //如果祖先為NULL，說明當前subL節點為根節點
subL->_parent = NULL;
_root = subL;
}
else
{
subL->_parent = ppNode;
if (ppNode->_left == parent)
ppNode->_left = subL;
else if (ppNode->_right == parent)
ppNode->_right = subL;
}
//4.重置平衡因子
parent->_bf = 0;
subL->_bf = 0;
//5.更新subL為當前父節點
parent = subL;
}
1. parent只有一個孩子：在插入節點sunLR之前，AVL樹處於平衡狀態，左右子樹高度差的絕對值不超過1。
由於插入了節點subLR導致grandfather的平衡因子變為-2，平衡樹失衡，所以需要利用旋轉來降低高度！
2. parent有兩個孩子：沒有插入subRL或subRR之前的AVL樹一定是處於平衡狀態的，並且滿足AVL樹的性質。
正是由於插入了節點subRL或者subRR，導致其祖先節點的平衡因子被改變，grandfather的平衡因子變為-2，平衡態比打破，需要進行旋轉來降低高度！
parent有兩個孩子時，要看插入的節點是subR的右孩子還是左孩子，雙旋後對平衡因子的修改分兩種情況：
//左右雙旋
template<class K, class V>
void AVLTree<K, V>::_RotateLR(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* pNode = parent;
AVLTreeNode<K, V>* subL = parent->_left;
AVLTreeNode<K, V>* subLR = subL->_right;
int bf = subLR->_bf;
_RotateL(parent->_left);
_RotateR(parent);
if (bf == 1)
{
pNode->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
pNode->_bf = 1;
subL->_bf = 0;
}
else
{
pNode->_bf = 0;
subL->_bf = 0;
}
}
1. parent只有一個孩子：由於節點subRL的插入破壞了AVL樹的平衡，parent的平衡因子變為2，需要利用旋轉來降低高度！
2.parent有兩個孩子：沒有插入subLL或者subLR之前的AVL樹一定是處於平衡狀態的，並且滿足AVL樹的性質。
正是由於插入了節點subLL或者subLR，導致其祖先節點的平衡因子被改變，grandfather的平衡因子變為2，平衡態比打破，需要進行旋轉來降低高度！
parent有兩個孩子時，要看插入的節點是subL的右孩子還是左孩子，雙旋後對平衡因子的修改分兩種情況：
//右左雙旋
template<class K, class V>
void AVLTree<K, V>::_RotateRL(AVLTreeNode<K, V>*& parent)
{
AVLTreeNode<K, V>* pNode = parent;
AVLTreeNode<K, V>* subR= parent->_right;
AVLTreeNode<K, V>* subRL = subR->_left;
int bf = subRL->_bf;
_RotateR(parent->_right);
_RotateL(parent);
if (bf == 1)
{
pNode->_bf = 0;
subR->_bf = -1;
}
else if (bf == -1)
{
pNode->_bf = 1;
subR->_bf = 0;
}
else
{
pNode->_bf = 0;
subR->_bf = 0;
}
}