AVL树

AVL 树是二叉搜索树（BST）的一种特殊类型，也被称为自平衡二叉搜索树。它在 BST 的基础上增加了平衡条件，确保树的高度始终保持在 O(logn) ，从而保证插入、删除、查找操作的时间复杂度稳定为 O(logn) 。 AVL 树 vs. 普通 BST 特性普通 BST AVL 树（BST 的特例）节点值关系左子树 < 根 < 右子树同 BST 平衡条件无（可能退化为链表）每个节点的左右子树高度差 ≤ 1 操作复杂度最坏 O(n) 稳定 O(logn) 适用场景数据插入顺序较随机频繁插入、删除、查找的场景平衡因子（Balance Factor） AVL 树通过计算每个节点的平衡因子来维持平衡：平衡因子 = 左子树高度 - 右子树高度若平衡因子的绝对值超过 1（即 < -1 或 > 1），则需要通过旋转操作调整树的结构。旋转操作（核心机制）当插入或删除节点导致树失衡时，AVL 树通过四种旋转操作恢复平衡： LL 旋转（右旋）：在左子树的左子节点插入导致失衡。 RR 旋转（左旋）：在右子树的右子节点插入导致失衡。 LR 旋转（先左旋后右旋）：在左子树的右子节点插入导致失衡。 RL 旋转（先右旋后左旋）：在右子树的左子节点插入导致失衡。示例：LL 旋转失衡树： plaintext 3 (BF=2) / 2 / 1 右旋后： plaintext 2 (BF=0) /
1 3 插入与删除操作插入：按 BST 规则插入新节点；从插入点向上更新平衡因子，若发现失衡则执行旋转。删除：按 BST 规则删除节点；从删除点的父节点向上更新平衡因子，若发现失衡则执行旋转。应用场景数据库索引：需要高效插入、删除和范围查询的场景。计算机图形学：维护动态几何数据（如四叉树、kd 树的基础）。需要严格性能保证的系统：如实时系统中对响应时间敏感的操作。代码示例（Python 实现插入与旋转） python 运行 class Node: def init(self, key): self.key = key self.left = None self.right = None self.height = 1 # 节点高度

class AVLTree: def insert(self, root, key): # 1. 执行标准BST插入 if not root: return Node(key) elif key < root.key: root.left = self.insert(root.left, key) else: root.right = self.insert(root.right, key)

    # 2. 更新当前节点的高度
    root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
    
    # 3. 获取平衡因子
    balance = self.get_balance(root)
    
    # 4. 如果失衡，执行旋转
    # LL情况
    if balance > 1 and key < root.left.key:
        return self.right_rotate(root)
    
    # RR情况
    if balance < -1 and key > root.right.key:
        return self.left_rotate(root)
    
    # LR情况
    if balance > 1 and key > root.left.key:
        root.left = self.left_rotate(root.left)
        return self.right_rotate(root)
    
    # RL情况
    if balance < -1 and key < root.right.key:
        root.right = self.right_rotate(root.right)
        return self.left_rotate(root)
    
    return root

def left_rotate(self, z):
    y = z.right
    T2 = y.left
    
    # 执行旋转
    y.left = z
    z.right = T2
    
    # 更新高度
    z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
    y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
    
    return y

def right_rotate(self, z):
    y = z.left
    T3 = y.right
    
    # 执行旋转
    y.right = z
    z.left = T3
    
    # 更新高度
    z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
    y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
    
    return y

def get_height(self, node):
    return node.height if node else 0

def get_balance(self, node):
    return self.get_height(node.left) - self.get_height(node.right) if node else 0

总结 AVL 树本质上是一种自平衡的 BST，通过强制平衡条件和旋转操作，解决了普通 BST 在极端情况下退化为链表的问题，从而保证了高效的动态操作。它是平衡树的基础，后续衍生出红黑树、B 树等更复杂的数据结构。