前言
前面對map/multimap/set/multiset進(jìn)行了簡單的介紹，在其文檔介紹中發(fā)現(xiàn)，這幾個容器有個共同點(diǎn)是：其底層都是按照二叉搜索樹來實(shí)現(xiàn)的，但是二叉搜索樹有其自身的缺陷，假如往樹中插入的元素有序或者接近有序，二叉搜索樹就會退化成單支樹，時間復(fù)雜度會退化成O(N)，因此map、set等關(guān)聯(lián)式容器的底層結(jié)構(gòu)是對二叉樹進(jìn)行了平衡處理，即采用平衡樹來實(shí)現(xiàn)。
1 AVL樹的概念
二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當(dāng)于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法：當(dāng)向二叉搜索樹中插入新結(jié)點(diǎn)后，如果能保證每個結(jié)點(diǎn)的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：
- 它的左右子樹都是AVL樹
- 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
- 平衡因子 = 右子樹高度 - 左子樹高度
平衡因子并不是必須的，它只是一種控制方式，幫助我們更便捷的控制樹
【擴(kuò)充】
這里為什么高度差為1？如果高度相等不是更平衡嗎？
節(jié)點(diǎn)是一個一個插入的，有些情況是無法做到相等的，最優(yōu)就是高度差是1；比如：兩個節(jié)點(diǎn)的樹和四個節(jié)點(diǎn)的樹等等。
2. AVL樹節(jié)點(diǎn)的定義
AVL樹節(jié)點(diǎn)的定義：
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _bf(0)
{}
AVLTreeNode<T>* _pLeft; // 該節(jié)點(diǎn)的左孩子
AVLTreeNode<T>* _pRight; // 該節(jié)點(diǎn)的右孩子
AVLTreeNode<T>* _pParent; // 該節(jié)點(diǎn)的雙親
T _data;
int _bf; // 該節(jié)點(diǎn)的平衡因子
};
3. AVL樹的插入
AVL樹就是在二叉搜索樹的基礎(chǔ)上引入了平衡因子，因此AVL樹也可以看成是二叉搜索樹。那么AVL樹的插入過程可以分為兩步：
- 按照二叉搜索樹的方式插入新節(jié)點(diǎn)
- 調(diào)整節(jié)點(diǎn)的平衡因子
插入節(jié)點(diǎn)會影響新增節(jié)點(diǎn)的部分祖先
更新原則：
- 若是插入的是左節(jié)點(diǎn)則父節(jié)點(diǎn)的平衡因子減1
- 若是插入的是右節(jié)點(diǎn)則父節(jié)點(diǎn)的平衡因子加1
是否要繼續(xù)更新取決于新增節(jié)點(diǎn)會不會影響父節(jié)點(diǎn)的高度，從而決定會不會影響爺爺節(jié)點(diǎn)
- 更新后，父節(jié)點(diǎn)所在的子樹高度不變則不會影響爺爺節(jié)點(diǎn)
說明父節(jié)點(diǎn)的平衡因子是1或者-1，父節(jié)點(diǎn)在矮的那邊插入了節(jié)點(diǎn)，左右均衡了，于是父節(jié)點(diǎn)的高度不變，則不會影響到爺爺，更新結(jié)束
- 更新后，父節(jié)點(diǎn)所在的子樹高度改變則會影響爺爺節(jié)點(diǎn)
說明更新前，父節(jié)點(diǎn)的平衡因子是0，父節(jié)點(diǎn)變得不均衡，但是不違反規(guī)則，高度改變，會影響爺爺節(jié)點(diǎn)繼續(xù)往上更新
更新后，父節(jié)點(diǎn)的平衡因子為2或-2，說明該子樹違反了平衡規(guī)則，需要處理->旋轉(zhuǎn)
代碼實(shí)現(xiàn)：
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;
//新節(jié)點(diǎn)插入后，AVL樹的平衡性可能會遭到破壞，此時就需要更新平衡因子，并檢測是否破壞了AVL樹的平衡性
/*
pCur插入后，pParent的平衡因子一定需要調(diào)整，在插入之前，pParent的平衡因子分為三種情況：-1，0, 1, 分以下兩種情況：
1. 如果pCur插入到pParent的左側(cè)，只需給pParent的平衡因子-1即可
2. 如果pCur插入到pParent的右側(cè)，只需給pParent的平衡因子+1即可
此時：pParent的平衡因子可能有三種情況：0，正負(fù)1， 正負(fù)2
1. 如果pParent的平衡因子為0，說明插入之前pParent的平衡因子為正負(fù)1，插入后被調(diào)整成0，此時滿足AVL樹的性質(zhì)，插入成功
2. 如果pParent的平衡因子為正負(fù)1，說明插入前pParent的平衡因子一定為0，插入后被更新成正負(fù)1，此時以pParent為根的樹的高度增加，需要繼續(xù)向上更新
3. 如果pParent的平衡因子為正負(fù)2，則pParent的平衡因子違反平衡樹的性質(zhì)，需要對其進(jìn)行旋轉(zhuǎn)處理
*/
while (parent)
{
// 更新雙親的平衡因子
if (cur == parent->left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
// 更新后檢測雙親的平衡因子
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// 插入前雙親的平衡因子是0，插入后雙親的平衡因?yàn)闉? 或者 -1 ，說明以雙親為根的二叉樹的高度增加了一層，因此需要繼續(xù)向上調(diào)整
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 雙親的平衡因子為正負(fù)2，違反了AVL樹的平衡性，需要對以pParent為根的樹進(jìn)行旋轉(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
{
RotateRL(parent);
}
break;
}
else
{
// 插入之前AVL樹就有問題
assert(false);
}
}
return true;
}
4. AVL樹的旋轉(zhuǎn)
如果在一棵原本是平衡的AVL樹中插入一個新節(jié)點(diǎn)，可能造成不平衡，此時必須調(diào)整樹的結(jié)構(gòu)，
使之平衡化。根據(jù)節(jié)點(diǎn)插入位置的不同，AVL樹的旋轉(zhuǎn)分為四種：
- 新節(jié)點(diǎn)插入較高左子樹的左側(cè)—左左：右單旋
上圖在插入前，AVL樹是平衡的，新節(jié)點(diǎn)插入到30的左子樹(注意：此處不是左孩子)中，30左子樹增加了一層，導(dǎo)致以60為根的二叉樹不平衡，要讓60平衡，只能將60左子樹的高度減少一層，右子樹增加一層，即將左子樹往上提，這樣60轉(zhuǎn)下來，因?yàn)?0比30大，只能將其放在30的右子樹，而如果30有右子樹，右子樹根的值一定大于30，小于60，只能將其放在60的左子樹，旋轉(zhuǎn)完成后，更新節(jié)點(diǎn)的平衡因子即可。
在旋轉(zhuǎn)過程中，有以下幾種情況需要考慮：
- 30節(jié)點(diǎn)的右孩子可能存在，也可能不存在
- 60可能是根節(jié)點(diǎn)，也可能是子樹
- 如果是根節(jié)點(diǎn)，旋轉(zhuǎn)完成后，要更新根節(jié)點(diǎn)
- 如果是子樹，可能是某個節(jié)點(diǎn)的左子樹，也可能是右子樹
void _RotateR(PNode pParent)
{
// pSubL: pParent的左孩子
// pSubLR: pParent左孩子的右孩子
PNode pSubL = pParent->_pLeft;
PNode pSubLR = pSubL->_pRight;
// 旋轉(zhuǎn)完成之后，30的右孩子作為雙親的左孩子
pParent->_pLeft = pSubLR;
// 如果30的左孩子的右孩子存在，更新親雙親
if (pSubLR)
pSubLR->_pParent = pParent;
// 60 作為 30的右孩子
pSubL->_pRight = pParent;
// 因?yàn)?0可能是棵子樹，因此在更新其雙親前必須先保存60的雙親
PNode pPParent = pParent->_pParent;
// 更新60的雙親
pParent->_pParent = pSubL;
// 更新30的雙親
pSubL->_pParent = pPParent;
// 如果60是根節(jié)點(diǎn)，根新指向根節(jié)點(diǎn)的指針
if (NULL == pPParent)
{
_pRoot = pSubL;
pSubL->_pParent = NULL;
}
else
{
// 如果60是子樹，可能是其雙親的左子樹，也可能是右子樹
if (pPParent->_pLeft == pParent)
pPParent->_pLeft = pSubL;
else
pPParent->_pRight = pSubL;
}
// 根據(jù)調(diào)整后的結(jié)構(gòu)更新部分節(jié)點(diǎn)的平衡因子
pParent->_bf = pSubL->_bf = 0;
}
-
新節(jié)點(diǎn)插入較高右子樹的右側(cè)—右右：左單旋
實(shí)現(xiàn)及情況考慮可參考右單旋。 -
新節(jié)點(diǎn)插入較高左子樹的右側(cè)—左右：先左單旋再右單旋
將雙旋變成單旋后再旋轉(zhuǎn)，即：先對30進(jìn)行左單旋，然后再對90進(jìn)行右單旋，旋轉(zhuǎn)完成后再考慮平衡因子的更新。
// 旋轉(zhuǎn)之前，60的平衡因子可能是-1/0/1，旋轉(zhuǎn)完成之后，根據(jù)情況對其他節(jié)點(diǎn)的平衡因子進(jìn)行調(diào)整
void _RotateLR(PNode pParent)
{
PNode pSubL = pParent->_pLeft;
PNode pSubLR = pSubL->_pRight;
// 旋轉(zhuǎn)之前，保存pSubLR的平衡因子，旋轉(zhuǎn)完成之后，需要根據(jù)該平衡因子來調(diào)整其他節(jié)點(diǎn)的平衡因子
int bf = pSubLR->_bf;
// 先對30進(jìn)行左單旋
_RotateL(pParent->_pLeft);
// 再對90進(jìn)行右單旋
_RotateR(pParent);
if(1 == bf)
pSubL->_bf = -1;
else if(-1 == bf)
pParent->_bf = 1;
}
- 新節(jié)點(diǎn)插入較高右子樹的左側(cè)—右左：先右單旋再左單旋
參考右左雙旋。
總結(jié)：
假如以pParent為根的子樹不平衡，即pParent的平衡因子為2或者-2，分以下情況考慮
- pParent的平衡因子為2，說明pParent的右子樹高，設(shè)pParent的右子樹的根為pSubR
- 當(dāng)pSubR的平衡因子為1時，執(zhí)行左單旋
- 當(dāng)pSubR的平衡因子為-1時，執(zhí)行右左雙旋
- pParent的平衡因子為-2，說明pParent的左子樹高，設(shè)pParent的左子樹的根為pSubL
- 當(dāng)pSubL的平衡因子為-1是，執(zhí)行右單旋
- 當(dāng)pSubL的平衡因子為1時，執(zhí)行左右雙旋
旋轉(zhuǎn)完成后，原pParent為根的子樹個高度降低，已經(jīng)平衡，不需要再向上更新。
實(shí)現(xiàn)代碼
#pragma once
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf; // balance factor
pair<K, V> _kv;
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
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->left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = cur->_parent;
parent = parent->_parent;
}
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
{
RotateRL(parent);
}
break;
}
else
{
// 插入之前AVL樹就有問題
assert(false);
}
}
return true;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
parent->_bf = 0;
subR->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
subL->_bf = 0;
parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
private:
Node* _root = nullptr;
};
5 AVL樹的驗(yàn)證
AVL樹是在二叉搜索樹的基礎(chǔ)上加入了平衡性的限制，因此要驗(yàn)證AVL樹，可以分兩步：
- 驗(yàn)證其為二叉搜索樹
如果中序遍歷可得到一個有序的序列，就說明為二叉搜索樹
- 驗(yàn)證其為平衡樹
- 每個節(jié)點(diǎn)子樹高度差的絕對值不超過1(注意節(jié)點(diǎn)中如果沒有平衡因子)
- 節(jié)點(diǎn)的平衡因子是否計(jì)算正確
int _Height(PNode pRoot);
bool _IsBalanceTree(PNode pRoot)
{
// 空樹也是AVL樹
if (nullptr == pRoot) return true;
// 計(jì)算pRoot節(jié)點(diǎn)的平衡因子：即pRoot左右子樹的高度差
int leftHeight = _Height(pRoot->_pLeft);
int rightHeight = _Height(pRoot->_pRight);
int diff = rightHeight - leftHeight;
// 如果計(jì)算出的平衡因子與pRoot的平衡因子不相等，或者
// pRoot平衡因子的絕對值超過1，則一定不是AVL樹
if (diff != pRoot->_bf || (diff > 1 || diff < -1))
return false;
// pRoot的左和右如果都是AVL樹，則該樹一定是AVL樹
return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot->_pRight);
}
6 AVL樹的刪除(了解)
因?yàn)锳VL樹也是二叉搜索樹，可按照二叉搜索樹的方式將節(jié)點(diǎn)刪除，然后再更新平衡因子，只不錯與刪除不同的時，刪除節(jié)點(diǎn)后的平衡因子更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置。具體實(shí)現(xiàn)學(xué)生們可參考《算法導(dǎo)論》或《數(shù)據(jù)結(jié)構(gòu)-用面向?qū)ο蠓椒ㄅcC++描述》殷人昆版。
AVL樹是一種自平衡的二叉搜索樹，它的刪除操作與插入操作類似，但需要在刪除節(jié)點(diǎn)后進(jìn)行平衡操作以保持樹的平衡性。
AVL樹的刪除操作可以分為以下幾種情況：
- 如果待刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，直接刪除即可。
- 如果待刪除的節(jié)點(diǎn)只有一個子節(jié)點(diǎn)，將子節(jié)點(diǎn)替代待刪除節(jié)點(diǎn)的位置。
如果待刪除的節(jié)點(diǎn)有兩個子節(jié)點(diǎn)，可以選擇以下兩種方式進(jìn)行刪除：
- 找到待刪除節(jié)點(diǎn)的前驅(qū)或后繼節(jié)點(diǎn)，將其值復(fù)制到待刪除節(jié)點(diǎn)，并將前驅(qū)或后繼節(jié)點(diǎn)刪除。
- 找到待刪除節(jié)點(diǎn)的左子樹中的最大值或右子樹中的最小值，將其值復(fù)制到待刪除節(jié)點(diǎn)，并將最大值或最小值節(jié)點(diǎn)刪除。
刪除節(jié)點(diǎn)后，需要從被刪除節(jié)點(diǎn)的父節(jié)點(diǎn)開始向上回溯，檢查每個祖先節(jié)點(diǎn)是否平衡。如果發(fā)現(xiàn)某個祖先節(jié)點(diǎn)不平衡，需要進(jìn)行相應(yīng)的旋轉(zhuǎn)操作來恢復(fù)平衡。
7 AVL樹的性能
AVL樹是一棵絕對平衡的二叉搜索樹，其要求每個節(jié)點(diǎn)的左右子樹高度差的絕對值都不超過1，這樣可以保證查詢時高效的時間復(fù)雜度，即 l o g 2 ( N ) log_2 (N) log2?(N)。但是如果要對AVL樹做一些結(jié)構(gòu)修改的操作，性能非常低下，比如：插入時要維護(hù)其絕對平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時，有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。因此：如果需要一種查詢高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù)據(jù)的個數(shù)為靜態(tài)的(即不會改變)，可以考慮AVL樹，但一個結(jié)構(gòu)經(jīng)常修改，就不太適合。
AVL樹是一種自平衡二叉搜索樹，它的性能相對于普通的二叉搜索樹更加穩(wěn)定。AVL樹的性能可以從以下幾個方面來介紹：
-
查找操作：AVL樹的查找操作與普通的二叉搜索樹相同，時間復(fù)雜度為O(log n)，其中n為樹中節(jié)點(diǎn)的數(shù)量。由于AVL樹是平衡的，所以查找操作的性能是穩(wěn)定的。
-
插入和刪除操作：AVL樹在插入和刪除節(jié)點(diǎn)時會進(jìn)行自平衡操作，以保持樹的平衡性。這些自平衡操作包括旋轉(zhuǎn)和重新計(jì)算節(jié)點(diǎn)的平衡因子。插入和刪除操作的時間復(fù)雜度也是O(log n)，但由于需要進(jìn)行自平衡操作，所以相對于普通二叉搜索樹，AVL樹的插入和刪除操作可能會更耗時。
-
平衡性：AVL樹的平衡性保證了樹的高度始終保持在一個較小的范圍內(nèi)。具體來說，AVL樹的任意節(jié)點(diǎn)的左右子樹高度差不超過1。這種平衡性保證了查找、插入和刪除操作的時間復(fù)雜度都能夠保持在O(log n)。
-
空間復(fù)雜度：AVL樹的空間復(fù)雜度與節(jié)點(diǎn)數(shù)量成正比，即O(n)。每個節(jié)點(diǎn)需要存儲鍵值對以及額外的平衡因子信息。文章來源：http://www.zghlxwxcb.cn/news/detail-844997.html
總的來說，AVL樹在查找操作上具有較好的性能，但在插入和刪除操作上可能會稍微慢一些。然而，AVL樹的平衡性保證了樹的高度始終保持在一個較小的范圍內(nèi)，從而保證了整體的性能穩(wěn)定性。文章來源地址http://www.zghlxwxcb.cn/news/detail-844997.html
到了這里，關(guān)于【C++庖丁解?！孔云胶舛嫠阉鳂?-AVL樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
