编辑“︁平衡二叉树”︁

{{DISPLAYTITLE:平衡二叉树}}

'''平衡二叉树'''（Balanced Binary Tree）是计算机科学中一种重要的[[非线性数据结构]]，它通过特定的平衡机制确保树的高度始终保持在<math>O(\log n)</math>级别，从而保证查找、插入和删除等操作的高效性。最常见的平衡二叉树实现包括[[AVL树]]和[[红黑树]]。

== 基本概念 ==
平衡二叉树是指任意节点的左右子树高度差（平衡因子）不超过1的二叉搜索树（BST）。这种平衡性通过旋转操作维护，确保最坏情况下的时间复杂度仍为对数级。

=== 关键性质 ===
* 每个节点的左右子树高度差绝对值 ≤ 1
* 子树也必须是平衡二叉树
* 对于n个节点，树的高度h满足：<math>h = O(\log n)</math>

<mermaid>
graph TD
    A((4)) --> B((2))
    A --> C((6))
    B --> D((1))
    B --> E((3))
    C --> F((5))
    C --> G((7))
</mermaid>
''图1：高度为2的平衡二叉树示例''

== 平衡操作 ==
当插入或删除节点导致树不平衡时（平衡因子 > 1），需要通过旋转操作恢复平衡。主要旋转类型包括：

=== 左旋（Left Rotation） ===
用于解决"右右"不平衡情况：
<mermaid>
graph TD
    subgraph 旋转前
    A((A)) --> B((B))
    A --> C((C))
    C --> D((D))
    C --> E((E))
    end
    subgraph 旋转后
    F((C)) --> G((A))
    F --> H((E))
    G --> I((B))
    G --> J((D))
    end
</mermaid>

=== 右旋（Right Rotation） ===
用于解决"左左"不平衡情况：
<mermaid>
graph TD
    subgraph 旋转前
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    end
    subgraph 旋转后
    F((B)) --> G((D))
    F --> H((A))
    H --> I((E))
    H --> J((C))
    end
</mermaid>

== 代码实现（AVL树示例） ==
以下是Python实现的AVL树核心代码片段：

<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.getHeight(root.left),
                              self.getHeight(root.right))
        
        # 获取平衡因子
        balance = self.getBalance(root)
        
        # 不平衡情况处理
        # 左左情况
        if balance > 1 and key < root.left.key:
            return self.rightRotate(root)
        # 右右情况
        if balance < -1 and key > root.right.key:
            return self.leftRotate(root)
        # 左右情况
        if balance > 1 and key > root.left.key:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
        # 右左情况
        if balance < -1 and key < root.right.key:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)
        
        return root
    
    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        
        # 执行旋转
        y.left = z
        z.right = T2
        
        # 更新高度
        z.height = 1 + max(self.getHeight(z.left),
                           self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                           self.getHeight(y.right))
        
        return y
    
    # 右旋实现类似左旋（对称操作）
</syntaxhighlight>

'''输入/输出示例'''：
<pre>
插入序列: 10, 20, 30, 40, 50, 25

生成的AVL树结构:
        30
       /  \
     20    40
    / \     \
  10  25    50
</pre>

== 时间复杂度分析 ==
平衡二叉树保证所有操作在最坏情况下仍高效：
{| class="wikitable"
|-
! 操作 !! 时间复杂度
|-
| 查找 || <math>O(\log n)</math>
|-
| 插入 || <math>O(\log n)</math>
|-
| 删除 || <math>O(\log n)</math>
|}

== 实际应用 ==
1. '''数据库索引'''：许多数据库系统使用平衡二叉树（特别是其变种如B树）实现索引结构
2. '''内存分配器'''：Linux内核的虚拟内存管理使用红黑树跟踪内存区域
3. '''事件调度'''：Java的Timer类使用平衡二叉树管理定时任务
4. '''网络路由'''：路由器使用平衡树结构高效存储和查找路由表

== 变种与扩展 ==
* '''红黑树'''：通过颜色标记和更宽松的平衡条件减少旋转次数
* '''AA树'''：通过"级别"概念简化的平衡树实现
* '''伸展树'''：通过"伸展"操作将最近访问节点移到根处

== 练习建议 ==
1. 手动构建一个AVL树，插入序列[14, 17, 11, 7, 53, 4, 13]
2. 实现删除操作的平衡维护
3. 比较不同平衡树实现的性能差异

平衡二叉树是理解高效数据存储和检索的基础，掌握其原理对设计高性能系统至关重要。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]