编辑“︁红黑树”︁

= 红黑树 =

'''红黑树'''（Red-Black Tree）是一种自平衡的二叉搜索树（BST），它通过特定的规则确保树在插入和删除操作后保持近似平衡，从而保证最坏情况下的时间复杂度为O(log n)。红黑树广泛应用于计算机科学中，例如在C++的STL（标准模板库）中的`std::map`和`std::set`，以及Java的`TreeMap`和`TreeSet`。

== 基本性质 ==
红黑树必须满足以下五个性质：
1. '''节点颜色'''：每个节点是红色或黑色。
2. '''根节点'''：根节点必须是黑色。
3. '''叶子节点'''：所有叶子节点（NIL节点，即空节点）是黑色。
4. '''红色节点规则'''：如果一个节点是红色，则它的两个子节点必须是黑色（即不能有两个连续的红色节点）。
5. '''黑高平衡'''：从任一节点到其每个叶子节点的所有路径上，黑色节点的数量相同（称为“黑高”）。

这些性质确保了红黑树的平衡性，使得最长路径不会超过最短路径的两倍。

== 红黑树的操作 ==

=== 插入操作 ===
插入新节点时，初始颜色为红色（以尽量不违反黑高平衡），然后通过旋转和重新着色调整树的结构以满足红黑树的性质。插入可能涉及以下情况：
1. 新节点是根节点（直接染黑）。
2. 父节点是黑色（无需调整）。
3. 父节点和叔节点都是红色（重新着色父、叔和祖父节点，并递归检查祖父节点）。
4. 父节点是红色，叔节点是黑色（通过旋转和重新着色调整）。

=== 删除操作 ===
删除操作比插入更复杂，因为可能需要调整树的结构以维持平衡。删除后，如果破坏了红黑树的性质，需要通过旋转和重新着色修复。

== 代码示例 ==
以下是一个红黑树的简单实现（使用Python）：

<syntaxhighlight lang="python">
class Node:
    def __init__(self, key, color='red'):
        self.key = key
        self.color = color  # 'red' or 'black'
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.NIL = Node(None, 'black')  # Sentinel node
        self.root = self.NIL

    def insert(self, key):
        new_node = Node(key)
        new_node.left = self.NIL
        new_node.right = self.NIL
        new_node.parent = None

        # Standard BST insertion
        parent = None
        current = self.root
        while current != self.NIL:
            parent = current
            if new_node.key < current.key:
                current = current.left
            else:
                current = current.right
        new_node.parent = parent
        if parent is None:
            self.root = new_node
        elif new_node.key < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node

        # Fix violations
        self._fix_insert(new_node)

    def _fix_insert(self, node):
        while node != self.root and node.parent.color == 'red':
            if node.parent == node.parent.parent.left:
                uncle = node.parent.parent.right
                if uncle.color == 'red':
                    # Case 1: Uncle is red
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    # Case 2: Uncle is black
                    if node == node.parent.right:
                        node = node.parent
                        self._left_rotate(node)
                    # Case 3: Recolor and rotate
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self._right_rotate(node.parent.parent)
            else:
                # Mirror cases
                uncle = node.parent.parent.left
                if uncle.color == 'red':
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    if node == node.parent.left:
                        node = node.parent
                        self._right_rotate(node)
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self._left_rotate(node.parent.parent)
        self.root.color = 'black'

    def _left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def _right_rotate(self, y):
        x = y.left
        y.left = x.right
        if x.right != self.NIL:
            x.right.parent = y
        x.parent = y.parent
        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        x.right = y
        y.parent = x
</syntaxhighlight>

=== 输入与输出示例 ===
假设我们依次插入键值 `[10, 20, 30, 15, 25]`：
1. 插入10（根节点，染黑）。
2. 插入20（红色，无需调整）。
3. 插入30（违反性质，左旋并重新着色）。
4. 插入15（红色，父节点为红色，叔节点为红色，重新着色）。
5. 插入25（红色，父节点为红色，叔节点为黑色，旋转并重新着色）。

最终红黑树的结构如下（简化为层级表示）：
```
        20 (black)
       /   \
  15 (black) 25 (black)
    /         \
10 (red)     30 (red)
```

== 实际应用 ==
红黑树的高效平衡特性使其广泛应用于：
1. '''数据库索引'''：如MySQL的InnoDB引擎使用红黑树优化查询。
2. '''内存管理'''：Linux内核的虚拟内存管理使用红黑树跟踪内存区域。
3. '''编程语言库'''：如C++的`std::map`和Java的`TreeMap`。

== 红黑树与其他平衡树的比较 ==
* 与'''AVL树'''相比，红黑树的平衡条件更宽松，插入和删除操作更快，但查询稍慢。
* 与'''B树'''相比，红黑树更适合内存中的数据存储，而B树更适合磁盘存储。

== 可视化示例 ==
以下是一个红黑树的Mermaid图表示例：

<mermaid>
graph TD
    20[20 (black)] --> 15[15 (black)]
    20 --> 25[25 (black)]
    15 --> 10[10 (red)]
    25 --> 30[30 (red)]
</mermaid>

== 数学分析 ==
红黑树的高度最多为<math>2 \log_2(n + 1)</math>，其中<math>n</math>是节点数。这一性质保证了其操作的时间复杂度为O(log n)。

== 总结 ==
红黑树是一种高效的自平衡二叉搜索树，通过颜色和旋转规则确保近似平衡。它在插入、删除和查找操作中均表现优异，是许多高级数据结构的核心实现方式。

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