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樹插入新節點後的四種調整情況梳理介紹的文章就介紹到這瞭,更多相關C++ AVL樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- C++AVL樹4種旋轉詳講(左單旋、右單旋、左右雙旋、右左雙旋)
- C++實現AVL樹的基本操作指南
- C++ STL容器詳解之紅黑樹部分模擬實現
- C++數據結構紅黑樹全面分析
- C++數據結構之紅黑樹的實現