🍎作者：努力學習的少年
🍎個人簡介：雙非大二，一個正在自學c++和linux作業系統，寫博客是總結知識，方便復習
🍎目標：進大廠
🍎 如果你覺得文章可以的話，麻煩你給我點個贊和關注，感謝你的關注！
目錄
📚 1. AVL樹的概念
📚 2. AVL樹節點的定義
📚 3. AVL樹的插入
📚 3. 右單旋
📚 4. 左單旋
📚 5. 左右雙旋
📚 6. 右左雙旋
📚 7. 插入的總的代碼（含注釋）
📚 8. AVL樹查找的代碼
📚 9. 洗掉
📚 1. AVL樹的概念
- AVL樹一顆二叉搜索樹
- 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1，
如果一顆AVL樹有n個節點，其高度可以保持在O(logn),搜索的時間復雜度是O(logn).
📚 2. AVL樹節點的定義
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode* _left;//左孩子節點
AVLTreeNode* _right;//右孩子節點
AVLTreeNode* parent;//父親節點
int _bf;//平衡因子
pair<K, V> _kv;//存盤資料
AVLTreeNode(pair<K,V> kv)//節點的建構式
:_left(nullptr)
,_right(nullptr)
,parent(nullptr)
,_kv(kv)
,_bf(0)
{
}
};📚 3. AVL樹的插入
AVL樹就是在二叉搜索樹的基礎上引入了平衡因子，因此AVL樹也可以看成是二叉搜索樹，那么AVL樹的插入程序可以分為兩步：
- 按照二叉搜索樹的方式直接插入新節點，
- 調整平衡因子（插入在左孩子節點，平衡因子-1，插入到右孩子節點，平衡因子+1）
新節點插入到二叉搜索樹中:
插入的程序：根據搜索樹的性質找到空位置，將新節點插入到該空位置，
插入程序：
插入的代碼：
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果是空樹，直接插入
{
_root = new node(kv);
return true;
}
node* cur = _root;
node* parent = nullptr;
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;
}
}
node* newnode = new node(kv);//創建新的節點
newnode->parent = parent;//將新的節點與parent進行連接
if (parent->_kv.first > kv.first)//判斷新節點是連接在parent的左孩子還是右孩子
{
parent->_left = newnode;
parent->_bf--;//插入到parent的左孩子，parent的平衡因子-1
}
else if (parent->_kv.first < kv.first)
{
parent->_right = newnode;
parent->_bf++; //插入到parent的右孩子，parent的平衡因子 +1 1
}
.......
.......
}
當然，AVL樹中插入新節點后還需要保持是AVL樹，所以我們需要向上調整平衡因子，
在插入之前，parent的平衡與因子可能取值是0，1，-1（AVL樹的左右子樹的高度差不超過1）
插入時，parent的平衡因子的調整分為以下兩種情況
- 如果cur是插入到parent右節點，則parent的平衡因子加1
- 如果是插入到parent的左節點，平衡因子-1；
插入后，parent的平衡因子的可能取值是0，1，-1，2，-2.
- 如果parent的平衡因子是0，那么插入前的parent的平衡因子可能取值是1或者-1.插入后被調整為0，此時AVL樹高度不變，則插入成功， 如下圖：插入13節點后，parent高度不變，不需要往上更新平衡因子，
- 如果parent的平衡因子是-1或者+1,那么插入前的parent的平衡因子一定是0，此時高度增加，需要對parent上面的節點的平衡因子進行調整，如下圖插入25這個節點后，則parent的高度增加，則上面的節點的樹的高度也增加，需要調整上面的平衡因子，
- 如果parent的平衡因子是-2或2，那么parent則違反AVL樹的性質，需要對它進行旋轉使該樹保持平衡，旋轉后高度降低，不需要向上調整平衡因子，具體旋轉如下解釋，
旋轉可以分為右單旋，左單旋，右左雙旋，左右雙旋這4中旋轉
📚 3. 右單旋
新節點插入到較高的左子樹的左側，則需要進行有單旋，如下這種情況，
觸發右單旋的條件：parent的平衡因子為-2，sub的平衡因子為-1.
上面這個圖是抽象圖，a，b，c代表著數種情況，但總之，a，b，c的高度都為h，
在上圖插入之前，AVL樹是平衡的，但我們在節點30的左子樹插入一個節點后，導致以根節點的60的二叉平衡樹不平衡，即60的平衡因子為-2.并且新插入的節點是在左子樹的左子樹上，所以我們需要對它進行右單旋，
在旋轉的程序中，我們需要知道：60可能是根節點，也可能是是子樹
程序：parent連接subL中的右子樹，然后subL的右子樹連接parent,parent的parent連接subL,subL
的parent連接pparent，pparent連接subL需要根據以下三種情況討論，
右單旋的代碼實作：
void RightRevole(node* parent)
{
node* pparent = parent->parent;
node* subL = parent->_left;
parent->_left = subL->_right;//subL的右孩子連接到parent的左孩子節點上
if (pparent)//pparent不為空
{
if (pparent->_left == parent)//parent位于pparent左節點上
{
pparent->_left = subL;//subL連接到pparent的左孩孩子節點上
}
else if (pparent->_right == parent)//parent位于pparent右節點上
{
pparent->_right = subL;//subL連接到pparent的右孩孩子節點上
}
subL->parent = pparent;//pparent連接到subL的parent的節點上
}
else//pparent為nullptr
{
_root = subL;//subL直接變為根節點
subL->parent = nullptr;//subL的parent指向空
}
subL->_right = parent;//subL的右節點連接parent
parent->parent = subL;//parent的parent連接subL
subL->_bf = parent->_bf = 0;//subL和parent的平衡因子變為0
}📚 4. 左單旋
實際情況跟右單旋基本差不多的，只要看懂右單旋，左單旋也就會了，
左單旋的觸發條件是：parent的平衡因子為2，subR的平衡因子為1，
左單旋的程序：
void LeftRevole(node*& parent)
{
node* pparent = parent->parent;
node* subR = parent->_right;
parent->_right = subR->_left;
if (pparent)//pparent不為空
{
if (pparent->_left == parent)//parent為pparent的左孩子的節點上
pparent->_left = subR;//subR連接到pparent的左孩子節點上
else if (pparent->_right == parent)//parent為pparent的右孩子的節點上
pparent->_right = subR;//subR連接到pparent的右孩子節點上
subR->parent = pparent;//subR的parent連接pparent
}
else//pparent為空
{
_root = subR;//subR直接為根節點
_root->parent = nullptr;//_root的parent的指向空
}
subR->_left = parent;//subR的left連接parent
parent->parent = subR;//parent的parent連接subR
subR->_bf = parent->_bf = 0;//subR和parent的平衡因子變為為0
}📚 5. 左右雙旋
新節點插入到較高左子樹的右側上，此時的就需要進行左右雙旋，
左右雙旋的條件：parent的平衡因子為-2，subL的平衡因子為1.
程序：先對subL進行左單旋，然后在對parent進行右單旋，最后在調節平衡因子（下列中有分析），
例如下面這種情況：
左右單旋的平衡因子有三種情況：
- 如果新節點插入到subLR的左子樹（b子樹）上，旋轉前subLR的平衡因子為-1.那么結果如上圖所示,旋轉后subLR的平衡因子為0，subL的平衡因子為0，parent的平衡因子為1.
- 如果新節點插入到subLR的右子樹（c子樹）上，旋轉前subLR的平衡因子為1，如下圖所示，旋轉后subLR的平衡因子為0，subL的平衡因子為-1，parent的平衡因子為0.
3. 另外一種情況是subLR的平衡因子為0，通過左右旋轉后subLR,subL,parent的平衡因子都為0.
void LRrevole(node* parent)
{
node* subL = parent->_left;
node* subLR = parent->_left->_right;
LeftRevole(subL);//對subL進行左單旋
RightRevole(parent);//對parent進行右單旋
if (subLR->_bf == -1)//subLR的平衡因子為-1
{
parent->_bf = 1;
subLR->_bf = 0;
subL->_bf = 0;
}
else if (subLR->_bf == 1)//subLR的平衡因子為1
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (subLR->_bf == 0)//subLR的平衡因子
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
}📚 6. 右左雙旋
新節點插入到較高右子樹的左側，此時就需要進行右左雙旋，
右左雙旋的條件為：parent的平衡因子為2，subR的平衡因子為-1，
右左雙旋后的平衡因子有三種情況：
- 如果subRL的平衡因子為1，則旋轉后parent的平衡因子為-1，subR的平衡因子為0,subRL的平衡因子為0.
- 如果subRL的平衡因子為-1，則旋轉后parent的平衡因子為0，subR的平衡因子為1,subRL的平衡因子為0.
- 如果subRL的平衡因子為0，則旋轉后parent，subR和subRL的平衡因子都為0.
代碼實作：
void RLrevole(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
RightRevole(subR);//對subR的進行右單旋
LeftRevole(parent);//對parent進行左單旋
if (subRL->_bf == -1)//subRL的平衡因子為-1
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (subRL->_bf== 1)//subRL的平衡因子為1
{
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else if (subRL->_bf == 0)//subRL的平衡因子為0
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
}📚 7. 插入的總的代碼（含注釋）
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果是空樹，直接插入
{
_root = new node(kv);
return true;
}
node* cur = _root;
node* parent = nullptr;
while (cur)//cur不為空
{
if (cur->_kv.first > kv.first)//如果值小于該節點的值，則去它的左子樹尋找
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)//如果值大于該節點的值，則去它的右子樹尋找
{
parent = cur;
cur = cur->_right;
}
}
node* newnode = new node(kv);//創建新的節點
newnode->parent = parent;//將新的節點與parent進行連接
if (parent->_kv.first > kv.first)//判斷新節點是連接在parent的左孩子還是右孩子
{
parent->_left = newnode;
parent->_bf--;
}
else if (parent->_kv.first < kv.first)
{
parent->_right = newnode;
parent->_bf++;
}
//向上更新平衡因子
while (parent)
{
node* pparent = parent->parent;
if (parent->_bf == 0)//平衡因子等于0直接跳出回圈
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)//平衡因子為1或者-1，需要更新上面的平衡因子
{
if (pparent==nullptr)
{
break;
}
else if (pparent->_left == parent)//parent是位于pparent的左節點
{
pparent->_bf--;//pparent的平衡因子-1
}
else if (pparent->_right == parent)//parent是位于pparent的右節點
{
pparent->_bf++;//pparent的平衡因子+1
}
parent = pparent;//parent向上爬
}
else if (parent->_bf == 2 || parent->_bf == -2)//進行旋轉
{
if (parent->_bf == 2)//parent的平衡因子為2
{
if (parent->_right->_bf == 1)//parent的右孩子的平衡因子為1
{
//左單旋
LeftRevole(parent);
}
else if (parent->_right->_bf == -1)//parent的右孩子的平衡因子為-1
{
//先右旋在左單旋
RLrevole(parent);
}
}
else if (parent->_bf == -2)//parent的平衡因子為-2
{
if (parent->_left->_bf == -1)//parent的左孩子的平衡因子為-1
{
//右單旋
RightRevole(parent);
}
else if (parent->_left->_bf == 1)//parent的右孩子的平衡因子為1
{
//先左單旋在右單旋
LRrevole(parent);
}
}
break;//旋轉之后都是平衡樹，直接跳出回圈
}
}
}📚 8. AVL樹查找的代碼
node* find(const K& key)
{
node* cur = _root;
while (cur)
{
if (cur->_kf->first > key)//key值小于cur，到左子樹找
{
cur = cur->_left;
}
else if (cur->_kf->first < key)//key值大于cur，到右子樹找
{
cur = cur->_right;
}
else if (cur->_kf->first == key)//找到了，回傳該節點
{
return cur;
}
}
return nullptr;//找不到，回傳空
}📚 9. 洗掉
AVL樹的洗掉也是分為兩步：
- 找到要洗掉節點，將該節點洗掉，
- 調整平衡因子
洗掉AVL樹有四種情況：
情況一
洗掉的節點不存在左右子樹，
那么我們直接將該節點洗掉即可，例如我們要洗掉cur，我直接將cur洗掉掉即可，然后在調整parent的平衡因子，
情況二
要洗掉的節點只存在左子樹，不存在右子樹，
例如洗掉15這個節點，我們需要將subL和parent互相連接，然后parent的平衡因子+1或者-1.
程序如下：
情況三
要洗掉的節點只存在右子樹，不存在左子樹，
例如洗掉4這個節點，我們需要將subR和parent互相連接，然后parent的平衡因子+1或者-1.
程序如下：
情況四
要洗掉的節點存在左右子樹，
例如我們要洗掉11這個節點，我們可以找到cur右子樹上的最小值Rightmin（也就是右子樹上最左邊上的值）然后將該Rightmin節點的值賦值給cur這個節點,將Rightmin這個節點洗掉掉，在洗掉Rightmin節點之前，需要先讓parent指向Rightmin的parent，調整parent的平衡因子，因為我們洗掉的是Rightmin，是會影響Rightmin以上的平衡因子，
對parent及以上進行調整平衡因子：
在這里我們只討論左單旋跟右單旋其中兩種特殊情況旋轉后的平衡因子，其它的旋轉調整跟插入是一樣的，
在之前的插入，當parent的平衡因子為-2，subL的平衡因子為-1,才對parent節點進行左旋，左旋后的parent和subL的平衡因子都為0，當洗掉60的時候，parent節點的平衡因子為-2，就需要進行左旋，由于subL節點的平衡因子為0，所以它的左旋后的parent平衡因子變為-1，subL的平衡因子為1，如下圖：
洗掉前：
洗掉60節點后：
左旋轉后：
同樣的，當洗掉后parent平衡因子為2，subR的平衡因子為0，需要進行右旋，
洗掉13這個節點前：
洗掉13節點后：
進行右旋后：右旋后的parent的平衡因子為1，subR的平衡因子為-1.
每次旋轉后都不需要往上更新平衡因子，因為旋轉后高度都會降低，不會影響上面節點的平衡因子，
bool erase(const K& key)
{
node* cur = find(key);//查找cur
if (cur == nullptr)//找不到
{
return false;
}
//找到了
node* parent = cur->parent;
if (cur->_left == nullptr && cur->_right == nullptr)//如果要洗掉的節點的左右孩子為空
{
if (parent->_left == cur)//cur為parent的左邊，平衡因子+1
{
parent->_bf++;
}
else//cur為parent的右邊，平衡因子-1
{
parent->_bf--;
}
delete cur;//直接洗掉
cur = nullptr;
//平衡因子
}
else if (cur->_left && cur->_right)//要洗掉的節點中的左右孩子都存在
{
node* rightmin = cur->_right;//右子樹的最小節點
while (rightmin->_left)//查找右子樹的最小值
{
rightmin == rightmin->_left;
}
cur->_kv = rightmin->_kv;//將右子樹的最小值給要洗掉的節點，然后洗掉rightmin
parent = rightmin->parent;//rightmin的父親
if (rightmin->_right)//rightmin存在右子樹
{
node* right = rightmin->_right;
parent->_right = right;//將rightmin的右子樹給parent
right->parent = parent;//右子樹的父親連接parent
}
else
{
parent->_right = nullptr;//右子樹不存在，連接nullptr
}
delete rightmin;//直接洗掉rightmin
rightmin = nullptr;
parent->_bf--;//right的父親的平衡因子-1
}
else if (cur->_left)//cur的左子樹不為空，右子樹不存在
{
if (cur == _root)//cur為根節點
{
_root = cur->_left;
_root->parent = nullptr;
}
else//cur不是根節點
{
node* subL = cur->_left;//cur的左子樹
if (parent->_left == cur)//cur是parent的左子樹
{
parent->_left = subL;//parent的左子樹連接subL
parent->_bf++;//parent的平衡因子+1
}
else
{
parent->_right = subL;//parent的右子樹連接subL
parent->_bf--;//parent的平衡因子-1
}
subL->parent = parent;//subL的parent連接cur的parent
}
delete cur;
cur == nullptr;
}
else if (cur->_right)//cur的右子樹不為空，左子樹不存在
{
if (cur == _root)
{
_root = cur->_right;
_root->parent = nullptr;
}
else
{
node* subR = cur->_right;//cur的右子樹
if (parent->_left == cur)//cur是parent的左子樹
{
parent->_left = subR;//parent的左子樹連接subR
parent->_bf++;
}
else
{
parent->_right = subR;//parent的右子樹連接subR
parent->_bf--;
}
subR->parent = parent;
}
delete cur;
cur == nullptr;
}
//更新平衡因子
while (parent)//parent為nullptr，則停下來
{
node* pparent = parent->parent;
if (parent->_bf == 0)//平衡因子等于0
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
if (pparent == nullptr)//parent是根節點
{
break;
}
else if (pparent->_left == parent)//parent是pparent的左節點
{
pparent->_bf--;
}
else if (pparent->_right == parent)//parent是pparent的右節點
{
pparent->_bf++;
}
parent = pparent;//parent向上移動
}
else if (parent->_bf == 2 || parent->_bf == -2)//parent
{
if (parent->_bf == 2)
{
if (parent->_right->_bf == -1)//parent的右孩子節點的平衡因子為-1
{
//先右旋在左單旋
RLrevole(parent);
}
else //parent的右孩子節點的平衡因子為1或者0
{
//左單旋
node* subR = parent->_right;
LeftRevole(parent);
if (subR->_bf == 0)//parent的右孩子節點的平衡因子為0
{
//改變平衡因子
subR->_bf = -1;
parent->_bf = 1;
}
}
}
else if (parent->_bf == -2)
{
if (parent->_left->_bf == 1)
{
//先左單旋在右單旋
LRrevole(parent);
}
else //parent的右孩子節點的平衡因子為-1或者0
{
//右單旋
node* subL = parent->_left;
RightRevole(parent);
if (subL->_bf == 0)//parent的右孩子節點的平衡因子為0
{
parent->_bf = -1;
subL->_bf = 1;
}
}
}
break;//旋轉之后都是平衡樹，直接跳出回圈
}
}
}
下篇高階資料結構預告：手撕紅黑樹
感謝你的關注和收藏！！！
種一顆樹最后是十年前，其次是現在！！！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413900.html
標籤：其他
下一篇：常見的【記憶體泄漏】姿勢