目錄

1. AVL樹的核心概念
2. 數據結構與節點定義
3. 插入操作與平衡因子更新
4. 旋轉操作：從理論到代碼
5. 雙旋場景深度剖析
6. 平衡檢測與測試策略
7. 性能分析與工程實踐
8. 總結

---

0.前置知識：BS樹

代碼實現部分對和BS樹相似的部分會省略。

1. AVL樹的核心概念

1.1 平衡二叉搜索樹的必要性

普通二叉搜索樹(BST)在極端情況下會退化為鏈表，時間復雜度惡化至O(N)。AVL樹通過強制平衡約束，將樹高度嚴格控制在O(log N)，確保所有操作的高效性。

1.2 AVL樹的定義

• 平衡條件：任意節點左右子樹高度差絕對值≤1
• 平衡因子(Balance Factor)：
  合法取值范圍：{-1, 0, 1}

1.3 歷史背景

由前蘇聯科學家Adelson-Velsky和Landis于1962年提出，論文《An algorithm for the organization of information》首次描述這一數據結構。

---

2. 數據結構與節點定義

2.1 節點結構（C++實現）

template<class K, class V>
struct AVLTreeNode 
{std::pair<K, V> _kv;AVLTreeNode<K, V>* _left;   // 左子節點AVLTreeNode<K, V>* _right;  // 右子節點AVLTreeNode<K, V>* _parent; // 父節點（關鍵用于回溯更新）int _bf;                    // 平衡因子// 構造函數AVLTreeNode(const std::pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr),_parent(nullptr), _bf(0) {}
};

2.2 樹類框架

template<class K, class V>
class AVLTree 
{typedef AVLTreeNode<K, V> Node;
public:// 接口方法bool Insert(const std::pair<K, V>& kv);Node* Find(const K& key);// ...
private:Node* _root = nullptr;// 旋轉工具方法void RotateL(Node* parent);   // 左單旋void RotateR(Node* parent);   // 右單旋void RotateLR(Node* parent);  // 左右雙旋void RotateRL(Node* parent);  // 右左雙旋
};

---

3. 插入操作與平衡因子更新

3.1 插入流程

3.2 平衡因子更新規則

• 插入右子樹：父節點bf++
• 插入左子樹：父節點bf–
• 更新終止條件：
  1. bf == 0：子樹高度不變，停止更新
  2. bf == ±1：子樹高度變化，繼續向上回溯
  3. bf == ±2：觸發旋轉調整

3.3 關鍵代碼實現

bool Insert(const std::pair<K, V>& kv) {// ... BST插入邏輯//...// 平衡因子更新循環while (parent) {if (cur == parent->_left) parent->_bf--;else parent->_bf++;if (parent->_bf == 0) break;else if (abs(parent->_bf) == 1) {cur = parent;parent = parent->_parent;} else if (abs(parent->_bf) == 2) {// 觸發旋轉if (parent->_bf == 2) {if (cur->_bf == 1) RotateL(parent);else RotateRL(parent);} else {if (cur->_bf == -1) RotateR(parent);else RotateLR(parent);}break;}}return true;
}

---

4. 旋轉操作：從理論到代碼

4.1 右單旋（LL型失衡）

觸發條件：
父節點bf = -2，左子節點bf = -1

代碼實現：

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 (!ppNode) _root = subL;else if (ppNode->_left == parent) ppNode->_left = subL;else ppNode->_right = subL;subL->_parent = ppNode;// 更新平衡因子parent->_bf = subL->_bf = 0;
}

4.2 左單旋（RR型失衡）

觸發條件：
父節點bf = 2，右子節點bf = 1

代碼實現：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;
}

---

5. 雙旋場景深度剖析

5.1 左右雙旋（LR型失衡）

場景分析：
當插入節點導致父節點bf=-2，且左子節點bf=1時，需要先對左子樹左旋，再對父節點右旋。

代碼實現：

void RotateLR(Node* parent) 
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);// 平衡因子修正if (bf == 0) {parent->_bf = subL->_bf = 0;} else if (bf == -1) {parent->_bf = 1;subL->_bf = 0;} else {subL->_bf = -1;parent->_bf = 0;}subLR->_bf = 0;
}

5.2右左雙旋（RL型失衡）

情況與左右雙旋類似。

代碼實現：

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

---

6. 平衡檢測與測試策略

6.1 遞歸驗證算法

bool IsBalance() {return _IsBalanceTree(_root);
}int _Height(Node* root) {if (!root) return 0;return 1 + std::max(_Height(root->_left), _Height(root->_right));
}bool _IsBalanceTree(Node* root) {if (!root) return true;int leftH = _Height(root->_left);int rightH = _Height(root->_right);if (rightH - leftH != root->_bf) {std::cout << "平衡因子異常:" << root->_kv.first;return false;}return abs(leftH - rightH) < 2 && _IsBalanceTree(root->_left)&& _IsBalanceTree(root->_right);
}

---

7. 性能分析與工程實踐

7.1 時間復雜度對比

操作	BST最壞	AVL樹	紅黑樹
插入	O(N)	O(logN)	O(logN)
刪除	O(N)	O(logN)	O(logN)
查找	O(N)	O(logN)	O(logN)

7.2 壓力測試

void StressTest() {AVLTree<int, int> tree;const int N = 1000000;// 隨機插入for (int i = 0; i < N; ++i) {tree.Insert({rand(), i});}assert(tree.IsBalance());// 查詢性能測試auto start = clock();for (int i = 0; i < N; ++i) {tree.Find(rand());}cout << "Query Time:" << clock() - start << "ms";
}

---

8. 總結

AVL樹的優勢：

• 嚴格的平衡保證最優查詢性能
• 適合讀多寫少的場景

---

如有錯誤，懇請指正。