C++數(shù)據(jù)結(jié)構(gòu)AVL樹全面分析
??博客代碼已上傳至gitee：https://gitee.com/byte-binxin/cpp-class-code
??概念
二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法：當向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點進行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
- 它的左右子樹都是AVL樹
- 左右子樹高度之差的絕對值（也叫平衡因子）不超過1
- 我規(guī)定：平衡因子（balance factor）= 右子樹高度 - 左子樹高度（后面這樣實現(xiàn)）
??AVL樹的實現(xiàn)
??AVL樹的節(jié)點定義
這里節(jié)點是一個三叉鏈，里面存放了元素的數(shù)據(jù)和該節(jié)點此時的平衡因子。不管今后我們進行什么操作，都要維持這里的平衡因子的絕對值不超過1。
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; // balance factor 平衡因子 右子樹高度-左子樹高度
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};??AVL樹的插入
??方法概述
第一步： 我們先按照二叉搜索樹樹插入節(jié)點的方式，插入節(jié)點（這一步很簡單，上一篇博客介紹過）
第二步： 更新平衡因子，更新平衡因子的過程是一個難點，下面我給大家分析一下整個過程
??平衡因子的調(diào)節(jié)
??正常情況
實際上，我們應(yīng)該能夠發(fā)現(xiàn)，插入一個節(jié)點后，它之后影響它祖先的平衡因子（可能是所有祖先，也可能是一部分祖先），下面就是一個分析過程：
第一步： 判斷父親節(jié)點是否存在，不存在直接結(jié)束，如果存在，且插入節(jié)點是它的左孩子，那么父親節(jié)點的平衡因子就減1，如果是父親的右，父親的平衡因子就加1。然后對父親節(jié)點的平衡因子進行檢索。
第二步： 繼續(xù)對父親節(jié)點的平衡因子進行檢索，平衡因子會有一下三種情況
第一種情況： 此時父親的平衡因子為0，則說明插入前父親的平衡因子為1或-1，缺少左節(jié)點或右節(jié)點插入后，插入的節(jié)點已經(jīng)補齊了左節(jié)點或右節(jié)點，整體高度不變，對上層無影響，不需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：
第二種情況 此時父親節(jié)點的平衡因子為-1或1，則說明插入前父親的平衡因子為0，插入后增加了一個左節(jié)點或右節(jié)點，整體高度增加1，對上層有影響，繼續(xù)迭代更新祖先的平衡因子。下面是一個演示圖：
第三種情況： 此時父親節(jié)點的平衡因子為-2或2，則說明插入前父親的平衡因子為-1或1，多了一個左節(jié)點或一個右節(jié)點，插入后增加了一個左節(jié)點或右節(jié)點，此時多了兩個左節(jié)點和右節(jié)點，這棵子樹一邊已經(jīng)被拉高了，此時這棵子樹不平衡了，需要旋轉(zhuǎn)處理。下面是一個演示圖：
??旋轉(zhuǎn)處理（出現(xiàn)了不平衡子樹）
旋轉(zhuǎn)有四種情況：
1.左單旋（新插入的節(jié)點在右子樹的右側(cè)）
具體步驟： 讓subR的左孩子成為parent的右孩子，然后讓parent成為subR的左孩子，最后把兩個節(jié)點的平衡因子修改為0.
先畫一個具像圖給大家演示如何進行這個操作（下面是一部分失衡的子樹）：
再畫一個抽像圖來演示：
代碼實現(xiàn)如下：
// 左單旋 bf為2 右邊高，把上面的壓下來放到左邊
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 1.先讓把subR的左邊（可能為空也可能不為空）作為parent的右邊
parent->_right = subRL;
// 2.如果subRL不為空，就讓subRL的父指針指向parent
if (subRL) subRL->_parent = parent;
// 3.先記錄parent的父節(jié)點的位置，然后把parent作為subR的左邊
Node* ppNode = parent->_parent;
subR->_left = parent;
// 4.parent的父指針指向subR
parent->_parent = subR;
// 5.如果ppNode為空==>說明subR現(xiàn)在是根節(jié)點，就讓subR的父指針指向nullptr
// 不是根節(jié)點就把subR的父指針指向parent的父節(jié)點，parent的父節(jié)點（左或右）指向subR
if (ppNode == nullptr)
{
// 更新根節(jié)點
_root = subR;
subR->_parent = nullptr;
}
else
{
// 判斷parent是ppNode的左還是右
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
// 6.把parent和subR的平衡因子更新為0
subR->_bf = parent->_bf = 0;
}2.右單旋 （新節(jié)點插入到較高左子樹的左側(cè)）
具體步驟： 讓subL的右孩子成為parent的左孩子，然后讓parent成為subL的右孩子，最后把兩個節(jié)點的平衡因子修改為0.
先畫一個具像圖給大家演示如何進行這個操作（下面是一部分失衡的子樹）：
在給大家演示一下抽象圖：
代碼實現(xiàn)如下：
// 右單旋 bf為-2 左邊高，把上面的壓下來放到右邊
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 1.先讓把subL的右邊（可能為空也可能不為空）作為parent的左邊
parent->_left = subLR;
// 2.如果subLR不為空，就讓subLR的父指針指向parent
if (subLR) subLR->_parent = parent;
// 3.先記錄parent的父節(jié)點的位置，然后把parent作為subL的右邊
Node* ppNode = parent->_parent;
subL->_right = parent;
// 4.parent的父指針指向subL
parent->_parent = subL;
// 5.如果ppNode為空==>說明subR現(xiàn)在是根節(jié)點，就讓subL的父指針指向nullptr
// 不是根節(jié)點就把subL的父指針指向parent的父節(jié)點，parent的父節(jié)點（左或右）指向subL
if (ppNode == nullptr)
{
// 更新根節(jié)點
_root = subL;
subL->_parent = nullptr;
}
else
{
// 判斷parent是ppNode的左還是右
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
// 6.把parent和subL的平衡因子更新為0
subL->_bf = parent->_bf = 0;
}3.右左雙旋（新節(jié)點插入在較高右子樹左側(cè)，這里和第一種情況的區(qū)別就是前者是直線，后者是折線）
具體步驟 先對subR進行一個右單旋，然后對parent進行左單旋，修改平衡因子，有三種改法。
三個節(jié)點從左至右的三個節(jié)點一次是：parent、subRL和subR。
如果subRL的平衡因子為0，就將它們依次改為0，0, 0；
如果subRL的平衡因子為1，就將它們依次改為-1，0, 0；
如果subRL的平衡因子為-1，就將它們依次改為0，0, 1。
先看具像圖：
再看一個抽象圖（兩種情況）：
subRL的bf為1
subRL的bf為-1
代碼實現(xiàn)如下：
// 右左旋轉(zhuǎn)==>parent->_bf==2&&cur->_bf==-1
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;// 保留subRL的平衡因子的值，方便知道新插入的節(jié)點是在subRL的左子樹還是右子樹
// 旋轉(zhuǎn) 先對subR進行右旋轉(zhuǎn)，再對parent進行左旋轉(zhuǎn)
RotateR(subR);
RotateL(parent);
// 從左到右 parent subRL subR
if (bf == -1)// subRL的左子樹 bf: 0 0 1
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)// subRL的右子樹 bf: -1 0 0
{
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 0;
}
}4.左右雙旋（新節(jié)點插入在較高右子樹左側(cè)，這里和第一種情況的區(qū)別就是前者是直線，后者是折線）
具體步驟先對subL進行一個左單旋，然后對parent進行右單旋，修改平衡因子，有三種改法。三個節(jié)點從左至右的三個節(jié)點一次是：subL、subLR和parent。（和上面的類似，這樣有助于我們記住平衡因子的調(diào)整，同時我們也可以畫簡圖理解記憶）
如果subLR的平衡因子為0，就將它們依次改為0，0, 0；
如果subLR的平衡因子為1，就將它們依次改為-1，0, 0；
如果subLR的平衡因子為-1，就將它們依次改為0，0, 1。
先看具像圖：
再看一個抽象圖（也有兩種情況）：
subLR的bf為-1
subLR的bf為1
代碼實現(xiàn)如下：
// 左右旋轉(zhuǎn)==>parent->_bf==-2&&cur->_bf==1
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的節(jié)點是在subLR的左子樹還是右子樹
// 旋轉(zhuǎn) 先對subL進行左旋轉(zhuǎn)，再對parent進行右旋轉(zhuǎn)
RotateL(subL);
RotateR(parent);
// 從左到右 subL subLR parent
if (bf == -1)// subLR的左子樹 bf: 0 0 1
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)// subLR的右子樹 bf: -1 0 0
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == 0)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
}??插入代碼實現(xiàn)
插入的步驟也就是如上面說的一樣，下面的代碼我們通過迭代實現(xiàn)。
代碼實現(xiàn)如下：
bool Insert(const pair<K, V>& kv)
{
// 先按照二叉搜索數(shù)一樣插入元素
// 無節(jié)點是插入
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
// 有節(jié)點時插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
// 小于往左走
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
// 大于往右走
else if (kv.first > cur->_kv.first)
{
cur = cur->_right;
}
else
{
// 找到了，就返回false
return false;
}
}
cur = new Node(kv);
// 判斷cur應(yīng)該插在parent的左還是右
// 小于在左，大于在右
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 更新parent的平衡因子
// 節(jié)點的插入只會影響cur的祖先的平衡因子（不是所有的，是一部分，分情況）
while (parent)
{
// 更新parent的平衡因子
// cur在parent的左，parent->_bf--
// cur在parent的右，parent->_bf++
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
// bf 可能為 -2、-1、0、1、2
// 如果平衡因子為0，說明更新之前，parent的bf為-1或1，現(xiàn)在補齊了左節(jié)點或右節(jié)點，bf==0，對上層無影響
// 如果平衡因子為-1或1，說明更新之前，parent的bf為0，現(xiàn)在增加了一個左節(jié)點或有節(jié)點，bf==-1 || bf==1,對上層有影響
// 如果平衡因子為-2或2，說明更新之前，parent的bf為-1或1，現(xiàn)在往左（右）節(jié)點補了左（右）節(jié)點，也就是一邊
// 拉高了，樹不平衡了，需要用左旋轉(zhuǎn)或右旋轉(zhuǎn)來進行調(diào)整
if (parent->_bf == 0)
{
// 對上層無影響，退出
break;
}
else if (parent->_bf == -1 || parent->_bf == 1)
{
// 對上層有影響，迭代更新
cur = parent;
parent = parent->_parent;
}
else
{
// 平衡樹出現(xiàn)了問題，需要調(diào)整
// 1.右邊高，左旋轉(zhuǎn)調(diào)整
if (parent->_bf == 2)
{
// 如果是一條直線==>左旋轉(zhuǎn)即可
// 如果是一條折線==>右左旋轉(zhuǎn)
if (cur->_bf == 1)
RotateL(parent);
else if (cur->_bf == -1)
RotateRL(parent);
}
// 2.左邊高，右旋轉(zhuǎn)調(diào)整
else if (parent->_bf == -2)
{
// 如果是一條直線==>右旋轉(zhuǎn)即可
// 如果是一條折線==>左右旋轉(zhuǎn)
if (cur->_bf == -1)
RotateR(parent);
else if (cur->_bf == 1)
RotateLR(parent);
}
// 調(diào)整后是平衡樹，bf為0，不需要調(diào)整了
break;
}
}
return bool;
}??AVL樹的查找
查找的代碼和二叉搜索樹是一樣的，這里就不過多介紹。
代碼實現(xiàn)如下：
bool Find(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
while (cur)
{
// 小于往左走
if (key < cur->_kv.first)
{
cur = cur->_left;
}
// 大于往右走
else if (key > cur->_kv.first)
{
cur = cur->_right;
}
else
{
// 找到了
return true;
}
}
return false;
}??AVL樹的刪除
??方法概述
第一步： 我們先按照二叉搜索樹樹刪除節(jié)點的方式，刪除節(jié)點（這一步很簡單，上一篇博客介紹過）
第二步： 然后根據(jù)對應(yīng)刪除情況更新平衡因子，這里更新平衡因子的方法與插入的更新方法是相反的，下面我給大家分析一下整個過程
??平衡因子的調(diào)節(jié)
??正常情況
刪除節(jié)點后，如果刪除的節(jié)點為根節(jié)點，就結(jié)束。否則根據(jù)刪除節(jié)點為父節(jié)點的左右調(diào)整父節(jié)點的平衡因子。如果刪除節(jié)點是父節(jié)點的左孩子，那么父親節(jié)點的平衡因子加1，否則減1。然后對父親節(jié)點進行檢索。
有以下幾種情況：
第一種情況： 此時父親的平衡因子為0，則說明刪除前父親的平衡因子為1或-1，多出一個左節(jié)點或右節(jié)點，刪除節(jié)點后，左右高度相等，整體高度減1，對上層有影響，需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：（如果此時3為根節(jié)點，那么也可以結(jié)束）
第二種情況： 此時父親的平衡因子為-1或1，則說明刪除前父親的平衡因子為0，左右高度相等，刪除節(jié)點后，少了一個左節(jié)點或右節(jié)點，但是整體高度不變，對上層無影響，不需要繼續(xù)調(diào)節(jié)。下面是一個演示圖：
第三種情況： 此時父親節(jié)點的平衡因子為-2或2，則說明刪除前父親的平衡因子為-1或1，多了一個左節(jié)點或一個右節(jié)點，刪除了一個右節(jié)點或左節(jié)點，此時多了兩個左節(jié)點和右節(jié)點，這棵子樹一邊已經(jīng)被拉高了，此時這棵子樹不平衡了，需要旋轉(zhuǎn)處理。下面是一個演示圖：
??需要旋轉(zhuǎn)處理的幾種情況
這里我只分析右邊高的情況，左邊高和它對稱的，操作是相同的。
情況一：
操作方法： 對parent進行左旋轉(zhuǎn)，因為subR的平衡因子為0，需要繼續(xù)檢索，然后繼續(xù)迭代，把cur迭代sub的位置，parent到cur的父親的位置
具像圖：
抽象圖：
情況二：
操作方法： 對parent進行左旋，然后修改平衡因子，把subR的平衡因子改為-1，parent的平衡因子改為1，因為subR的平衡因子為-1，所以無需迭代，直接結(jié)束
具像圖：
抽象圖：
情況三：
操作方法： 對subR進行右旋，然后對parent進行左旋，此時subR的平衡因子為0，需迭代
具像圖：
抽象圖：
??刪除代碼如下
刪除代碼如下：
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
// 有節(jié)點時插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 小于往左走
if (key < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
// 大于往右走
else if (key > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了
// 1.左邊為空，把parent指向cur的右
// 2.右邊為空，把parent指向cur的左
// 3.左右都不為空，用右子樹的最左邊的節(jié)點（最小節(jié)點）的值替換要刪除的節(jié)點，然后轉(zhuǎn)換為用1的情況刪除該節(jié)點
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
delete cur;
break;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
parent->_bf++;
}
else
{
parent->_right = cur->_right;
parent->_bf--;
}
}
if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent);
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
delete cur;
break;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
parent->_bf++;
}
else
{
parent->_right = cur->_left;
parent->_bf--;
}
}
if (parent->_bf != -1 && parent->_bf != 1) AfterEraseUpdateBf(parent);
delete cur;
}
else
{
Node* rightMinParent = cur;
Node* rightMin = cur->_right;// 先去右子樹
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;// 一種往左走
}
cur->_kv = rightMin->_kv;
// 替代刪除
// 刪除minNode 第一種情況：左節(jié)點為空
if (rightMinParent->_left == rightMin)
{
rightMinParent->_left = rightMin->_right;
rightMinParent->_bf++;
}
else
{
rightMinParent->_right = rightMin->_right;
rightMinParent->_bf--;
}
if (rightMinParent->_bf != -1 && rightMinParent->_bf != 1) AfterEraseUpdateBf(rightMinParent);
delete rightMin;
}
return true;
}
}
return false;
}
void AfterEraseUpdateBf(Node* parent)
{
if (parent == nullptr)
return;
Node* cur = parent;
goto first;
while (parent)
{
// 更新parent的平衡因子
// cur在parent的左，parent->_bf++
// cur在parent的右，parent->_bf--
if (cur == parent->_left)
parent->_bf++;
else
parent->_bf--;
// bf 可能為 -2、-1、0、1、2
// 如果平衡因子為0，說明更新之前，parent的bf為-1或1，現(xiàn)在刪掉了左節(jié)點或右節(jié)點，整體高度變了，對上層有影響
// 如果平衡因子為-1或1，說明更新之前，parent的bf為0，現(xiàn)在刪掉了一個左節(jié)點或有節(jié)點，整體高度不變，對上層無影響
// 如果平衡因子為-2或2，說明更新之前，parent的bf為-1或1，現(xiàn)在往左（右）節(jié)點補了左（右）節(jié)點，也就另一邊
// 拉高了，樹不平衡了，需要用左旋轉(zhuǎn)或右旋轉(zhuǎn)來進行調(diào)整
first:
if (parent->_bf == 0)
{
// 對上層有影響，迭代更新
// 如果parent是根節(jié)點就結(jié)束
if (parent->_parent == nullptr)
break;
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -1 || parent->_bf == 1)
{
// 對上層無影響，退出
break;
}
else
{
// 平衡樹出現(xiàn)了問題，需要調(diào)整
// 1.右邊高，左旋轉(zhuǎn)調(diào)整
if (parent->_bf == 2)
{
// 如果是一條直線==>左旋轉(zhuǎn)即可
// 如果是一條折線==>右左旋轉(zhuǎn)
if (parent->_right->_bf == 1)
{
RotateL(parent);
cur = parent->_parent;
parent = cur->_parent;
continue;
}
else if (parent->_right->_bf == -1)// 調(diào)整后 p sL s 如果sL是1或-1可以退出
{
Node* s = parent->_right;
Node* sL = s->_left;
RotateRL(parent);
// 不平衡向上調(diào)整 注意：bug1（以為調(diào)整完就是1或-1了，其實這里不是，畫圖思考一下）
//if (sL->_bf != 1 && sL->_bf != -1)
{
cur = sL;
parent = cur->_parent;
continue;
}
}
else if (parent->_right->_bf == 0)// 旋轉(zhuǎn)后平衡因子要修改，畫圖感受 parent: 1 parent->_parent:- 1
{
RotateL(parent);
parent->_bf = 1;
parent->_parent->_bf = -1;
}
}
// 2.左邊高，右旋轉(zhuǎn)調(diào)整
else if (parent->_bf == -2)
{
// 如果是一條直線==>右旋轉(zhuǎn)即可
// 如果是一條折線==>左右旋轉(zhuǎn)
if (parent->_left->_bf == -1)
{
RotateR(parent);
cur = parent->_parent;// bug2 cur要變成這個位置是因為選擇后父親的位置變了，畫圖
parent = cur->_parent;
continue;//parent不是-1或1就繼續(xù)
}
else if (parent->_left->_bf == 1)// 調(diào)整后 s sR p 如果sL是1或-1可以退出
{
Node* s = parent->_left;
Node* sR = s->_right;
RotateLR(parent);
// 不平衡向上調(diào)整 為0時如果parent為根
//if (sR->_bf != 1 && sR->_bf != -1)
{
cur = sR;
parent = cur->_parent;
continue;
}
}
else if (parent->_left->_bf == 0)// 平衡因子要修改，畫圖感受 parent->_parent: 1 parent: -1
{
RotateR(parent);
parent->_parent->_bf = 1;
parent->_bf = -1;
}
}
// 調(diào)整后是平衡樹，bf為1或-1，不需要調(diào)整了
break;
}
}
}??AVL樹的測試代碼
下面是驗證是否為AVL樹的代碼：
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return 1 + max(leftHeight, rightHeight);
}
bool _IsBalanceTree(Node* root)
{
if (root == nullptr)
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return rightHeight - leftHeight == root->_bf
&& abs(rightHeight - leftHeight) < 2
&& _IsBalanceTree(root->_left)
&& _IsBalanceTree(root->_right);
}實例演示：
void TestAVLTree1()
{
AVLTree<int, int> at;
srand((size_t)time(nullptr));
// int a[] = { 4,3,5,3,1,2,7 };
// int a[] = { 1,2,3,4,5,6,7,8,9 };
// int a[] = { 2,4,6,3,5,1,9,10,8,7 };
// int a[] = { 4,2,3,5 };
// int a[] = { 16,3,7,11,9,26,18,14,15 };
// int a[] = { 4,2,6,1,3,5,15,7,16,14 };
// int* a = new int[10000];
/*int i = 1;
for (auto& e : a)
{
e = i++;
}*/
vector<int> a;
for (size_t i = 0; i < 13; ++i)
{
// a.push_back(rand());
a.push_back(13);
}
for (auto e : a)
{
int begin = clock();
pair<AVLTreeNode<int, int>*, bool> ret = at.Insert(make_pair(e, e));
int end = clock();
// cout << ret.first->_kv.second << endl;
// cout << ret.first->_kv.second << ":" << ret.second << endl;
cout << "插入 " << e << " 后變化 --> Height: " << at.Height() << " 是否為AVLTree：" << at.IsBalanceTree();
cout << " 用時: " << end - begin << "ms" << endl;
}
cout << "------------------------------------------------------" << endl;
// at.InOrder();
for (auto e : a)
{
if (e == 11478)
{
int a = 0;
}
int begin = clock();
at.Erase(e);
int end = clock();
cout << "刪除 " << e << " 后變化 --> Height: " << at.Height() << " 是否為AVLTree：" << at.IsBalanceTree();
cout << " 用時: " << end - begin << "ms" << endl;
}
at.InOrder();
}代碼運行結(jié)果如下：
??總結(jié)
AVL樹的全部內(nèi)容就介紹到這，圖畫了一下午，創(chuàng)造不易，感謝支持，下一篇博客更新紅黑樹的相關(guān)內(nèi)容，喜歡的話，歡迎點贊支持~
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)AVL樹全面分析的文章就介紹到這了,更多相關(guān)C++ AVL樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家介紹了C語言基礎(chǔ)的類型轉(zhuǎn)換，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-11-11
本文主要介紹C語言 結(jié)構(gòu)體的知識，學習C語言肯定需要學習結(jié)構(gòu)體，這里詳細說明了結(jié)構(gòu)體并附示例代碼，供大家參考學習，有需要的小伙伴可以參考下2021-10-10
這篇文章主要介紹了C++?DLL注入工具的相關(guān)資料,并向大家分享了完整的源碼，具有一定的參考價值，希望對正在工作或?qū)W習的你有所幫助2022-02-02
這篇文章主要介紹了C語言實現(xiàn)掃雷游戲詳細代碼實例，有感興趣的同學可以借鑒參考下2021-02-02
這篇文章主要介紹了C++賦值運算符,C++當中允許類對象賦值，這是通過默認的重載賦值運算符實現(xiàn)的,下面我們就來介紹介紹該內(nèi)容吧，,需要的朋友可以參考一下2022-01-01
這篇文章主要為大家介紹了C/C++開發(fā)中extern一些使用注意事項的事例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
這篇文章主要介紹了解決scanf_s輸入%d%c%d格式錯誤的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
這篇文章主要介紹了C++實現(xiàn)遺傳算法，以實例形式較為詳細的分析了遺傳算法的C++實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-12-12
C++中為何推薦要把基類析構(gòu)函數(shù)設(shè)置成虛函數(shù)
這篇文章主要介紹了C++中為何推薦要把基類析構(gòu)函數(shù)設(shè)置成虛函數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
本文給大家分享的是使用C++實現(xiàn)簡單的圖書管理系統(tǒng)的代碼，本系統(tǒng)采用了面向?qū)ο蟮某绦蛟O(shè)計方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2015-08-08