编辑“︁平衡树”︁

{{DISPLAYTITLE:平衡树}}  
'''平衡树'''（Balanced Tree）是一种特殊的[[二叉搜索树]]（BST），其通过特定的平衡条件确保树的高度始终保持在<math>O(\log n)</math>级别，从而保证插入、删除和查找操作的最坏时间复杂度为<math>O(\log n)</math>。本文详细介绍平衡树的核心概念、常见类型、实现原理及应用场景。

== 概述 ==  
平衡树的设计目的是解决普通二叉搜索树在极端情况下（如插入有序数据）退化为链表的性能问题。通过动态调整树的结构（如旋转操作），平衡树始终保持左右子树的高度差不超过限定值。

=== 核心性质 ===  
* '''平衡条件'''：不同平衡树的定义略有差异，但通常要求左右子树高度差不超过1（如AVL树）或其他约束（如红黑树的颜色规则）。  
* '''操作效率'''：所有操作（增删查）的时间复杂度为<math>O(\log n)</math>。  
* '''动态调整'''：在插入或删除节点后，通过旋转或重新着色恢复平衡。

== 常见类型 ==  
以下是几种主流的平衡树实现：

=== AVL树 ===  
AVL树是最早的自平衡二叉搜索树，其平衡条件为：任意节点的左右子树高度差（平衡因子）绝对值不超过1。  
==== 旋转操作 ====  
AVL树通过四种旋转恢复平衡：  
* 左旋（Left Rotation）  
* 右旋（Right Rotation）  
* 左右旋（Left-Right Rotation）  
* 右左旋（Right-Left Rotation）  

<mermaid>  
graph TD  
    A[节点A, 平衡因子=2] --> B[节点B]  
    A --> C[空]  
    B --> D[节点D]  
    B --> E[节点E]  
    style A fill:#f9d71c  
    style B fill:#a6e3a1  
</mermaid>  
*图：AVL树失衡示例（节点A的平衡因子为2）*

=== 红黑树 ===  
红黑树通过以下规则保持平衡：  
1. 节点是红色或黑色。  
2. 根节点和叶子节点（NIL）为黑色。  
3. 红色节点的子节点必须为黑色。  
4. 从任一节点到其叶子节点的路径包含相同数量的黑色节点。  

=== B树与B+树 ===  
B树和B+树是用于磁盘存储的多路平衡搜索树，广泛应用于数据库索引。

== 代码示例 ==  
以下为AVL树的Python实现片段，展示插入操作与旋转调整：  

<syntaxhighlight lang="python">  
class AVLNode:  
    def __init__(self, key):  
        self.key = key  
        self.left = None  
        self.right = None  
        self.height = 1  

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

        # 更新高度  
        root.height = 1 + max(self.get_height(root.left),  
                              self.get_height(root.right))  

        # 检查平衡因子  
        balance = self.get_balance(root)  

        # 失衡情况处理  
        if balance > 1 and key < root.left.key:  
            return self.right_rotate(root)  # 右旋  
        if balance < -1 and key > root.right.key:  
            return self.left_rotate(root)   # 左旋  
        if balance > 1 and key > root.left.key:  
            root.left = self.left_rotate(root.left)  
            return self.right_rotate(root)  # 左右旋  
        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  

# 示例用法  
avl = AVLTree()  
root = None  
keys = [10, 20, 30, 40, 50, 25]  
for key in keys:  
    root = avl.insert(root, key)  
</syntaxhighlight>  

'''输出效果'''：插入后树的高度始终平衡，例如输入序列`[10, 20, 30]`会触发左旋，使根节点变为20。

== 实际应用 ==  
* '''数据库索引'''：B+树是MySQL InnoDB引擎的默认索引结构。  
* '''语言标准库'''：C++的`std::map`和Java的`TreeMap`基于红黑树实现。  
* '''文件系统'''：如Ext4文件系统的目录索引使用B树。  

== 总结 ==  
平衡树通过动态调整结构保障高效操作，是算法设计与系统开发中的重要工具。理解其原理有助于优化数据密集型应用的性能。  

{{数据结构基础}}

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:数据结构基础]]