溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“C++如何實現AVL樹”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
也許因為插入的值不夠隨機，也許因為經過某些插入或刪除操作，二叉搜索樹可能會失去平衡，甚至可能退化為單鏈表，造成搜索效率低。
AVL Tree 是一個「加上了額外平衡條件」的二叉搜索樹，其平衡條件的建立是為了確保整棵樹的深度為 O(log2N)。
AVL Tree 要求任何節點的左右子樹高度相差最多為 1。當違反該規定時，就需要進行旋轉來保證該規定。
AVL 樹節點的定義比一般的二叉搜索樹復雜，它需要額外一個 parent 指針，方便后續旋轉。并在每個節點中引入平衡因子，便于判斷是否需要旋轉。
/// @brief AVL 樹節點結構
/// @tparam K 節點的 key 值
/// @tparam V 節點的 value 值
template <class K, class V>
struct AVLTreeNode {
AVLTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _bf(0)
{}
pair<K, V> _kv;
AVLTreeNode<K, V>* _parent;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
// 左右子樹高度相同平衡因子為：0
// 左子樹高平衡因子為負
// 右子樹高平衡因子為正
int _bf;
};template<class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
Node* Find(const K& key);
bool Insert(const pair<K, V>& kv);
private:
void RotateR(Node* parent);
void RotateL(Node* parent);
void RotateLR(Node* parent);
void RotateRL(Node* parent);
private:
Node* _root = nullptr;
};查找
AVL 樹的查找和普通的搜索二叉樹一樣：
若 key 值大于當前節點的值，在當前節點的右子樹中查找
若 key 值小于當前節點的值，在當前節點的左子樹中查找
若 key 值等于當前節點的值，返回當前節點的地址
若找到空，查找失敗，返回空指針
/// @brief 查找指定 key 值
/// @param key 要查找的 key
/// @return 找到返回節點的指針，沒找到返回空指針
Node* Find(const K& key) {
Node* cur = _root;
while (cur != nullptr) {
// key 值與當前節點值比較
if (key > cur->_kv.first) {
cur = cur->_right;
} else if (key < cur->_kv.first) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr;
}AVL 的插入整體分為兩步：
按照二叉搜索樹的方式將節點插入
調整節點的平衡因子
平衡因子是怎么調整的？
設新插入的節點為 pCur，新插入節點的父節點為 pParent。在插入之前，pParent 的平衡因子有三種可能：0、-1、1。
插入分為兩種：
pCur 插入到 pParent 的左側，將 pParent 的平衡因子減 1
pCur 插入到 pParent 的右側，將 pParent 的平衡因子加 1
此時，pParent 的平衡因子可能有三種情況：0、正負 1、正負 2。
0：說明插入之前是正負 1，插入后被調整為 0，滿足 AVL 性質插入成功
正負 1：說明插入之前是 0，插入后被調整為正負 1，此時 pParent 變高，需要繼續向上更新
正負 2：說明插入之前是正負 1，插入后被調整為正負 2，此時破壞了規定，需要旋轉處理
/// @brief 插入指定節點
/// @param kv 待插入的節點
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// 先找到要插入的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr) {
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
} else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
} else {
// 已經存在，插入失敗
return false;
}
}
// 將節點插入
cur = new Node(kv);
if (kv.first > parent->_kv.first) {
parent->_right = cur;
cur->_parent = parent;
} else {
parent->_left = cur;
cur->_parent = parent;
}
// 更新平衡因子，直到正常
while (parent != nullptr) {
// 調整父親的平衡因子
if (parent->_left == cur) {
--parent->_bf;
} else {
++parent->_bf;
}
if (parent->_bf == 0) {
// 此時不需要再繼續調整了，直接退出
break;
} else if (parent->_bf == 1 || parent->_bf == -1) {
// 此時需要繼續向上調整
cur = parent;
parent = parent->_parent;
} else if (parent->_bf == 2 || parent->_bf == -2) {
// 此時需要旋轉處理
if (parent->_bf == -2 && cur->_bf == -1) {
RotateR(parent);
} else if (parent->_bf == 2 && cur->_bf == 1) {
RotateL(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);
} // end of if (parent->_bf == 0)
} // end of while (parent != nullptr)
return true;
}假設平衡因子為正負 2 的節點為 X，由于節點最多擁有兩個子節點，因此可以分為四種情況：
插入點位于 X 的左子節點的左子樹——左左：右單旋
插入點位于 X 的左子節點的右子樹——左右：左右雙旋
插入點位于 X 的右子節點的右子樹——右右：左單旋
插入點位于 X 的右子節點的左子樹——右左：右左雙旋
右單旋
假設平衡因子為正負 2 的節點為 parent，parent 的父節點為 pParent，parent 的左子樹為 subL，subL 的右子樹為 subLR。
右單旋的操作流程：
讓 subLR 作為 parent 的左子樹
讓 parent 作為 subL 的右子樹
讓 subL 作為整個子樹的新根
更新平衡因子
/// @brief 進行右單旋
/// @param parent 平衡因子為正負 2 的節點
void RotateR(Node* parent) {
Node* pParent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
// 更改鏈接關系
// 1. subLR 作為 parent 的左子樹
parent->_left = subLR;
if (subLR != nullptr) {
subLR->_parent = parent;
}
// 2. parent 作為 subL 的右子樹
subL->_right = parent;
parent->_parent = subL;
// 3. subL 作為整個子樹的新根
if (parent == _root) {
// parent 為 _root，此時令 subL 為 _root
_root = subL;
subL->_parent = nullptr;
} else {
// parent 不為 _root，pParent 也就不為空
if (parent == pParent->_left) {
pParent->_left = subL;
} else {
pParent->_right = subL;
}
subL->_parent = pParent;
}
// 4. 更新平衡因子
// 觀察上圖明顯可知
subL->_bf = 0;
parent->_bf = 0;
}左單旋
左單旋與右單旋類似，只是方向不同。
假設平衡因子為正負 2 的節點為 parent，parent 的父節點為 pParent，parent 的右子樹為 subR，subR 的左子樹為 subRL。
左單旋的操作流程：
讓 subRL 作為 parent 的右子樹
讓 parent 作為 subR 的左子樹
讓 subR 作為整個子樹的新根
更新平衡因子
/// @brief 進行左單旋
/// @param parent 平衡因子為正負 2 的節點
void RotateL(Node* parent) {
Node* pParetn = parent->_parent;
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
// 更改鏈接關系
// 1. subRL 作為 parent 的右子樹
parent->_right = subRL;
if (subRL != nullptr) {
subRL->_parent = parent;
}
// 2. parent 作為 subR 的左子樹
subR->_left = parent;
parent->_parent = subR;
// 3. subR 作為整個子樹的新根
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
} else {
if (parent == pParetn->_left) {
pParetn->_left = subR;
} else {
pParetn->_right = subR;
}
subR->_parent = pParetn;
}
// 4. 更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}左右雙旋
假設平衡因子為正負 2 的節點為 parent，parent 的左子樹為 subL，subL 的右子樹為 subLR。
左右雙旋就是對 subL 進行一次左單旋，對 parent 進行一次右單旋。雙旋也就完成了，要注意的是雙旋后平衡因子的更新。
此時分三種情況：
1.新插入的節點是 subLR 的右子樹
2.新插入的節點是 subLR 的左子樹
3.新插入的是 subLR
結合上述情況，寫出如下代碼：
/// @brief 進行左右雙旋
/// @param parent 平衡因子為正負 2 的節點
void RotateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 1) {
// 新插入節點是 subLR 的右子樹
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
} else if (bf == -1) {
// 新插入的節點是 subLR 的左子樹
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
} else if (bf == 0) {
// 新插入的節點是 subLR
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
} else {
assert(false);
}
}右左雙旋
假設平衡因子為正負 2 的節點為 parent，parent 的右子樹為 subR，subR 的左子樹為 subRL。
右左雙旋就是對 subR 進行一次右單旋，對 parent 進行一次左單旋。流程和左右雙旋一樣，這里就不過多介紹了。
void RotateRL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 1) {
// 新插入節點是 subRL 的右子樹
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
} else if (bf == -1) {
// 新插入的節點是 subRL 的左子樹
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
} else if (bf == 0) {
// 新插入的節點是 subRL
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
} else {
assert(false);
}
}“C++如何實現AVL樹”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
