前言

本篇博客將為大家詳細(xì)講述AVL樹是什么以及其相對于普通的二叉搜索樹有什么優(yōu)點(diǎn)，將詳細(xì)講述其擁有哪些性質(zhì)，并且通過模擬實(shí)現(xiàn)的方式讓大家對該數(shù)據(jù)結(jié)構(gòu)有更深入的理解和認(rèn)識，對于該數(shù)據(jù)結(jié)構(gòu)的增刪查改操作，其中的刪除操作是在普通搜索二叉樹的基礎(chǔ)上進(jìn)行一些改進(jìn)，會簡單提及，但不會細(xì)講，重點(diǎn)將會講述插入操作，查和改操作和二叉搜索樹一模一樣，也不做講解。

由于AVL樹是一棵特殊的二叉搜索樹，因此想要學(xué)習(xí)AVL樹需要先知道二叉搜索樹是什么東西，如果有不知道二叉搜索樹是什么的小伙半可以先看看博主的另一篇博客:
數(shù)據(jù)結(jié)構(gòu)—— 二叉搜索樹(附c++模擬實(shí)現(xiàn))
該篇博客詳細(xì)介紹了二叉搜索樹。

AVL樹的概念

我們知道，二叉搜索樹雖然可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序，那么此時二叉搜索樹將會退化成單支樹，此時的查找效率和在鏈表中搜索等同，效率低下，因此，兩位俄羅斯的數(shù)學(xué)家(G.M.Adelson-Velskii 和E.M.Landis)在1962年的時候發(fā)明了一種解決上述問題的方法：

當(dāng)向二叉搜索樹中插入新節(jié)點(diǎn)后，如果能夠保證每個節(jié)點(diǎn)的左右子樹高度差的絕對值不超過1(在不破壞二叉搜素樹性質(zhì)的情況下對樹中節(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。

因此，AVL樹就這樣誕生了！
一棵AVL樹可以是空樹，或者是具有如下性質(zhì)的搜索二叉樹：

• 它的左右子樹都是AVL樹
• 左右子樹高度之差的絕對值超過1

因此，對于一棵AVL樹，最重要的就是如何控制每棵樹左右子樹高度之差都不超過1，這種控制是通過翻轉(zhuǎn)操作來實(shí)現(xiàn)的，博主在下文會重點(diǎn)講解。

另外，AVL樹的實(shí)現(xiàn)方式有兩種，一種就是在插入的過程中動態(tài)的檢查左右子樹的高度差是否超過1，另外一種就是引入一個新的概念——平衡因子，對于每個節(jié)點(diǎn)都存儲一個int值表示該根節(jié)點(diǎn)左右子樹的高度差，負(fù)數(shù)代表左子樹更高，正數(shù)代表右子樹更高，然后在插入的過程中不斷維護(hù)每個節(jié)點(diǎn)的平衡因子即可。

這里由于第二種方法實(shí)現(xiàn)起來相對邏輯更加清晰，所以我們采用第二種方法進(jìn)行模擬實(shí)現(xiàn)，并且用key_value的模型進(jìn)行實(shí)現(xiàn)

AVL樹節(jié)點(diǎn)的定義

和普通二叉搜索樹節(jié)點(diǎn)定義不同的是，AVL樹的節(jié)點(diǎn)為了方便進(jìn)行旋轉(zhuǎn)操作，需要多加一個指針指向其雙親節(jié)點(diǎn)，并且還要有一個int值表示平衡因子，定義如下：

template<typename K, typename V>
struct TreeNode
{pair<K, V> _kv;TreeNode<K, V>* _parent = nullptr;TreeNode<K, V>* _left = nullptr;TreeNode<K, V>* _right = nullptr;int _bf = 0;          //balance factorTreeNode(const K& key, const V& value):_kv({ key, value }){}
};

AVL樹類框架

template<typename K, typename V>
class AVL_Tree
{typedef TreeNode<K, V> node;
private:node* _root = nullptr;
public:bool insert(const pair<K, V>& kv)	void inorder();void is_AVL();
};

AVL樹的插入

AVL樹就是在二叉搜索樹的基礎(chǔ)上引入平衡因子，因此插入過程其實(shí)可以分成兩步：

1. 按照二叉搜索樹的方式插入新節(jié)點(diǎn)
2. 調(diào)整節(jié)點(diǎn)的平衡因子

對于第一步按照二叉搜索樹的規(guī)則插入新節(jié)點(diǎn)的步驟這里不進(jìn)行詳解，這里重點(diǎn)講解如何調(diào)整插入節(jié)點(diǎn)后各個AVL樹節(jié)點(diǎn)的平衡因子。

pCur表示新插入的節(jié)點(diǎn)，pParent表示新插入節(jié)點(diǎn)的父節(jié)點(diǎn)，（需要找到父節(jié)點(diǎn)是節(jié)點(diǎn)定義時需要定義指向雙親的指針的原因之一）。
pCur插入后， pParent的平衡因子一定需要調(diào)整，插入之前，pParent的平衡因子分為三種情況(-1/0/1)，而根據(jù)pCur插入位置的不同，可以分為以下兩種情況：

1. 如果pCur插入到pParent的左側(cè)，只需要給pParent的平衡因子減一
2. 如果pCur插入到pParent的右側(cè)，只需要給pParent的平衡因子加一

pParent的平衡因子經(jīng)過修改后，可能會出現(xiàn)五種情況，0，±1，±2

1. 如果pParent的平衡因子為0，說明修改后以pParent為根節(jié)點(diǎn)的最高高度并沒有發(fā)生變化，所以無需繼續(xù)調(diào)整，插入成功
   如下圖所示：
2. 如果插入后pParent的平衡因子為±1，說明插入前pParent的平衡因子一定是0，插入后被更新成±1，說明插入后以pParent為根的子樹高度增加了1，也就是說我們需要繼續(xù)向上更新祖先節(jié)點(diǎn)的平衡因子
   如下圖所示:
   
   這個過程將不斷循環(huán)，直到一直更新到pParent的平衡因子為0或者pParent更新到根節(jié)點(diǎn)為止。

3. 如果pParent的平衡因子為±2，那么此時以pParent為根的樹已經(jīng)不滿足AVL樹的性質(zhì)了，此時，就需要進(jìn)行旋轉(zhuǎn)操作，對于旋轉(zhuǎn)是什么，我們在下一個小節(jié)進(jìn)行講解，這里先給出插入代碼整體框架：

	bool insert(const pair<K, V>& kv){//如果頭節(jié)點(diǎn)為空，直接將值賦給頭節(jié)點(diǎn)即可if (!_root){node* newNode = new node(kv.first, kv.second);_root = newNode;return true;}//如果不為空，尋找插入位置node* parent = nullptr, *cur = _root;while (cur){auto& key = cur->_kv.first;parent = cur;if (kv.first > key)cur = cur->_right;else if (kv.first < key)cur = cur->_left;else return false;}node* newNode = new node(kv.first, kv.second);//循環(huán)結(jié)束，找到插入位置if (parent->_kv.first < kv.first)parent->_right = newNode;elseparent->_left = newNode;newNode->_parent = parent;cur = newNode;//更新平衡因子while (parent){//先修改因子//判斷新增節(jié)點(diǎn)的方位對parent的平衡因子進(jìn)行處理if (parent->_right == cur)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0) break;//如果parent的平衡因子為±1，繼續(xù)處理else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){//此時以pParent為根的子樹已經(jīng)違反了AVL樹的特性，需要進(jìn)行旋轉(zhuǎn)處理//...}//由于平衡因子的情況只有以上五種，出現(xiàn)其他種類的平衡因子說明AVL樹已經(jīng)被破壞//通過拋異常來顯示else throw "the bf out_of_range";}return true;}

AVL樹的旋轉(zhuǎn)

上一小節(jié)說到，在一棵本來是平衡的AVL樹中插入一個新節(jié)點(diǎn)，可能導(dǎo)致不平衡，必須調(diào)整樹的結(jié)構(gòu)，使之平衡，這一步也叫做旋轉(zhuǎn)，AVL樹的旋轉(zhuǎn)也分為四種：

旋轉(zhuǎn)的本質(zhì)其實(shí)是使高度較高的子樹高度降低，然后將降低的高度給到其另一個較低的子樹

新節(jié)點(diǎn)插入較高子樹的左側(cè) —— 左左: 右單旋

上圖是左單旋的普遍思路，但是我們還需要考慮一些特殊場景:

1. 30的右孩子可能存在，也可能不存在
2. 60可能是根節(jié)點(diǎn)，也可能是子樹
   如果60是根節(jié)點(diǎn)，旋轉(zhuǎn)完成之后需要更新根節(jié)點(diǎn)，如果60是子樹，可能是左子樹也可能是右子樹，需要注意更改上面的鏈接關(guān)系

這里大家可以自行畫圖模擬一下各種特殊場景，至于為什么要考慮這些場景，是因?yàn)殡m然整個思路很簡單，但是由于我們整棵樹是以三叉鏈的形式來存儲的，所以修改過程中需要維護(hù)這一結(jié)構(gòu)。
下面是右旋代碼：

void reverseR(node* parent)
{node* cur = parent->_left, *ppnode = parent->_parent;node* curR = cur->_right;//連接parent和curRparent->_left = curR;if (curR)curR->_parent = parent;//連接cur和parentcur->_right = parent;parent->_parent = cur;//連接ppnode和curcur->_parent = ppnode;if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;}else_root = cur;//跟新bfparent->_bf = cur->_bf = 0;
}

新節(jié)點(diǎn)插入較高右子樹的右側(cè)——右右: 左單旋

由于右單旋和左單旋基本類似，這里不進(jìn)行細(xì)致講解，下面是實(shí)現(xiàn)代碼:

void reverseL(node* parent)
{node* ppnode = parent->_parent, *cur = parent->_right;node* curL = cur->_left;// 連接parent和curLeftparent->_right = curL;if (curL) curL->_parent = parent;// 連接parent和curcur->_left = parent;parent->_parent = cur;//跟新parent和cur的平衡因子parent->_bf = cur->_bf = 0;//更新根節(jié)點(diǎn)或者與ppnode的連接關(guān)系if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;cur->_parent = ppnode;}else{_root = cur;cur->_parent = nullptr;}
}

新節(jié)點(diǎn)插入較高左子樹的右側(cè) —— 左右： 先左單旋然后再有單旋

其次，對于右左單旋來說還有一個需要考慮的點(diǎn)就是平衡因子的更新，對于這個問題，我們可以先總結(jié)一下上圖，（90作為pParent, 30作為pCur, 60作為curR）左右單旋的結(jié)果其實(shí)使把curR的左子樹與pCur鏈接，curR的右子樹與pParent鏈接，然后curR作為新樹的根，那么平衡因子的修改就需要根據(jù)60的平衡因子為狀況進(jìn)行修改了,curR的平衡因子一共有三種情況(-1/0/1).我們逐步分析：

1. curR是新插入的節(jié)點(diǎn) —— curR的平衡因子是0，相當(dāng)于上圖中h等于0的情況

插入后pParent，pCur和curR的平衡因子都變成0

2. 插入在curR的左子樹 —— curR的平衡因子是-1

由于插入后curR的左子樹交給了pCur，也就是上圖中的情況，此時pCur和curR的平衡因子都變成0，pParent的平衡因子變成1

3. 插入在curR的右子樹——curR的平衡因子是1

對應(yīng)的就是上圖中c的高度是h, b的高度是h - 1, 此時pParent 和 curR的平衡因子都變成0， pCur的平衡因子變成-1

因此，旋轉(zhuǎn)后平衡因子的改變是根據(jù)curR的平衡因子的狀況就行分類修改的，并且由于上文中我們定義了左右旋轉(zhuǎn)的函數(shù)，直接復(fù)用就可以得到左右單選的函數(shù)，代碼如下:

	void reverseRL(node* parent){node* cur = parent->_right, * curL = cur->_left;int bf = curL->_bf;reverseR(cur);reverseL(parent);if (bf == 0)cur->_bf = parent->_bf = curL->_bf = 0;else if (bf == -1){cur->_bf = 1;parent->_bf = curL->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = curL->_bf = 0;}elsethrow "balance factor out_of_range";}

新節(jié)點(diǎn)插入較高右子樹的左側(cè)：右左單旋

這里的思考方式和右左單選相同，留給大家自己思考。

旋轉(zhuǎn)總結(jié)

假如以pParent為根的子樹不平衡，即pParent的平衡因子為±2，分以下情況考慮：

1. pParent的平衡因子為2，說明pParent的右子樹高，設(shè)pParent的右子樹的根為pCur

• 當(dāng)pCur的平衡因子為1是，執(zhí)行左單旋
• 如果是-1，執(zhí)行右左單選

2. pParent的平衡因子為-2，說明pParent的左子樹高，設(shè)pParent的左子樹的根為pCur

• 當(dāng)pCur的平衡因子為-1時，執(zhí)行右單旋
• 當(dāng)pCur的平衡因子為1時，執(zhí)行左右單旋
  另外，我們可以發(fā)現(xiàn)旋轉(zhuǎn)完成之后，當(dāng)前根的平衡因子都變成了0，因此不需要繼續(xù)向上更新

AVL樹插入完整代碼

public:bool insert(const pair<K, V>& kv){//如果頭節(jié)點(diǎn)為空，直接將值賦給頭節(jié)點(diǎn)即可if (!_root){node* newNode = new node(kv.first, kv.second);_root = newNode;return true;}//如果不為空，尋找插入位置node* parent = nullptr, *cur = _root;while (cur){auto& key = cur->_kv.first;parent = cur;if (kv.first > key)cur = cur->_right;else if (kv.first < key)cur = cur->_left;else return false;}node* newNode = new node(kv.first, kv.second);//循環(huán)結(jié)束，找到插入位置if (parent->_kv.first < kv.first)parent->_right = newNode;elseparent->_left = newNode;newNode->_parent = parent;cur = newNode;//更新平衡因子while (parent){//先修改因子//判斷新增節(jié)點(diǎn)的方位對parent的平衡因子進(jìn)行處理if (parent->_right == cur)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0) break;//如果parent的平衡因子為±1，繼續(xù)處理else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){//進(jìn)行翻轉(zhuǎn)操作if (parent->_bf == 2 && cur->_bf == 1) reverseL(parent);else if (parent->_bf == -2 && cur->_bf == -1)reverseR(parent);else if (parent->_bf == 2 && cur->_bf == -1) reverseRL(parent);else if (parent->_bf == -2 && cur->_bf == 1) reverseLR(parent);break;}//由于平衡因子的情況只有以上五種，出現(xiàn)其他種類的平衡因子說明AVL樹已經(jīng)被破壞//通過拋異常來顯示else throw "the bf out_of_range";}return true;}
private:void reverseL(node* parent){node* ppnode = parent->_parent, *cur = parent->_right;node* curL = cur->_left;// 連接parent和curLeftparent->_right = curL;if (curL) curL->_parent = parent;// 連接parent和curcur->_left = parent;parent->_parent = cur;//跟新parent和cur的平衡因子parent->_bf = cur->_bf = 0;//更新根節(jié)點(diǎn)或者與ppnode的連接關(guān)系if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;cur->_parent = ppnode;}else{_root = cur;cur->_parent = nullptr;}}void reverseR(node* parent){node* cur = parent->_left, *ppnode = parent->_parent;node* curR = cur->_right;//連接parent和curRparent->_left = curR;if (curR)curR->_parent = parent;//連接cur和parentcur->_right = parent;parent->_parent = cur;//連接ppnode和curcur->_parent = ppnode;if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;}else_root = cur;//跟新bfparent->_bf = cur->_bf = 0;}void reverseRL(node* parent){node* cur = parent->_right, * curL = cur->_left;int bf = curL->_bf;reverseR(cur);reverseL(parent);if (bf == 0)cur->_bf = parent->_bf = curL->_bf = 0;else if (bf == -1){cur->_bf = 1;parent->_bf = curL->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = curL->_bf = 0;}elsethrow "balance factor out_of_range";}void reverseLR(node* parent){node* cur = parent->_left;node* curR = cur->_right;int bf = curR->_bf;reverseL(cur);reverseR(parent);if (bf == 0)cur->_bf = parent->_bf = curR->_bf = 0;else if (bf == -1){parent->_bf = -1;cur->_bf = curR->_bf = 0;}else if (bf == 1){cur->_bf = 1;curR->_bf = parent->_bf = 0;}else throw"balance factor out_of_range";}

AVL樹的驗(yàn)證

可以通過監(jiān)視窗口進(jìn)行驗(yàn)證，但是這樣過于麻煩，我們可以設(shè)計一個驗(yàn)證函數(shù)：

驗(yàn)證其為二叉搜索樹

如果中序遍歷能夠得到一個有序序列，那就說明是二叉搜索樹

public:void inorder() {_inorder(_root); cout << endl;return;}
private:void _inorder(node* root){if (!root) return;_inorder(root->_left);cout << root->_kv.first << ' ' << root->_kv.second << endl;_inorder(root->_right);}

驗(yàn)證其為平衡樹

• 每個節(jié)點(diǎn)子樹的高度絕對值不超過1
• 驗(yàn)證節(jié)點(diǎn)的平衡因子是否計算正確
  博主采用的是回溯的方法來驗(yàn)證，先驗(yàn)證左子樹和右子樹是否為AVL_Tree，同時返回該樹的高度，用于驗(yàn)證上層的樹是否為AVL_Tree。
  代碼如下:

public:void is_AVL() {auto ret = _is_AVL(_root); if (ret.second) cout << "this tree is AVL_tree\n";}
private:pair<int, bool> _is_AVL(node* root){pair<int, bool> ret{ 0, true };if (!root) return ret;auto ret_left = _is_AVL(root->_left);auto ret_right = _is_AVL(root->_right);ret.second = ret_left.second && ret_right.second;//判斷平衡因子是否正確int ans_bf = ret_right.first - ret_left.first;if (ans_bf != root->_bf){printf("平衡因子計算錯誤，正確平衡因子: %d, 當(dāng)前平衡因子:%d", ans_bf, root->_bf);ret.second = false;}if (abs(ans_bf) >= 2){cout << "平衡因子超過最大值\n";ret.second = false;}ret.first = max(ret_left.first, ret_right.first) + 1;return ret;}

AVL樹的刪除

因?yàn)锳VL樹也是搜索二叉樹，所以可以按照搜索二叉樹的方式將節(jié)點(diǎn)刪除，然后只需要加入更新平衡因子的步驟就可以了，比較不同的是刪除操作下平衡因子的更新是如果刪除后節(jié)點(diǎn)的平衡因子為0還需要繼續(xù)更新，而如果是±1不需要繼續(xù)更新，±2進(jìn)行旋轉(zhuǎn)，但是旋轉(zhuǎn)完成之后由于根的平衡因子變成了0，還有可能需要繼續(xù)向上更新。

AVL樹的性能

AVL樹是一棵絕對平衡的二叉搜索樹，其要求每個節(jié)點(diǎn)的左右子樹高度差的絕對值都不超過1，這 樣可以保證查詢時高效的時間復(fù)雜度，即$lo{g}_2(N)$。但是如果要對AVL樹做一些結(jié)構(gòu)修改的操 作，性能非常低下，比如：插入時要維護(hù)其絕對平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時， 有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。因此：如果需要一種查詢高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù) 據(jù)的個數(shù)為靜態(tài)的(即不會改變)，可以考慮AVL樹，但一個結(jié)構(gòu)經(jīng)常修改，就不太適合。

完整實(shí)現(xiàn)代碼

template<typename K, typename V>
struct TreeNode
{pair<K, V> _kv;TreeNode<K, V>* _parent = nullptr;TreeNode<K, V>* _left = nullptr;TreeNode<K, V>* _right = nullptr;int _bf = 0;TreeNode(const K& key, const V& value):_kv({ key, value }){}
};template<typename K, typename V>
class AVL_Tree
{typedef TreeNode<K, V> node;
private:node* _root = nullptr;
public:bool insert(const pair<K, V>& kv){//如果頭節(jié)點(diǎn)為空，直接將值賦給頭節(jié)點(diǎn)即可if (!_root){node* newNode = new node(kv.first, kv.second);_root = newNode;return true;}//如果不為空，尋找插入位置node* parent = nullptr, *cur = _root;while (cur){auto& key = cur->_kv.first;parent = cur;if (kv.first > key)cur = cur->_right;else if (kv.first < key)cur = cur->_left;else return false;}node* newNode = new node(kv.first, kv.second);//循環(huán)結(jié)束，找到插入位置if (parent->_kv.first < kv.first)parent->_right = newNode;elseparent->_left = newNode;newNode->_parent = parent;cur = newNode;//更新平衡因子while (parent){//先修改因子//判斷新增節(jié)點(diǎn)的方位對parent的平衡因子進(jìn)行處理if (parent->_right == cur)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0) break;//如果parent的平衡因子為±1，繼續(xù)處理else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){//進(jìn)行翻轉(zhuǎn)操作if (parent->_bf == 2 && cur->_bf == 1) reverseL(parent);else if (parent->_bf == -2 && cur->_bf == -1)reverseR(parent);else if (parent->_bf == 2 && cur->_bf == -1) reverseRL(parent);else if (parent->_bf == -2 && cur->_bf == 1) reverseLR(parent);break;}//由于平衡因子的情況只有以上五種，出現(xiàn)其他種類的平衡因子說明AVL樹已經(jīng)被破壞//通過拋異常來顯示else throw "the bf out_of_range";}return true;}void inorder() {_inorder(_root); cout << endl;return;}void is_AVL() {auto ret = _is_AVL(_root); if (ret.second) cout << "this tree is AVL_tree\n";}
private:void reverseL(node* parent){node* ppnode = parent->_parent, *cur = parent->_right;node* curL = cur->_left;// 連接parent和curLeftparent->_right = curL;if (curL) curL->_parent = parent;// 連接parent和curcur->_left = parent;parent->_parent = cur;//跟新parent和cur的平衡因子parent->_bf = cur->_bf = 0;//更新根節(jié)點(diǎn)或者與ppnode的連接關(guān)系if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;cur->_parent = ppnode;}else{_root = cur;cur->_parent = nullptr;}}void reverseR(node* parent){node* cur = parent->_left, *ppnode = parent->_parent;node* curR = cur->_right;//連接parent和curRparent->_left = curR;if (curR)curR->_parent = parent;//連接cur和parentcur->_right = parent;parent->_parent = cur;//連接ppnode和curcur->_parent = ppnode;if (ppnode){if (ppnode->_right == parent)ppnode->_right = cur;elseppnode->_left = cur;}else_root = cur;//跟新bfparent->_bf = cur->_bf = 0;}void reverseRL(node* parent){node* cur = parent->_right, * curL = cur->_left;int bf = curL->_bf;reverseR(cur);reverseL(parent);if (bf == 0)cur->_bf = parent->_bf = curL->_bf = 0;else if (bf == -1){cur->_bf = 1;parent->_bf = curL->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = curL->_bf = 0;}elsethrow "balance factor out_of_range";}void reverseLR(node* parent){node* cur = parent->_left;node* curR = cur->_right;int bf = curR->_bf;reverseL(cur);reverseR(parent);if (bf == 0)cur->_bf = parent->_bf = curR->_bf = 0;else if (bf == -1){parent->_bf = -1;cur->_bf = curR->_bf = 0;}else if (bf == 1){cur->_bf = 1;curR->_bf = parent->_bf = 0;}else throw"balance factor out_of_range";}//需要知道兩個東西，層數(shù)高度以及高度差pair<int, bool> _is_AVL(node* root){pair<int, bool> ret{ 0, true };if (!root) return ret;auto ret_left = _is_AVL(root->_left);auto ret_right = _is_AVL(root->_right);ret.second = ret_left.second && ret_right.second;//判斷平衡因子是否正確int ans_bf = ret_right.first - ret_left.first;if (ans_bf != root->_bf){printf("平衡因子計算錯誤，正確平衡因子: %d, 當(dāng)前平衡因子:%d", ans_bf, root->_bf);ret.second = false;}if (abs(ans_bf) >= 2){cout << "平衡因子超過最大值\n";ret.second = false;}ret.first = max(ret_left.first, ret_right.first) + 1;return ret;}void _inorder(node* root){if (!root) return;_inorder(root->_left);cout << root->_kv.first << ' ' << root->_kv.second << endl;_inorder(root->_right);}};

總結(jié)

AVL樹的出現(xiàn)較為有效的解決了二叉搜索樹在極端情況下效率低下的問題，但還處理的不夠完善，因此，后面又出現(xiàn)了紅黑樹，對于AVL樹在一些地方會更有優(yōu)勢，紅黑樹博主在之后也會講解！關(guān)于AVL樹的知識就到此結(jié)束了，如果大家有什么疑惑或者發(fā)現(xiàn)博主寫的有哪些問題，歡迎在評論區(qū)指出！