手撕AVL樹

引入：為何要有AVL樹，二次搜索樹有什么不足？

二叉搜索樹有其自身的缺陷，假如往樹中插入的元素有序或者接近有序，二叉搜索樹就會退化成單支樹，時間復雜度會退化成O(N)，因此產生了AVL樹，該結構對二叉樹進行了平衡處理，AVL樹的時間復雜度永遠為O(logn)

下圖為二叉搜索樹退化為單支樹的場景：

不會搜索二叉樹，是看不懂此篇博客的。先去看：搜索二叉樹的模擬實現-CSDN博客

一：AVL樹的概念

如果一棵二叉搜索樹是高度平衡的(樹中任意一顆子樹的左右子樹高度差不超過1)，它就是AVL樹。

且一顆AVL樹具有以下性質：它的左右子樹都是AVL樹

這不純純廢話嗎，樹中任意一顆子樹的左右子樹高度差不超過1，那每顆子樹不都是AVL樹嗎~

下圖為AVL樹：

其滿足樹中的任意一顆子樹的左右子樹高度差不超過1

Q：節點旁邊的數字代表什么？

A：實現AVL樹的方式多種多樣，博主采取的是平衡因子法來實現，圖中節點旁邊的數字即代表該節點的平衡因子大小，平衡因子值 = 該節點的右子樹高度-左子樹高度，其能反映該樹是否為AVL樹，平衡因子>1 或 <-1則代表該樹不為AVL樹，則需要通過一些列的處理，讓其再成為AVL樹

Q：高度差不超過0，不是更平衡嗎

A：某些個數的節點，永遠無法達到0的高度差，如2個節點，4個節點，所以最優就是高度差為1

注意：

①：高度指的是該子樹的最高高度，例如節點5的右子樹高度是3 而不是7->6此路徑的高度2

②：博主的_bf表示的是：某個節點的右子樹高度-左子樹高度的值，某些實現也有可能是左-右，這里以博主自己的右-左來講解

二：AVL樹實現

一個結構只要包含節點，實現的框架都是兩個類：這里是節點類和AVL樹類(list就是list類)

1：節點類的實現

//節點類
template<class K, class V>
struct AVLTreeNode
{//成員變量AVLTreeNode<K, V>* _left;//左指針AVLTreeNode<K, V>* _right;//右指針AVLTreeNode<K, V>* _parent;//父指針int _bf; //平衡因子(balance factor的縮寫) 代表某個節點的右子樹高度-左子樹高度的值pair<K, V> _kv;//每個節點的kv值//構造函數AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr) , _bf(0) , _kv(kv) {}
};

解釋：

①：AVL樹是對KV模型的搜索二叉樹的升級，所以AVL樹照樣是KV結構的

②：博主還設置了父指針，方便后序的操作

2：AVL類的實現

AVL樹的實現很多，一步一步講解吧~ 先看框架

a：框架

template<class K, class V>
class AVLTree
{//方便使用節點類 只需Node即可typedef AVLTreeNode<K, V> Node;
public://......各種函數private://成員變量_root根節點Node* _root = nullptr;
};

b：插入函數(重難點)

注意：代碼注釋中博主有時候會簡稱parent節點為p節點

插入函數的思路：

找到插入的位置將其插入進去，插入后判斷是否還是AVL樹，不是則處理，讓其恢復為AVL樹

插入的情況：

a：插入后還是一顆AVL樹

咋找到插入的地方進行插入即可

b：插入后不再是一顆AVL樹

根據不再是AVL樹的情況，進行對應的處理(旋轉處理)，讓其恢復為AVL樹

由于代碼過長分成以下4步來講解和展示

①：如何找到插入的位置并插入

②：如何判斷插入后是否還是AV樹

③：不是AVL樹的幾種旋轉處理

④：展示的總代碼

①：如何找到插入的位置并插入

//插入函數bool Insert(const pair<K, V>& kv){//空樹情況if (_root == nullptr){_root = new Node(kv);return true;}//開始找位置進行插入Node* parent = nullptr;Node* cur = _root;//從根節點開始找while (cur){//大則往右//小則往左if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else//AVL樹不會存在相同的節點{return false;}}//走到這代表 找到了插入的位置 cur = new Node(kv);//先把該節點準備好//parent節點是找到的插入位置的父節點//所以現在將cur正確的鏈接到parent的正確方向if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完成 則返回真return true;}

解釋：

a：如何找到插入的位置和如何插入和二叉搜索樹是一樣的，根據你插入的值的k值，來和根節點的k值比較，插入的k大，則往右子樹找，反之左子樹，如此循環，直到找到插入的位置，且找的途中遇到和插入的k值一樣的節點，代表插入失敗，因為AVL樹不會存在兩個相同的節?

b：成功找到插入的位置了，該位置一定原先為nullptr，此時再根絕原先為nullptr的節點和其父節點(代碼注釋中博主有時候會簡稱parent節點為p節點)的關系，來對parent節點和插入節點的鏈接

以上代碼只是讓插入的節點成功的插入到了該插入的位置，若是二叉搜索樹到此也就結束了，但是AVL樹插入之后，需要判斷其是否還是一顆AVL樹，是則不再處理，不是則需要處理

②：如何判斷插入后是否還是AV樹

Q：如何判斷插入節點后，該樹是否還是一顆AVL樹呢？

A：根據插入節點后，該插入節點對于其祖先節點的_bf的值帶來的改變來判斷

插入對祖先節點的_bf的影響有以下幾種：

解釋：插入后p節點的_bf變為0，則代表插入前p節點的_bf為-1(只有一個左孩子) 或者 1(圖示)，此情況則代表插入節點只會影響p節點的_bf，因為對于p的parent節點來說，p這顆子樹高度沒變，所以次樹還是一顆AVL樹，無需處理

解釋：插入后p節點的_bf變為1(圖示)或者-1(插入到了節點9的左側)，則代表插入前p節點的_bf為0，此情況則代表插入一個節點后，不僅會影響p還會影響p的parent節點的_bf，此時的p的parent節點的_bf為2或者-2，皆代表不再是一顆AVL樹，需要處理了

總結：

AVL樹插入操作中平衡因子的更新規則

在AVL樹中插入一個新節點時，需要更新相關祖先節點的平衡因子（Balance Factor, BF），并檢查更新之后的平衡因子是否違反平衡條件。邏輯如下：

1. 受影響的節點

插入新節點后，需要從新節點的父節點開始，逐層向上更新，直到根節點或某個祖先節點的子樹高度不再變化。

2. 平衡因子更新原則

設當前正在更新的_bf是節點為p，現在插入一個子節點為?c

如果?c?是?p?的左孩子：p->bf--（左子樹高度增加）。
如果?c?是?p?的右孩子：p->bf++（右子樹高度增加）。

3. 是否繼續向上更新？

更新?p?的平衡因子后，根據其更新后的值來決定是否繼續回溯更新祖先節點：

情況 1：p->bf == 0
- 說明：更新前?p->bf?為?1?或?-1，插入操作使較矮的一側子樹高度增加，p?的左右子樹變得平衡。
- 影響：以p為根節點的這顆樹高度不變，因此不會影響更高層祖先節點的平衡因子。
- 操作：終止更新祖先節點的_bf。
情況 2：p->bf == 1?或?p->bf == -1
- 說明：更新前?p->bf?為?0，插入操作使某一側子樹高度增加。
- 影響：p?的子樹高度變化，會影響其父節點的平衡因子。
- 操作：繼續向上更新祖先節點。
情況 3：p->bf == 2?或?p->bf == -2
- 說明：p?的平衡因子違反AVL樹規則，需要通過處理(旋轉操作)重新平衡子樹。

所以如何判斷插入后是否還是AVL樹的代碼如下：

        //插入完成一定會影響parent節點的bf(只是看cur是p的哪一邊 bf再++或--)//p的bf三種情況：bf 0; 1/-1;2/-2//0：不會影響parent的祖先的bf 直接break//1/-1：樹高度增加 會影響祖先的bf 所以更新完p的bf 再次循環繼續更新上面的bf//2/-2：則需要旋轉while (parent){//根據插入節點是p的哪一邊來更新p的bfif (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//對更新完的p的bf判斷if (parent->_bf == 0){break;}//祖先節點依舊需要更新bf  再次循環else if (parent->_bf == 1 || parent->_bf == -1){//向上更新兩個變量cur = cur->_parent;parent = parent->_parent;}//來到這代表需要旋轉//進入旋轉，咋代表cur和parent在之前的循環中已經找到了_bf為2/-1的節點 則對該節點處理else if (parent->_bf == 2 || parent->_bf == -2){//進行旋轉處理//旋轉處理后 則代表恢復AVL樹 break出去break;}

以上只是完成了判斷插入的后時候是AVL樹，是則不處理，不是則處理，那么不是AVL樹的旋轉處理是什么？

③：不是AVL樹的幾種旋轉處理

旋轉不只是一種，分為四種旋轉，兩種單旋，兩種雙旋

也就是說不是AVL樹的情況分為四種，每種對應一種旋轉來處理~

a：左單旋

新節點插入較高右子樹的右側-->需要 左單旋

如圖：

其中的a b c 是一顆子樹的抽象圖? 一開始abc都是高度為h的子樹

有同學就要問了，直接舉例子不好嗎？為什么要用抽象圖？

因為例子多到數不過來，用單一的例子反而不能代表全部情況，用抽象圖更好

對上圖的左單旋再畫圖講解：

Q：這樣操作下來，還符合搜索二叉樹嗎？b為什么能放在30的右 30又為什么能放在60的左

A：符合。b這顆子樹的值都是比60小(其在60的左)且比30大(因為30的右子樹都比30大)，所以b可以放在30的右，30能放在60的左(30新增的右子樹b，也比60小)

將左旋轉轉換為代碼：

    //步驟： //①：給到p的右指針指向原先p的右孩子的左子樹//②：p的右子樹的的左指針指向p節點void RotateL(Node* parent)//參數的p節點 就是bf為2的節點{Node* subR = parent->_right; //p的右Node* subRL = subR->_left;   //p的右左parent->_right = subRL;//①if (subRL) //避免p的右左為空subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent; //先記錄p的父節點 以防p節點不是根節點parent->_parent = subR; //②if (parent == _root)//查看p是否為根節點{//p是根節點 則subR成為新的根接節點//再置一下subR父指針為空_root = subR;subR->_parent = nullptr;}else//p不是根 則p的父親也需要正確的指向subR(判斷原先的p是pp的左右孩子的哪一個){if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}

解釋： 看起來僅僅是需要執行步驟中的①② ，但實則會有幾個問題：

①：若subRL為空的處理

②：subRL 和 p ?的父指針需要重新指向父節點

③：30節點也就是左旋轉函數的參數parent節點，是根節點和不是根節點的處理

④：修改平衡因子，按照上上圖可知，左旋轉，會讓parent和subR的_bf為0

b：右單旋

新節點插入較高左子樹的左側需要--> 右單旋

右單旋和左單旋大同小異，不再過多贅述了

//①：p的左指針指向p原先的左孩子的右孩子//②：原先的p的左孩子的右指針指向p節點//代碼邏輯和左旋轉同理 不再贅述void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}

c：左右雙旋

AVL在插入節點失去平衡的前提是，是有一顆子樹較高(比另一測高1)

所以我們之前：

a右單旋，就是左子樹為較高子樹，且在該子樹的左側插入

b左單旋，就是右子樹為較高子樹，且在該子樹的右側插入

那有沒有可能插入較高左子樹的右側或?較高右子樹的左側？

當然有，所以前者需要左右雙旋后者需要右左雙旋

左右雙旋示意圖：

解釋：先以30為旋轉節點，對其左單旋，然后再以90為旋轉節點，對其右單旋

只看最后一步和第一步的話。也可以理解為：40作根節點，30 60 做40左右孩子，40的左給30的右，40的右給60的左，一定是符合搜索二叉樹的

新的問題：插入較高左子樹的右測不止一種情況！！

如圖所示，共有三種情況：

解釋：每種情況雖然都可以用左右雙旋恢復成AVL樹，但是恢復之后某些節點的_bf值不一樣，

如下圖所示：

Q：那我們現在知道了不同的情況恢復為AVL樹后的節點的_bf不同，那根據什么去判斷不同的情況呢？

A：先明白插入一個節點后，是先更新整棵樹需要更新_bf的節點，所以我們可以按照插入之后的subRL的_bf，也就是上圖中的40節點的_bf值來判斷，由圖也可知，三種不同的插入情況，也只有subRL的_bf不同了，分別為-1；1；0，-1則對應左右旋轉后的subRL的bf為0，subL的bf為0，parent的bf為1，其他兩種不在贅述

所以左右旋轉的代碼如下：

//步驟 ：//①：對p的左節點進行左單旋//②：再對p節點進行右單旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//由于在b樹插入 在c樹插入 或60本身就是插入的節點入 這三種情況雙旋之后的樹的bf不同//規律：根據插入節點的bf判斷即可if (bf == -1)//代表在b樹插入{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1)//代表在c樹插入{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//else if (bf == 0)//代表subLR就是插入節點{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

d：右左雙旋

和左右雙旋的情況類型，也是分為三種情況，不再贅述

代碼如下：

//步驟 ：//①：對p的右節點進行右單旋//②：再對p節點進行左單旋//代碼邏輯類似 不再贅述void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

?④：插入函數的總代碼

//插入函數bool Insert(const pair<K, V>& kv){//空樹情況if (_root == nullptr){_root = new Node(kv);return true;}//開始找位置進行插入Node* parent = nullptr;Node* cur = _root;//從根節點開始找while (cur){//大則往右//小則往左if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else//AVL樹不會存在相同的節點{return false;}}//走到這代表 找到了插入的位置 cur = new Node(kv);//先把該節點準備好//parent節點在之前是cur的父節點 也就是空節點的父親//所以現在能將cur正確的鏈接到parent的正確方向if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完成一定會影響parent節點的bf(只是看cur是p的哪一邊 bf再++或--)//p的bf三種情況：bf 0 1/-1 2/-2//0：不會影響parent的祖先的bf 直接break//1/-1：樹高度增加 會影響祖先的bf 所以更新完p的bf 再次循環繼續更新上面的bf//2/-2：則需要旋轉while (parent){//第一次更新p的bfif (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//對更新完的p的bf判斷if (parent->_bf == 0){break;}//祖先節點依舊需要更新bf  再次循環else if (parent->_bf == 1 || parent->_bf == -1){cur = cur->_parent;parent = parent->_parent;}//需要旋轉//進入旋轉，咋代表cur和parent 之前已經循環找了 需要旋轉的p節點//(該p節點的bf 2/-2)else if (parent->_bf == 2 || parent->_bf == -2){// 左旋轉// 觸發條件：p->bf為2 cur->_bf == 1if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}// 右旋轉// 觸發條件：parent->_bf == -2 && cur->_bf == -1else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}// 左右旋轉// 觸發條件：parent->_bf == -2 && cur->_bf == 1else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//除此之外右左旋轉else{RotateRL(parent);}break;}else{// 插入之前AVL樹就有問題assert(false);//標記“不應執行到此處”}}//插入完成 則返回真return true;}//左旋轉//新節點插入較高右子樹的右側---簡稱右右//代表從次樹的_root節點看右子樹高1 且插入的節點在右子樹的右側//步驟： //①：給到p的右指針指向原先p的右孩子的左子樹//②：p的右子樹的的左指針指向p節點void RotateL(Node* parent)//參數的p節點 就是bf為2的節點{Node* subR = parent->_right; //p的右Node* subRL = subR->_left;   //p的右左parent->_right = subRL;//①if (subRL) //避免p的右左為空subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent; //先記錄p的父節點 以防p節點不是根節點parent->_parent = subR; //②if (parent == _root)//查看p是否為根節點{//p是根節點 則subR成為新的根接節點//再置一下subR父指針為空_root = subR;subR->_parent = nullptr;}else//p不是根 則p的父親也需要正確的指向subR(判斷原先的p是pp的左右孩子的哪一個){if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}//右旋轉//新節點插入較高左子樹的左側 簡稱左左//代表從次樹的_root節點看左子樹高1 且插入的節點在左子樹的左側//步驟： //①：p的左指針指向p原先的左孩子的右孩子//②：原先的p的左孩子的右指針指向p節點//代碼邏輯和左旋轉同理 不再贅述void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}//左右旋轉->先左單旋再右單旋//新節點插入較高左子樹的右側//步驟 ：//①：對p的左節點進行左單旋//②：再對p節點進行右單旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//由于在b樹插入 在c樹插入 或60本身就是插入的節點入 這三種情況雙旋之后的樹的bf不同//規律：根據插入節點的bf判斷即可if (bf == -1)//代表在b樹插入{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1)//代表在c樹插入{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//else if (bf == 0)//代表subLR就是插入節點{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}//右左旋轉//新節點插入較高右子樹的左側---右左：先右單旋再左單旋//步驟 ：//①：對p的右節點進行右單旋//②：再對p節點進行左單旋//代碼邏輯類似 不再贅述void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

c：中序函數

和二叉搜索樹類似，不再贅述

void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << "[" << root->_bf << "]" << endl;_InOrder(root->_right);}//中序遍歷void InOrder(){_InOrder(_root);}

d：查找函數

和二叉搜索樹類似，不再贅述

//查找函數Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}

e：IsBalence()函數(判斷平衡函數)

我們寫了以上這么多的函數實現，能證明其是一顆AVL樹嗎？？？

Q：我們中序遍歷是升序，不就是AVL樹嗎

A：?中序遍歷是升序，只能說明是二叉搜索樹！

Q：打印一下每個節點的_bf值，沒有一個_bf值大于1或者小于-1，不就行了？

A：萬一bf本身就是錯的呢，你怎么保證你的bf一定是對的？

Q：層序遍歷打印，然后自己畫二叉樹？

A：你怎么知道打印出來的一串值，從哪里分割？怎么畫二叉樹？

正確答案：寫一個IsBalence()函數(判斷平衡函數)！來解決

該函數內部，會遞歸調用Height()函數去算每顆子樹的高度差，順便將此高度差和我們自己的_bf值對比一下，驗證一下我們的準確性！

代碼：

    int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}//高度函數int Height(){return _Height(_root);}bool _IsBalance(Node* root) {if (root == nullptr) {return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);// 檢查當前節點是否平衡（左右子樹高度差不超過1）if (abs(rightHeight - leftHeight) >= 2) {cout << root->_kv.first << " 不平衡" << endl;return false;}// 檢查平衡因子是否正確（bf應等于右子樹高度減左子樹高度）if (rightHeight - leftHeight != root->_bf) {cout << root->_kv.first << " 平衡因子異常" << endl;return false;}// 遞歸檢查左右子樹return _IsBalance(root->_left) && _IsBalance(root->_right);}//是否平衡判斷函數 bool IsBalance() //這是我們在類外調用的函數{int height = 0;return _IsBalance(_root, height);}

解釋：該函數雖然達到了我們的要求，但是其并不是一個優秀的函數，其進行了大量的重復運算

對于一棵樹，_IsBalance 會從根節點開始，逐層遞歸計算高度，導致子節點的高度被重復計算多次。例如，根節點的左右子樹高度會被計算一次，而它們的子節點又會在各自的遞歸中被重復計算。

更優秀的判斷平衡函數：

//更優秀的平衡函數bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight)|| !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子異常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}//是否平衡判斷函數bool IsBalance(){int height = 0;return _IsBalance(_root, height);}

?解釋：該函數沒有重復運算

抽象圖如下：?

由上上圖可知：

在遞歸過程中，通過 int& height 參數傳遞子樹高度，避免重復計算。

計算高度和平衡性檢查在一次后序遍歷（左→右→根）中完成，時間復雜度降至 O(n)。

f：節點個數函數

過于簡單不再贅述

//計算樹的節點個數size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}

沒有實現刪除，因為刪除校招不考考得一般是手撕旋轉

三：AVL樹代碼

#pragma once
#include<assert.h>
#include<vector>//節點類
template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorpair<K, V> _kv;AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr) //指向父節點的之怎, _bf(0) //平衡因子, _kv(kv) //pair類型的對象  存儲k值和v值{}
};
//AVL類
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://插入函數bool Insert(const pair<K, V>& kv){//空樹情況if (_root == nullptr){_root = new Node(kv);return true;}//開始找位置進行插入Node* parent = nullptr;Node* cur = _root;//從根節點開始找while (cur){//大則往右//小則往左if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else//AVL樹不會存在相同的節點{return false;}}//走到這代表 找到了插入的位置 cur = new Node(kv);//先把該節點準備好//parent節點在之前是cur的父節點 也就是空節點的父親//所以現在能將cur正確的鏈接到parent的正確方向if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完成一定會影響parent節點的bf(只是看cur是p的哪一邊 bf再++或--)//p的bf三種情況：bf 0 1/-1 2/-2//0：不會影響parent的祖先的bf 直接break//1/-1：樹高度增加 會影響祖先的bf 所以更新完p的bf 再次循環繼續更新上面的bf//2/-2：則需要旋轉while (parent){//第一次更新p的bfif (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//對更新完的p的bf判斷if (parent->_bf == 0){break;}//祖先節點依舊需要更新bf  再次循環else if (parent->_bf == 1 || parent->_bf == -1){cur = cur->_parent;parent = parent->_parent;}//需要旋轉//進入旋轉，咋代表cur和parent 之前已經循環找了 需要旋轉的p節點//(該p節點的bf 2/-2)else if (parent->_bf == 2 || parent->_bf == -2){// 左旋轉// 觸發條件：p->bf為2 cur->_bf == 1if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}// 右旋轉// 觸發條件：parent->_bf == -2 && cur->_bf == -1else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}// 左右旋轉// 觸發條件：parent->_bf == -2 && cur->_bf == 1else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//除此之外右左旋轉else{RotateRL(parent);}break;}else{// 插入之前AVL樹就有問題assert(false);//標記“不應執行到此處”}}//插入完成 則返回真return true;}//左旋轉//新節點插入較高右子樹的右側---簡稱右右//代表從次樹的_root節點看右子樹高1 且插入的節點在右子樹的右側//步驟： //①：給到p的右指針指向原先p的右孩子的左子樹//②：p的右子樹的的左指針指向p節點void RotateL(Node* parent)//參數的p節點 就是bf為2的節點{Node* subR = parent->_right; //p的右Node* subRL = subR->_left;   //p的右左parent->_right = subRL;//①if (subRL) //避免p的右左為空subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent; //先記錄p的父節點 以防p節點不是根節點parent->_parent = subR; //②if (parent == _root)//查看p是否為根節點{//p是根節點 則subR成為新的根接節點//再置一下subR父指針為空_root = subR;subR->_parent = nullptr;}else//p不是根 則p的父親也需要正確的指向subR(判斷原先的p是pp的左右孩子的哪一個){if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}//右旋轉//新節點插入較高左子樹的左側 簡稱左左//代表從次樹的_root節點看左子樹高1 且插入的節點在左子樹的左側//步驟： //①：p的左指針指向p原先的左孩子的右孩子//②：原先的p的左孩子的右指針指向p節點//代碼邏輯和左旋轉同理 不再贅述void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}//左右旋轉->先左單旋再右單旋//新節點插入較高左子樹的右側//步驟 ：//①：對p的左節點進行左單旋//②：再對p節點進行右單旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//由于在b樹插入 在c樹插入 或60本身就是插入的節點入 這三種情況雙旋之后的樹的bf不同//規律：根據插入節點的bf判斷即可if (bf == -1)//代表在b樹插入{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1)//代表在c樹插入{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//else if (bf == 0)//代表subLR就是插入節點{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}//右左旋轉//新節點插入較高右子樹的左側---右左：先右單旋再左單旋//步驟 ：//①：對p的右節點進行右單旋//②：再對p節點進行左單旋//代碼邏輯類似 不再贅述void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << "[" << root->_bf << "]" << endl;_InOrder(root->_right);}//中序遍歷void InOrder(){_InOrder(_root);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}//高度函數int Height(){return _Height(_root);}//bool _IsBalance(Node* root) {//	if (root == nullptr) {//		return true;//	}//	int leftHeight = Height(root->_left);//	int rightHeight = Height(root->_right);//	// 檢查當前節點是否平衡（左右子樹高度差不超過1）//	if (abs(rightHeight - leftHeight) >= 2) {//		cout << root->_kv.first << " 不平衡" << endl;//		return false;//	}//	// 檢查平衡因子是否正確（bf應等于右子樹高度減左子樹高度）//	if (rightHeight - leftHeight != root->_bf) {//		cout << root->_kv.first << " 平衡因子異常" << endl;//		return false;//	}//	// 遞歸檢查左右子樹//	return _IsBalance(root->_left) && _IsBalance(root->_right);//}//更優秀的平衡函數bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight)|| !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子異常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}//是否平衡判斷函數bool IsBalance(){int height = 0;return _IsBalance(_root, height);}//計算樹的節點個數size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}//查找函數Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}
private://成員變量_root根節點Node* _root = nullptr;
};

四：AVL樹代碼的測試

①：平衡函數的測試

void TestAVLTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t;for (auto e : a){cout << e << "->" << t.IsBalance() << endl;}t.InOrder();cout << t.IsBalance() << endl;
}

運行結果：

完美~?

②：代碼總體的測試一百萬個數據

void TestAVLTree2()
{//將一百萬個數放進v數組中const int N = 1000000;vector<int> v;v.reserve(N);//先預開辟一下srand(time(0));//for (size_t i = 0; i < N; i++){v.push_back(rand() + i);// 生成隨機數并插入到 v 末尾； rand() 的范圍有限（通常 0~32767），而 + i 可以擴展范圍，降低重復概率。//cout << v.back() << endl;// 可取消注釋以打印每個數}size_t begin2 = clock();//記錄起始時間 begin2 AVLTree<int, int> t;for (auto e : v){//每個元素 e 作為 (key, value) 插入 AVLTreet.Insert(make_pair(e, e));//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();//記錄結束時間 end2//插入 100 萬個元素的總 CPU 時間（時鐘周期）。cout << "Insert:" << end2 - begin2 << endl;cout << "是否平衡:" << t.IsBalance() << endl;// 檢查是否平衡cout << "Height:" << t.Height() << endl; // 輸出樹的高度cout << "Size:" << t.Size() << endl;// 輸出樹的節點數size_t begin1 = clock();//記錄起始時間begin1// 在AVL樹中查找所有已存在的值for (auto e : v){t.Find(e);}// 查找隨機值（可能不存在）for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();//記錄結束時間end1//end1 - begin1: 執行 200 萬次查找（100 萬成功 + 100 萬隨機）的 CPU 時間。cout << "Find:" << end1 - begin1 << endl;
}

運行結果：

Debug版本：