07-AVL树

💡 核心结论

AVL树本质

  • 定义：严格平衡的二叉搜索树，左右子树高度差≤1

  • 性能：所有操作严格O(log n)，查询最快

  • 平衡因子：BF = 左子树高度 - 右子树高度，范围[-1, 0, 1]

  • 核心：通过旋转维持平衡，保证树高度为O(log n)

  • 代价：插入删除时旋转次数多于红黑树

AVL vs 红黑树（重要对比）

特性

AVL树

红黑树

平衡标准

高度差≤1

最长≤2倍最短

平衡度

更严格

较宽松

查询

更快

稍慢

插入删除

较慢（旋转多）

更快

使用场景

查询密集

插入删除密集

实际应用

Windows NT

Linux、STL

四种旋转情况（必须记住）

  1. LL（左左）：右旋

  2. RR（右右）：左旋

  3. LR（左右）：先左旋左子树，再右旋根

  4. RL（右左）：先右旋右子树，再左旋根

判断方法：
- 看插入路径：根→左→左 = LL
- 看平衡因子：根BF=2，左子BF=1 = LL

旋转原理

  • 目的：降低树高度，保持BST性质

  • 次数：插入最多2次旋转，删除最多O(log n)次

  • 关键：旋转不改变中序遍历结果（仍然有序）

🔄 四种旋转详解

LL型（右旋）

      z(BF=2)              y
     /                    / \
    y(BF=1)      =>      x   z
   /
  x

右旋z节点

RR型（左旋）

  z(BF=-2)                 y
   \                      / \
    y(BF=-1)      =>     z   x
     \
      x

左旋z节点

LR型（先左旋再右旋）

    z(BF=2)          z             y
   /                /             / \
  y(BF=-1)   =>    y      =>     x   z
   \              /
    x            x

先左旋y，再右旋z

RL型（先右旋再左旋）

  z(BF=-2)        z               y
   \               \             / \
    y(BF=1)  =>     y      =>   z   x
   /                 \
  x                   x

先右旋y，再左旋z

📊 性能分析

树高度保证

设 N(h) 为高度h的AVL树最少节点数
N(h) = N(h-1) + N(h-2) + 1（类似斐波那契）

结论：n个节点的AVL树
高度h ≈ 1.44 log₂(n)

操作次数统计

插入1000个元素（随机顺序）：
- BST可能退化：高度1000，查找O(n)
- AVL保持平衡：高度~14，查找O(log n)
- 平均旋转次数：~0.5次/插入

🎯 实现要点

更新高度

def update_height(node):
    if not node:
        return 0
    left_height = node.left.height if node.left else 0
    right_height = node.right.height if node.right else 0
    node.height = 1 + max(left_height, right_height)

计算平衡因子

def get_balance(node):
    if not node:
        return 0
    left_height = node.left.height if node.left else 0
    right_height = node.right.height if node.right else 0
    return left_height - right_height

插入后调整

def insert(root, val):
    # 1. BST插入
    if not root:
        return AVLNode(val)
    
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    
    # 2. 更新高度
    root.height = 1 + max(
        root.left.height if root.left else 0,
        root.right.height if root.right else 0
    )
    
    # 3. 获取平衡因子
    balance = get_balance(root)
    
    # 4. 四种情况调整
    # LL
    if balance > 1 and val < root.left.val:
        return right_rotate(root)
    
    # RR
    if balance < -1 and val > root.right.val:
        return left_rotate(root)
    
    # LR
    if balance > 1 and val > root.left.val:
        root.left = left_rotate(root.left)
        return right_rotate(root)
    
    # RL
    if balance < -1 and val < root.right.val:
        root.right = right_rotate(root.right)
        return left_rotate(root)
    
    return root

💡 使用建议

何时使用AVL

  • 查询操作远多于插入删除

  • 需要严格的O(log n)保证

  • 对查询性能要求极高

何时不用AVL

  • 频繁插入删除（用红黑树）

  • 数据量小（直接用数组）

  • 不需要有序（用哈希表）

📚 LeetCode练习

AVL树实现本身较复杂，LeetCode中较少直接考察，但理解AVL树有助于：

  • 理解平衡树概念

  • BST相关题目

  • 系统设计选型

💻 完整代码实现

Python 实现

  1"""
  2AVL树实现
  3严格平衡的二叉搜索树
  4"""
  5
  6class AVLNode:
  7    """AVL树节点"""
  8    
  9    def __init__(self, val):
 10        self.val = val
 11        self.left = None
 12        self.right = None
 13        self.height = 1
 14
 15
 16class AVLTree:
 17    """AVL树实现"""
 18    
 19    def __init__(self):
 20        self.root = None
 21    
 22    def _get_height(self, node):
 23        """获取节点高度"""
 24        return node.height if node else 0
 25    
 26    def _update_height(self, node):
 27        """更新节点高度"""
 28        if node:
 29            node.height = 1 + max(
 30                self._get_height(node.left),
 31                self._get_height(node.right)
 32            )
 33    
 34    def _get_balance(self, node):
 35        """获取平衡因子"""
 36        if not node:
 37            return 0
 38        return self._get_height(node.left) - self._get_height(node.right)
 39    
 40    def _right_rotate(self, z):
 41        """右旋
 42        
 43            z                y
 44           / \              / \
 45          y   T4    =>     x   z
 46         / \                  / \
 47        x   T3               T3  T4
 48        """
 49        y = z.left
 50        T3 = y.right
 51        
 52        # 旋转
 53        y.right = z
 54        z.left = T3
 55        
 56        # 更新高度
 57        self._update_height(z)
 58        self._update_height(y)
 59        
 60        return y
 61    
 62    def _left_rotate(self, z):
 63        """左旋
 64        
 65          z                  y
 66         / \                / \
 67        T4  y      =>      z   x
 68           / \            / \
 69          T3  x          T4  T3
 70        """
 71        y = z.right
 72        T3 = y.left
 73        
 74        # 旋转
 75        y.left = z
 76        z.right = T3
 77        
 78        # 更新高度
 79        self._update_height(z)
 80        self._update_height(y)
 81        
 82        return y
 83    
 84    def insert(self, val):
 85        """插入节点"""
 86        self.root = self._insert(self.root, val)
 87    
 88    def _insert(self, root, val):
 89        """插入辅助函数"""
 90        # 1. BST插入
 91        if not root:
 92            return AVLNode(val)
 93        
 94        if val < root.val:
 95            root.left = self._insert(root.left, val)
 96        elif val > root.val:
 97            root.right = self._insert(root.right, val)
 98        else:
 99            return root  # 重复值不插入
100        
101        # 2. 更新高度
102        self._update_height(root)
103        
104        # 3. 获取平衡因子
105        balance = self._get_balance(root)
106        
107        # 4. 四种情况调整
108        
109        # LL型：右旋
110        if balance > 1 and val < root.left.val:
111            return self._right_rotate(root)
112        
113        # RR型：左旋
114        if balance < -1 and val > root.right.val:
115            return self._left_rotate(root)
116        
117        # LR型：先左旋左子树，再右旋根
118        if balance > 1 and val > root.left.val:
119            root.left = self._left_rotate(root.left)
120            return self._right_rotate(root)
121        
122        # RL型：先右旋右子树，再左旋根
123        if balance < -1 and val < root.right.val:
124            root.right = self._right_rotate(root.right)
125            return self._left_rotate(root)
126        
127        return root
128    
129    def delete(self, val):
130        """删除节点"""
131        self.root = self._delete(self.root, val)
132    
133    def _delete(self, root, val):
134        """删除辅助函数"""
135        # 1. BST删除
136        if not root:
137            return None
138        
139        if val < root.val:
140            root.left = self._delete(root.left, val)
141        elif val > root.val:
142            root.right = self._delete(root.right, val)
143        else:
144            # 找到要删除的节点
145            if not root.left:
146                return root.right
147            if not root.right:
148                return root.left
149            
150            # 两个子节点：用后继替换
151            successor = self._find_min(root.right)
152            root.val = successor.val
153            root.right = self._delete(root.right, successor.val)
154        
155        if not root:
156            return None
157        
158        # 2. 更新高度
159        self._update_height(root)
160        
161        # 3. 重新平衡
162        balance = self._get_balance(root)
163        
164        # LL
165        if balance > 1 and self._get_balance(root.left) >= 0:
166            return self._right_rotate(root)
167        
168        # RR
169        if balance < -1 and self._get_balance(root.right) <= 0:
170            return self._left_rotate(root)
171        
172        # LR
173        if balance > 1 and self._get_balance(root.left) < 0:
174            root.left = self._left_rotate(root.left)
175            return self._right_rotate(root)
176        
177        # RL
178        if balance < -1 and self._get_balance(root.right) > 0:
179            root.right = self._right_rotate(root.right)
180            return self._left_rotate(root)
181        
182        return root
183    
184    def _find_min(self, root):
185        """找最小节点"""
186        while root.left:
187            root = root.left
188        return root
189    
190    def inorder(self):
191        """中序遍历"""
192        result = []
193        self._inorder(self.root, result)
194        return result
195    
196    def _inorder(self, root, result):
197        if root:
198            self._inorder(root.left, result)
199            result.append(root.val)
200            self._inorder(root.right, result)
201    
202    def print_tree(self, node=None, level=0, prefix="Root: "):
203        """打印树结构"""
204        if node is None:
205            node = self.root
206        
207        if node:
208            bf = self._get_balance(node)
209            print(" " * (level * 4) + prefix + f"{node.val}(h:{node.height},bf:{bf})")
210            if node.left or node.right:
211                self.print_tree(node.left, level + 1, "L--- ")
212                self.print_tree(node.right, level + 1, "R--- ")
213
214
215def demo():
216    """演示AVL树操作"""
217    print("=== AVL树演示 ===\n")
218    
219    avl = AVLTree()
220    
221    # 插入节点
222    values = [10, 20, 30, 40, 50, 25]
223    print(f"依次插入: {values}\n")
224    
225    for val in values:
226        avl.insert(val)
227        print(f"插入 {val}:")
228        avl.print_tree()
229        print()
230    
231    # 中序遍历
232    print(f"中序遍历（有序）: {avl.inorder()}\n")
233    
234    # 删除节点
235    print("删除节点 20:")
236    avl.delete(20)
237    avl.print_tree()
238    print()
239    
240    print(f"中序遍历: {avl.inorder()}")
241
242
243if __name__ == '__main__':
244    demo()
245

C++ 实现

  1/**
  2 * AVL树实现
  3 * 严格平衡的二叉搜索树
  4 */
  5
  6#include <iostream>
  7#include <algorithm>
  8
  9struct AVLNode {
 10    int val;
 11    AVLNode* left;
 12    AVLNode* right;
 13    int height;
 14    
 15    AVLNode(int v) : val(v), left(nullptr), right(nullptr), height(1) {}
 16};
 17
 18
 19class AVLTree {
 20private:
 21    AVLNode* root;
 22    
 23    int getHeight(AVLNode* node) {
 24        return node ? node->height : 0;
 25    }
 26    
 27    void updateHeight(AVLNode* node) {
 28        if (node) {
 29            node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
 30        }
 31    }
 32    
 33    int getBalance(AVLNode* node) {
 34        if (!node) return 0;
 35        return getHeight(node->left) - getHeight(node->right);
 36    }
 37    
 38    AVLNode* rightRotate(AVLNode* z) {
 39        AVLNode* y = z->left;
 40        AVLNode* T3 = y->right;
 41        
 42        y->right = z;
 43        z->left = T3;
 44        
 45        updateHeight(z);
 46        updateHeight(y);
 47        
 48        return y;
 49    }
 50    
 51    AVLNode* leftRotate(AVLNode* z) {
 52        AVLNode* y = z->right;
 53        AVLNode* T3 = y->left;
 54        
 55        y->left = z;
 56        z->right = T3;
 57        
 58        updateHeight(z);
 59        updateHeight(y);
 60        
 61        return y;
 62    }
 63    
 64    AVLNode* insertHelper(AVLNode* node, int val) {
 65        // 1. BST插入
 66        if (!node) {
 67            return new AVLNode(val);
 68        }
 69        
 70        if (val < node->val) {
 71            node->left = insertHelper(node->left, val);
 72        } else if (val > node->val) {
 73            node->right = insertHelper(node->right, val);
 74        } else {
 75            return node;  // 重复值
 76        }
 77        
 78        // 2. 更新高度
 79        updateHeight(node);
 80        
 81        // 3. 获取平衡因子
 82        int balance = getBalance(node);
 83        
 84        // 4. 四种情况调整
 85        
 86        // LL
 87        if (balance > 1 && val < node->left->val) {
 88            return rightRotate(node);
 89        }
 90        
 91        // RR
 92        if (balance < -1 && val > node->right->val) {
 93            return leftRotate(node);
 94        }
 95        
 96        // LR
 97        if (balance > 1 && val > node->left->val) {
 98            node->left = leftRotate(node->left);
 99            return rightRotate(node);
100        }
101        
102        // RL
103        if (balance < -1 && val < node->right->val) {
104            node->right = rightRotate(node->right);
105            return leftRotate(node);
106        }
107        
108        return node;
109    }
110    
111    AVLNode* findMin(AVLNode* node) {
112        while (node->left) {
113            node = node->left;
114        }
115        return node;
116    }
117    
118    void printTreeHelper(AVLNode* node, int level, std::string prefix) const {
119        if (node) {
120            int bf = getBalance(node);
121            std::cout << std::string(level * 4, ' ') << prefix 
122                      << node->val << "(h:" << node->height << ",bf:" << bf << ")" 
123                      << std::endl;
124            if (node->left || node->right) {
125                printTreeHelper(node->left, level + 1, "L--- ");
126                printTreeHelper(node->right, level + 1, "R--- ");
127            }
128        }
129    }
130    
131    void deleteTree(AVLNode* node) {
132        if (node) {
133            deleteTree(node->left);
134            deleteTree(node->right);
135            delete node;
136        }
137    }
138
139public:
140    AVLTree() : root(nullptr) {}
141    
142    ~AVLTree() {
143        deleteTree(root);
144    }
145    
146    void insert(int val) {
147        root = insertHelper(root, val);
148    }
149    
150    void printTree() const {
151        printTreeHelper(root, 0, "Root: ");
152    }
153};
154
155
156int main() {
157    std::cout << "=== AVL树演示 ===" << std::endl << std::endl;
158    
159    AVLTree avl;
160    
161    std::vector<int> values = {10, 20, 30, 40, 50, 25};
162    std::cout << "依次插入: ";
163    for (int val : values) {
164        std::cout << val << " ";
165    }
166    std::cout << std::endl << std::endl;
167    
168    for (int val : values) {
169        avl.insert(val);
170        std::cout << "插入 " << val << ":" << std::endl;
171        avl.printTree();
172        std::cout << std::endl;
173    }
174    
175    return 0;
176}