二叉搜索樹有其自身的缺陷，假如往樹中插入的元素有序或者接近有序，二叉搜索樹就會退化成單支樹，時間復雜度會退化成 O(N)，因此 map、set 等關聯式容器的底層結構是對二叉樹進行了平衡處理，即采用平衡樹來實現

1.AVL樹的概念

我們已經從多種樹型結構走到現在，每一次變化都是為了提高搜索的效率，即時間復雜度

二叉搜索樹雖可以縮短查找的效率，但如果數據有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下，因此發明了 AVL 樹

那么什么是AVL樹呢？

當向二叉搜索樹中插入新結點后，如果能保證每個結點的左右子樹高度之差的絕對值不超過 1 (需要對樹中的結點進行調整)，即可降低樹的高度，從而減少平均搜索長度

一棵 AVL 樹或者是空樹，應該是具有以下性質的二叉搜索樹：

• 它的左右子樹都是 AVL 樹
• 左右子樹高度之差(簡稱平衡因子)的絕對值不超過 1(-1/0/1)

二叉搜索樹在理想情況下時間復雜度與二叉平衡搜索樹相同，均為$O(lo{g}_{2}n)$，但在極端情況下二叉平衡搜索樹優于二叉搜索樹，因為二叉平衡搜索樹會自己調整平衡（后面會詳細解釋）

為什么是嚴格的絕對值為 1，不是 0 或者更大的數字？

若要求高度差為 0，即嚴格平衡，樹的結構會過于 rigid（僵化）。每次插入或刪除節點都可能需要大量調整操作，導致性能下降。允許高度差為 1，在保持較好平衡性的同時，減少了不必要的調整
若允許高度差為 2，樹的平衡性會明顯下降，可能出現一側子樹比另一側高很多的情況，導致查找等操作的時間復雜度增加
所以平衡因子為 1 是最合適的

2.AVL樹的結構

template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){ }
};

• pair<K, V> _kv：用于存儲鍵值對，pair 是 C++ 標準庫中的一個模板類，可將兩個不同類型的值組合在一起
• AVLTreeNode<K, V>* _left：指向左子節點的指針
• AVLTreeNode<K, V>* _right：指向右子節點的指針
• AVLTreeNode<K, V>* _parent：指向父節點的指針，這在調整樹的平衡時很有用
• int _bf：平衡因子（Balance Factor），用來記錄該節點左右子樹的高度差。平衡因子為 0 時表示左右子樹高度相等；為 1 時表示右子樹比左子樹高 1；為 -1 時表示左子樹比右子樹高 1

3.AVL樹的插入

	typedef AVLTreeNode<K, V> Node;
public: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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//鏈接插入節點與AVL樹cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//調整平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//旋轉調整（...）}else{assert(false);}}return true;}

AVL 樹的插入和二叉搜索樹是很像的，先根據左大右小的原則，尋找插入節點的位置，然后判斷父母節點與插入節點的關系，連接新節點，唯一不同的地方是平衡因子調節的部分，高度差是由右子樹減去左子樹得出的，可以總結出以下方法：

🚩 (1)新增在左，parent平衡因子減減

🚩 (2)新增在右，parent平衡因子加加

🚩 (3)更新后parent平衡因子 == 0

說明 parent 所在的子樹的高度不變，不會影響祖先，不用再繼續沿著到 root 的路徑往上更新，然后循環結束

🚩 (4)更新后parent平衡因子 == 1 or -1

說明 parent 所在的子樹的高度變化，會影響祖先，需要繼續沿著到 root 的路徑往上更新，循環繼續

🚩 (5)更新后parent平衡因子 == 2 or -2

說明 parent 所在的子樹的高度變化且不平衡，需要對parent所在子樹進行旋轉，讓他平衡，然后循環結束

🔥值得注意的是： 如果平衡因子出現比 2 還大，比 -2 還小的數，說明之前的插入就已經出問題了

4.AVL樹的旋轉

4.1 左單旋

void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;
}

以下將根據一個圖例來解釋如何進行的左單旋：

左單旋顧名思義就是右子樹太長，需要向左旋轉形成平衡，平衡因子為 2 的節點定為 parent，其右節點為 cur，cur 的左節點為 curleft

1. 調整 parent 的右子節點： 把 parent 的右子節點設置成 curleft，若 curleft 不為空，就把 curleft 的父節點設置成 parent
2. 調整 cur 的左子節點： 把 cur 的左子節點設置成 parent，ppnode 為 parent 的父節點，把 parent 的父節點設置成 cur
3. 調整根節點或者 ppnode 的子節點： 若 parent 是根節點，那就把 cur 設為新的根節點，并且將 cur 的父節點設為 nullptr。若 parent 不是根節點，就依據 parent 是 ppnode 的左子節點還是右子節點，來更新 ppnode 的相應子節點為 cur，同時把 cur 的父節點設為 ppnode

4.2 右單旋

void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;
}

和左單旋類似，這里就不詳細解釋了

4.3 右左雙旋

void RotateRL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

右左雙旋適用于新節點插入較高右子樹的左側的情況

30 為 parent 節點，90 為 cur 節點，60 為 curleft 節點

先以 90 進行右單旋，再以 30 進行左單旋

雙旋的重點是平衡節點的調整，根據多個例子可以知道，主要是看 curleft 節點的平衡因子

如果原來 curleft 平衡因子為 0 ，即 curleft 為新增節點導致的雙旋，那么 curleft、cur、parent 平衡因子都為 0

如果原來 curleft 平衡因子為 1 ，即在 curleft 右邊新增，那么 cur 和 curleft 平衡因子都為 0，parent 的平衡因子為 1

如果原來 curleft 平衡因子為 -1 ，即在 curleft 左邊新增，那么 parent 和 curleft 平衡因子都為 0，cur 的平衡因子為 1

4.4 左右雙旋

void RotateLR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}
}

和右左雙旋類似，這里就不詳細解釋了

5.AVL樹的刪除

在實際開發中，雖然 AVL 樹是一種自平衡的二叉搜索樹，但其刪除操作通常不被優先實現

AVL 樹的核心特性是通過旋轉操作（左旋、右旋、左右旋、右左旋）來保證樹的高度平衡。在插入操作中，僅需從插入節點向上回溯至根節點，檢查并調整路徑上節點的平衡因子，最多進行兩次旋轉操作就能恢復樹的平衡。然而，刪除操作后，平衡的破壞可能會沿著從刪除節點到根節點的路徑向上傳播，導致需要多次旋轉操作來恢復平衡。這使得刪除操作的實現邏輯變得異常復雜，需要仔細處理各種可能的情況

而且實現插入刪除一般會使用 紅黑樹、B樹 等更優的數據結構

6.AVL樹的高度

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;
}

比較左子樹和右子樹的高度，取較大值并加 1（加上當前根節點），得到當前子樹的高度

7.AVL樹的平衡判斷

bool IsBalance(Node* root)
{if (root == nullptr)return true;int leftHight = Height(root->_left);int rightHight = Height(root->_right);if (rightHight - leftHight != root->_bf){cout << "平衡因子異常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(rightHight - leftHight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);
}

每遍歷一個節點就對其左右子樹的高度進行計算，然后判斷是否絕對值小于 2

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

---

希望讀者們多多三連支持

小編會繼續更新

你們的鼓勵就是我前進的動力！