# C++ AVL樹深度解析：平衡之道與旋轉實現(xiàn)
AVL樹是最早發(fā)明的自平衡二叉搜索樹，以其發(fā)明者Adelson-Velsky和Landis的名字命名。它通過維護平衡因子來確保樹的高度始終保持在O(log n)范圍內，為各種操作提供了穩(wěn)定的性能保證。
## AVL樹的基本概念
### 平衡因子定義
AVL樹要求每個節(jié)點的左右子樹高度差（平衡因子）的絕對值不超過1。平衡因子的計算公式為：
```
平衡因子 = 左子樹高度 - 右子樹高度
```
當平衡因子的絕對值大于1時，需要通過旋轉操作來恢復平衡。
### AVL樹的性質
1. 是一棵二叉搜索樹
2. 每個節(jié)點的平衡因子絕對值不超過1
3. 每個子樹也都是AVL樹
4. 搜索、插入、刪除操作的時間復雜度均為O(log n)
## AVL樹節(jié)點設計
```cpp
template<typename T>
struct AVLTreeNode {
? ? T data;
? ? AVLTreeNode* left;
? ? AVLTreeNode* right;
? ? AVLTreeNode* parent;
? ? int height;
? ? AVLTreeNode(const T& val)
? ? ? ? : data(val), left(nullptr), right(nullptr),
? ? ? ? ? parent(nullptr), height(1) {}
? ? // 更新節(jié)點高度
? ? void updateHeight() {
? ? ? ? int left_height = left ? left->height : 0;
? ? ? ? int right_height = right ? right->height : 0;
? ? ? ? height = std::max(left_height, right_height) + 1;
? ? }
? ? // 獲取平衡因子
? ? int getBalanceFactor() const {
? ? ? ? int left_height = left ? left->height : 0;
? ? ? ? int right_height = right ? right->height : 0;
? ? ? ? return left_height - right_height;
? ? }
};
```
## AVL樹核心框架
```cpp
template<typename K, typename V, typename KeyOfValue>
class AVLTree {
public:
? ? using Node = AVLTreeNode<V>;
? ? AVLTree() : root(nullptr), size_(0) {}
? ? ~AVLTree() { clear(); }
? ? // 基本操作接口
? ? bool insert(const V& value);
? ? bool erase(const K& key);
? ? Node* find(const K& key) const;
? ? void clear();
? ? // 工具函數(shù)
? ? size_t size() const { return size_; }
? ? bool empty() const { return size_ == 0; }
? ? int height() const { return root ? root->height : 0; }
? ? // 遍歷接口
? ? template<typename Func>
? ? void inorder(Func func) const { inorder(root, func); }
private:
? ? Node* root;
? ? size_t size_;
? ? KeyOfValue keyOfValue;
? ? // 旋轉操作
? ? Node* leftRotate(Node* y);
? ? Node* rightRotate(Node* x);
? ? // 平衡維護
? ? Node* balance(Node* node);
? ? // 輔助函數(shù)
? ? Node* insert(Node* node, const V& value, bool& inserted);
? ? Node* erase(Node* node, const K& key, bool& deleted);
? ? Node* find(Node* node, const K& key) const;
? ? Node* minimum(Node* node) const;
? ? void destroy(Node* node)<"8N.2597.HK">;
? ? template<typename Func>
? ? void inorder(Node* node, Func func) const;
};
```
## 旋轉操作詳解
### 左旋操作
左旋用于處理右子樹過高的情況：
```cpp
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::leftRotate(Node* y) {
? ? if (!y || !y->right) return y;
? ? Node* x = y->right;
? ? Node* T2 = x->left;
? ? // 執(zhí)行旋轉
? ? x->left = y;
? ? y->right = T2;
? ? // 更新父指針
? ? if (T2) {
? ? ? ? T2->parent = y;
? ? }
? ? x->parent = y->parent;
? ? y->parent = x;
? ? // 更新高度
? ? y->updateHeight();
? ? x->updateHeight();
? ? return x;
}
```
### 右旋操作
右旋用于處理左子樹過高的情況：
```cpp
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::rightRotate(Node* x) {
? ? if (!x || !x->left) return x;
? ? Node* y = x->left;
? ? Node* T2 = y->right;
? ? // 執(zhí)行旋轉
? ? y->right = x;
? ? x->left = T2;
? ? // 更新父指針
? ? if (T2) {
? ? ? ? T2->parent = x;
? ? }
? ? y->parent = x->parent;
? ? x->parent = y;
? ? // 更新高度
? ? x->updateHeight();
? ? y->updateHeight();
? ? return y;
}
```
## 四種不平衡情況處理
### LL情況（左左情況）
當節(jié)點的左子樹的左子樹過高時，需要單次右旋：
```cpp
// 在balance函數(shù)中處理LL情況
if (balance_factor > 1 && node->left->getBalanceFactor() >= 0) {
? ? return rightRotate(node);
}
```
### RR情況（右右情況）
當節(jié)點的右子樹的右子樹過高時，需要單次左旋：
```cpp
// 在balance函數(shù)中處理RR情況
if (balance_factor < -1 && node->right->getBalanceFactor() <= 0) {
? ? return leftRotate(node);
}
```
### LR情況（左右情況）
當節(jié)點的左子樹的右子樹過高時，需要先左旋再右旋：
```cpp
// 在balance函數(shù)中處理LR情況
if (balance_factor > 1 && node->left->getBalanceFactor() < 0) {
? ? node->left = leftRotate(node->left);
? ? return rightRotate(node);
}
```
### RL情況（右左情況）
當節(jié)點的右子樹的左子樹過高時，需要先右旋再左旋：
```cpp
// 在balance函數(shù)中處理RL情況
if (balance_factor < -1 && node->right->getBalanceFactor() > 0) {
? ? node->right <"2T.2597.HK">= rightRotate(node->right);
? ? return leftRotate(node);
}
```
## 完整的平衡函數(shù)
```cpp
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::balance(Node* node) {
? ? if (!node) return nullptr;
? ? node->updateHeight();
? ? int balance_factor = node->getBalanceFactor();
? ? // LL情況
? ? if (balance_factor > 1 && node->left->getBalanceFactor() >= 0) {
? ? ? ? return rightRotate(node);
? ? }
? ? // RR情況
? ? if (balance_factor < -1 && node->right->getBalanceFactor() <= 0) {
? ? ? ? return leftRotate(node);
? ? }
? ? // LR情況
? ? if (balance_factor > 1 && node->left->getBalanceFactor() < 0) {
? ? ? ? node->left = leftRotate(node->left);
? ? ? ? return rightRotate(node);
? ? }
? ? // RL情況
? ? if (balance_factor < -1 && node->right->getBalanceFactor() > 0) {
? ? ? ? node->right = rightRotate(node->right);
? ? ? ? return leftRotate(node);
? ? }
? ? return node;
}
```
## 插入操作實現(xiàn)
```cpp
template<typename K, typename V, typename KeyOfValue>
bool AVLTree<K, V, KeyOfValue>::insert(const V& value) {
? ? bool inserted = false;
? ? root = insert(root, value, inserted);
? ? if (inserted) size_++;
? ? return inserted;
}
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::insert(Node* node, const V& value, bool& inserted) {
? ? if (!node) {
? ? ? ? inserted = true;
? ? ? ? return new Node(value);
? ? }
? ? K key_val = keyOfValue(value);
? ? K node_key = keyOfValue(node->data);
? ? if (key_val < node_key) {
? ? ? ? node->left = insert(node->left, value, inserted);
? ? ? ? if (node->left) node->left->parent = node;
? ? } else if (key_val > node_key) {
? ? ? ? node->right = insert(node->right, value, inserted);
? ? ? ? if (node->right) node->right->parent = node;
? ? } else {
? ? ? ? // 鍵值已存在，不插入
? ? ? ? inserted = false;
? ? ? ? return node;
? ? }
? ? // 更新高度并平衡樹
? ? return balance(node);
}
```
## 刪除操作實現(xiàn)
```cpp
template<typename K, typename V, typename KeyOfValue>
bool AVLTree<K, V, KeyOfValue>::erase(const K& key) {
? ? bool deleted = false;
? ? root = erase(root, key, deleted);
? ? if (deleted) size_--;
? ? return deleted;
}
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::erase(Node* node, const K& key, bool& deleted) {
? ? if (!node) {
? ? ? ? deleted = false;
? ? ? ? return nullptr;
? ? }
? ? K node_key = keyOfValue(node->data);
? ? if (key<"5A.2597.HK"> < node_key) {
? ? ? ? node->left = erase(node->left, key, deleted);
? ? ? ? if (node->left) node->left->parent = node;
? ? } else if (key > node_key) {
? ? ? ? node->right = erase(node->right, key, deleted);
? ? ? ? if (node->right) node->right->parent = node;
? ? } else {
? ? ? ? // 找到要刪除的節(jié)點
? ? ? ? deleted = true;
? ? ? ? if (!node->left || !node->right) {
? ? ? ? ? ? // 有一個子節(jié)點或沒有子節(jié)點
? ? ? ? ? ? Node* temp = node->left ? node->left : node->right;
? ? ? ? ? ? if (!temp) {
? ? ? ? ? ? ? ? // 沒有子節(jié)點
? ? ? ? ? ? ? ? delete node;
? ? ? ? ? ? ? ? return nullptr;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? // 有一個子節(jié)點
? ? ? ? ? ? ? ? temp->parent = node->parent;
? ? ? ? ? ? ? ? delete node;
? ? ? ? ? ? ? ? return temp;
? ? ? ? ? ? }
? ? ? ? } else {
? ? ? ? ? ? // 有兩個子節(jié)點，找到中序后繼
? ? ? ? ? ? Node* temp = minimum(node->right);
? ? ? ? ? ? node->data = temp->data;
? ? ? ? ? ? node->right = erase(node->right, keyOfValue(temp->data), deleted);
? ? ? ? }
? ? }
? ? return balance(node);
}
```
## 查找和遍歷操作
```cpp
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::find(const K& key) const {
? ? return find(root, key);
}
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::find(Node* node, const K& key) const {
? ? while (node) {
? ? ? ? K node_key = keyOfValue(node->data);
? ? ? ? if (key < node_key) {
? ? ? ? ? ? node = node->left;
? ? ? ? } else if (key > node_key) {
? ? ? ? ? ? node = node->right;
? ? ? ? } else {
? ? ? ? ? ? return node;
? ? ? ? }
? ? }
? ? return nullptr;
}
template<typename K, typename V, typename KeyOfValue>
template<typename Func>
void AVLTree<K, V, KeyOfValue>::inorder(Node* node, Func func) const {
? ? if (!node) return;
? ? inorder(node->left, func);
? ? func(node->data);
? ? inorder(node->right, func);
}
```
## 實用工具函數(shù)
```cpp
template<typename K, typename V, typename KeyOfValue>
typename AVLTree<K, V, KeyOfValue>::Node*
AVLTree<K, V, KeyOfValue>::minimum(Node* node) const {
? ? if (!node) return nullptr;
? ? while (node->left) {
? ? ? ? node = node->left;
? ? }
? ? return node;
}
template<typename K, typename V, typename KeyOfValue>
void AVLTree<K, V, KeyOfValue>::clear() {
? ? destroy(root);
? ? root = nullptr;
? ? size_ = 0;
}
template<typename K, typename V, typename KeyOfValue>
void AVLTree<K, V, KeyOfValue>::destroy(Node* node) {
? ? if (!node) return;
? ? destroy(node->left);
? ? destroy(node->right);
? ? delete node;
}
```
## 使用示例
### 實現(xiàn)學生成績管理系統(tǒng)
```cpp
#include <iostream>
#include <string>
struct Student {
? ? int id;
? ? std::string name;
? ? double score;
? ? Student(int i, const std::string& n, double s)
? ? ? ? : id(i), name(n), score(s) {}
? ? bool operator<(const Student& other) const {
? ? ? ? return id <"9E.2597.HK">< other.id;
? ? }
};
struct StudentKey {
? ? int operator()(const Student& s) const {
? ? ? ? return s.id;
? ? }
};
void student_management_example() {
? ? AVLTree<int, Student, StudentKey> student_db;
? ? // 插入學生記錄
? ? student_db.insert(Student(1001, "Alice", 85.5));
? ? student_db.insert(Student(1002, "Bob", 92.0));
? ? student_db.insert(Student(1003, "Charlie", 78.5));
? ? student_db.insert(Student(1004, "Diana", 88.0));
? ? // 查找學生
? ? auto student = student_db.find(1002);
? ? if (student) {
? ? ? ? std::cout << "Found student: " << student->name
? ? ? ? ? ? ? ? ? << ", Score: " << student->score << std::endl;
? ? }
? ? // 中序遍歷輸出所有學生（按學號排序）
? ? std::cout << "All students (sorted by ID):" << std::endl;
? ? student_db.inorder([](const Student& s) {
? ? ? ? std::cout << "ID: " << s.id << ", Name: " << s.name
? ? ? ? ? ? ? ? ? << ", Score: " << s.score << std::endl;
? ? });
? ? std::cout << "Tree height: " << student_db.height() << std::endl;
? ? std::cout << "Total students: " << student_db.size() << std::endl;
}
```
## 性能分析與驗證
### 平衡性檢查
```cpp
template<typename K, typename V, typename KeyOfValue>
class AVLTreeValidator {
public:
? ? static bool isBalanced(const AVLTree<K, V, KeyOfValue>& tree) {
? ? ? ? return checkBalance(tree.getRoot());
? ? }
? ? static bool isBST(const AVLTree<K, V, KeyOfValue>& tree) {
? ? ? ? return checkBST(tree.getRoot(), nullptr, nullptr);
? ? }
private:
? ? static bool checkBalance(typename AVLTree<K, V, KeyOfValue>::Node* node) {
? ? ? ? if (!node) return true;
? ? ? ? int balance_factor = node->getBalanceFactor();
? ? ? ? if (balance_factor < -1 || balance_factor > 1) {
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? return checkBalance(node->left) && checkBalance(node->right);
? ? }
? ? static bool checkBST(typename AVLTree<K, V, KeyOfValue>::Node* node,
? ? ? ? ? ? ? ? ? ? ? ? const K* min_val, const K* max_val) {
? ? ? ? if (!node) return true;
? ? ? ? K current_key = KeyOfValue()(node->data);
? ? ? ? if (min_val && current_key <= *min_val) return false;
? ? ? ? if (max_val && current_key >= *max_val) return false;
? ? ? ? return checkBST(node->left, min_val, ¤t_key) &&
? ? ? ? ? ? ? checkBST(node->right, ¤t_key, max_val);
? ? }
};
```
## 與紅黑樹的比較
### 適用場景分析
```cpp
// AVL樹的優(yōu)勢：
// - 查找操作性能更優(yōu)（更嚴格的平衡）
// - 適用于查找密集型的應用
// - 高度始終保持在最小范圍內
// AVL樹的劣勢：
// - 插入和刪除操作可能更慢（需要更多旋轉）
// - 實現(xiàn)相對復雜
// - 內存開銷稍大（需要存儲高度信息）
// 紅黑樹的優(yōu)勢：
// - 插入和刪除操作更快
// - 實現(xiàn)相對簡單
// - 適用于頻繁修改的場景
// 選擇建議：
// - 如果查找操作遠多于修改操作，選擇AVL樹
// - 如果插入刪除操作頻繁，選擇紅黑樹
// - 對于內存敏感的場景，考慮紅黑樹
```
## 總結
AVL樹通過精妙的旋轉操作維護嚴格的平衡條件，為需要高效查找操作的場景提供了理想的數(shù)據(jù)結構解決方案。其四種旋轉情況（LL、RR、LR、RL）涵蓋了所有可能的不平衡狀態(tài)，確保了樹的平衡性。
理解AVL樹的實現(xiàn)不僅有助于掌握自平衡樹的基本原理，還能為學習更復雜的數(shù)據(jù)結構打下堅實基礎。在實際應用中，應根據(jù)具體的操作頻率和性能要求，在AVL樹和紅黑樹之間做出合適的選擇。
