溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“C++ AVL樹插入新節點后的調整情況有哪些”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++ AVL樹插入新節點后的調整情況有哪些”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
AVL樹是一個高度平衡的二叉搜索樹
滿足二叉搜索樹的所有特性。
左子樹和右子樹的高度之差的絕對值不大于1。
此處AVL樹結點的定義
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; //平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};使用平衡因子，是維持AVL樹的方法之一。
此處平衡因子 = 右子樹高度 - 左子樹高度。
AVL樹的定義及默認構造函數
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(nullptr)
{}
private:
Node* _root;
};按照普通二叉搜索樹的辦法先嘗試插入： bool insert(const pair<K, V>& kv);。
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
//插入之前是一棵空樹，則插入結點變成根結點
_root = new Node(kv);
return true;
}
//找到一個NULL位置插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
//說明已經有了，就不再插入
return false;
}
}
//已找到，準備插入
cur = new Node(kv);
if (parent->_kv.first > kv.first)
{
//如果比parent小，鏈接到parent的左
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
}雖然插入之后，依舊會保持二叉搜索樹的特性，但是AVL樹的特性可能就被破壞了。當平衡因子的絕對值是2的時候就需要進行調整。以下是AVL樹特性被破壞的四種情況及解決辦法：
情況一：右單旋。
結點插入后，導致左子樹高度比右子樹高2，其左孩子的左子樹比右子樹高1。
口訣：自己左高2，左孩子左高1，左單旋。
情況二：左單旋。
結點插入后，導致右子樹的高度比左子樹高2，其右孩子的右子樹比左子樹高1.
口訣：自己右高2，右孩子右高1，右單旋。
情況三：先左單旋、再右邊單旋。
結點插入后，導致左子樹的高度比右子樹的高度高2，其左孩子的右子樹比左子樹高度高1.
口訣：自己左高2，左孩子右高1，先右旋后左旋。
情況四：先右單旋，再左單旋。
結點插入后右子樹比左子樹高2，其右孩子的左子樹比右子樹高1。
口訣：自己右高2，右孩子左高1，先右旋后左旋。
情況三和情況四種，每一種情況又衍生出了兩種子問題，關乎平衡因子的更新數值。（假設此時平衡因子是-2的結點為parent， parent的左孩子為subL， subL的右孩子為subLR）
情況三的子問題
a、增加結點放在subLR的左子樹。
b、增加結點放在subLR的右子樹
調整后
parent的平衡因子：1
subL的平衡因子：0
subLR的平衡因子：0
調整后
parent的平衡因子：0
subL 的平衡因子：-1
subLR的平衡因子：0
可以看出，平衡因子的數值和結點放置位置是強相關的。雖然是同一種大情況，但是放在左子樹和放在右子樹，上面結點的平衡因子數值不一樣。情況四也有兩種子情況，和情況三的兩種子情況一樣。
假設此時平衡因子是2的結點為parent， parent的右孩子為subR， subR的左孩子為subRL
情況四的子問題
a、增加結點放在subRL的左子樹。
parent的平衡因子：0
subR 的平衡因子：0
subRL的平衡因子：1
b、增加結點放在sub的右子樹。
parent的平衡因子：-1
subR 的平衡因子：0
subRL的平衡因子：0
AVL樹簡單模擬插入的對應代碼
namespace Blog
{
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; //平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(nullptr)
{}
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
//插入之前是一棵空樹，則插入結點變成根結點
_root = new Node(kv);
return true;
}
//找到一個NULL位置插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if(cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
//說明已經有了，就不再插入
return false;
}
}
//已找到，準備插入
cur = new Node(kv);
if (parent->_kv.first > kv.first)
{
//如果比parent小，鏈接到parent的左
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//更新平衡因子，平衡因子不符合時，調節樹
while (parent)
{
//第一步：更新平衡因子
if (parent->_left == cur)
parent->_bf--;
else
parent->_bf++;
//檢查平衡因子，如果平衡因子不符合，需要調整樹
if (0 == parent->_bf)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//繼續往上更新平衡因子
cur = parent;
parent = cur->_parent;
}
else if(parent->_bf == 2 || parent->_bf == -2)
{
//平衡因子不符合，說明左子樹和右子樹高度之差為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);
}
}
else
{
//說明插入之前，這顆樹就已經不符合AVL樹的特性了
assert(false);
}
}
return true;
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subLR->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
if (parentParent->_left = parent)
{
parentParent->_left = subL;
subL->_parent = parentParent;
}
else
{
parentParent->_right = subL;
subL->_parent = parentParent;
}
}
//調節后，重新更新平衡因子
parent->_bf = subL->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subRL->_left;
parent->_right = subRL;
if (subRL)
suRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
if (parentParent->_left = parent)
{
parentParent->_left = subR;
subR->_parent = parentParent;
}
else
{
parentParent->_right = subR;
subR->_parent = parentParent;
}
}
subR->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; //用于后面判斷加在subRL的左子樹還是右子樹
RotateL(parent->_left);
RotateR(parent);
//它的兩種子情況，更新的平衡因子不一樣
if (bf == -1)
{
//加在subLR的左子樹
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
//加在右子樹
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subL->_left;
int bf = subRL->_bf; //用于后面判斷加在subRL的左子樹還是右子樹
RotateL(parent->_right);
RotateR(parent);
//它的兩種子情況，更新的平衡因子不一樣
if (bf == -1)
{
//加在subRL的子樹
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 1;
}
else if (bf == 1)
{
//加在左子樹
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
private:
Node* _root;
};
}讀到這里，這篇“C++ AVL樹插入新節點后的調整情況有哪些”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
