引言
之前講解了二叉搜索樹，最優(yōu)情況下它具有非常好的搜索性能，但是在極端場景下，它可能退化為單支樹，可以形象地稱為歪脖子樹~
這樣的話，它搜索的時間復(fù)雜度會從O(log2N)退化為O(N2)，完全喪失了其優(yōu)良的搜索性能。那么AVL樹就可以登場了，它就是為解決這類問題而生的！
一、AVL樹的概念
兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了AVL樹，AVL樹滿足兩條性質(zhì)：
- 它的左右子樹都是AVL樹
- 任意結(jié)點的左右子樹高度差的絕對值不超過1
這樣通過控制子樹高度差，讓AVL樹幾乎完美接近于平衡，便不會出現(xiàn)單支樹的情況，保證了優(yōu)良的搜索性能，因此AVL樹又稱為高度平衡二叉搜索樹。
二、AVL樹的模擬實現(xiàn)
2.1 結(jié)點
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf;//balance factor
AVLTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
細(xì)節(jié)：
- 使用三叉鏈，增加了指向parent的指針
- 使用KV模型，數(shù)據(jù)存儲鍵值對pair
- 結(jié)點存儲平衡因子，用來記錄左右子樹高度差
注：平衡因子計算高度差，是 右子樹高度 - 左子樹高度
2.2 成員變量
template<class K, class V>
class AVLTree
{
protected:
typedef AVLTreeNode<K, V> Node;
public:
protected:
Node* _root = nullptr;
};
2.3 插入
因為AVL樹也是二叉搜索樹，所以默認(rèn)成員函數(shù)和遍歷與之前寫的沒什么不同，這里重點講解AVL樹的插入。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent)//討論平衡因子
{
if (cur == parent->_right)
{
++parent->_bf;
}
else
{
--parent->_bf;
}
if (parent->_bf == 1 || parent->_bf == -1)
{
parent = parent->_parent;
cur = cur->_parent;
}
else if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋轉(zhuǎn)
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
break;
}
else
{
assert(false);
}
}
return true;
}
思路：
- 以二叉搜索樹的方式正常插入
- 討論平衡因子，以及調(diào)整結(jié)構(gòu)
這里的重點在于如何討論和調(diào)整平衡因子(bf)。
- 首先，插入cur結(jié)點，調(diào)整parent結(jié)點的bf，左減右加
- 討論parent的bf
- bf為0
- bf為1或-1
- bf為2或-2
bf為0時：
分析：此時沒有增加高度，而是補上缺口，整棵樹是平衡的，直接break即可
bf為1或-1時：
分析：此時增加了局部子樹的高度，不確定有沒有影響整體的高度差，所以要繼續(xù)向上調(diào)整
parent = parent->_parent;
cur = cur->_parent;
bf為2或-2時：
此時bf已經(jīng)超出平衡限制區(qū)間，需要進(jìn)行結(jié)構(gòu)調(diào)整，我們稱之為旋轉(zhuǎn)。
2.4 旋轉(zhuǎn)
旋轉(zhuǎn)分為兩大類：單旋和雙旋。而單旋分為左單旋和右單旋，雙旋分為左右旋和右左旋。
2.4.1 左單旋
場景：右部外側(cè)插入
過程：
- parent接過subR的左子樹subRL
- subR左邊再鏈接parent
void RotateL(Node* parent)//左單旋
{
Node* grandparent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (grandparent)
{
if (grandparent->_right == parent)
{
grandparent->_right = subR;
}
else
{
grandparent->_left = subR;
}
}
else
{
_root = subR;
}
subR->_parent = grandparent;
parent->_bf = subR->_bf = 0;
}
細(xì)節(jié)：
- 大體是三步鏈接，注意雙向鏈接
- 注意判空（subRL，grandparent）
- 如果判空，注意_root的傳遞
- 最后調(diào)整平衡因子_bf
2.4.2 右單旋
場景：左部外側(cè)插入
過程：
- parent接過subL的右子樹subLR
- subL右邊再鏈接parent
void RotateR(Node* parent)//右單旋
{
Node* grandparent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (grandparent)
{
if (grandparent->_right == parent)
{
grandparent->_right = subL;
}
else
{
grandparent->_left = subL;
}
}
else
{
_root = subL;
}
subL->_parent = grandparent;
parent->_bf = subL->_bf = 0;
}
細(xì)節(jié)：同左單旋
2.4.3 左右旋
場景：左部內(nèi)側(cè)插入
過程：
- 先對subL進(jìn)行左單旋
- 再對parent進(jìn)行右單旋
void RotateLR(Node* parent)//左右旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 1)
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
細(xì)節(jié)：
- 這里旋轉(zhuǎn)直接復(fù)用前面單旋的代碼
- 主要的重點，在于平衡因子bf的討論
- bf為1，在subLR的右側(cè)插入
- bf為-1，在subLR的左側(cè)插入
- bf為0，插入subLR（之前為空）
2.4.4 右左旋
場景：右部內(nèi)側(cè)插入
過程：
- 先對subR進(jìn)行右單旋
- 再對parent進(jìn)行左單旋
void RotateRL(Node* parent)//右左旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 1)
{
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
細(xì)節(jié)：同左右旋
綜上所述，旋轉(zhuǎn)的目的：保證平衡，同時降低樹的高度。
三、AVL樹的驗證
我們主要驗證左右子樹高度是否平衡，即高度差是否小于等于1
bool IsBalance()
{
return _IsBalance(_root);
}
int Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftH = Height(root->_left);
int rightH = Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftH = Height(root->_left);
int rightH = Height(root->_right);
if (rightH - leftH != root->_bf)
{
cout << root->_kv.first << "節(jié)點平衡因子異常" << endl;
return false;
}
return abs(rightH - leftH) <= 1
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
細(xì)節(jié)：
- 為了方便計算高度，寫一個Height函數(shù)
- 在子函數(shù)遞歸中，計算高度差是否小于等于1
- 與此同時，還要檢查平衡因子是否正常
四、AVL樹的性能
4.1 優(yōu)勢
AVL樹是一棵絕對平衡的二叉搜索樹，其要求每個節(jié)點的左右子樹高度差的絕對值都不超過1，這樣可以保證查詢時高效的時間復(fù)雜度，即 l o g 2 ( N ) log_2 (N) log2?(N)。
4.2 缺陷
但是如果要對AVL樹做一些結(jié)構(gòu)修改的操作，性能非常低下，比如：插入時要維護(hù)其絕對平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時，有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。
4.3 適用場景
因此，如果需要一種查詢高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù)據(jù)的個數(shù)為靜態(tài)的(即不會改變)，可以考慮AVL樹，但一個結(jié)構(gòu)經(jīng)常修改，就不太適合。文章來源：http://www.zghlxwxcb.cn/news/detail-843258.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-843258.html
到了這里，關(guān)于【C++練級之路】【Lv.15】AVL樹（雙子旋轉(zhuǎn)，領(lǐng)略絕對平衡之美）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
