红黑树：解决二叉搜索树性能不平衡的利器

# 1. 红黑树概述**

红黑树是一种平衡二叉搜索树，它通过强制执行一组特定的性质来保持平衡。这些性质确保了红黑树始终保持近似平衡，从而避免了二叉搜索树可能出现的性能不平衡问题。

红黑树的性质包括：

1. 每个节点要么是红色，要么是黑色。
2. 根节点始终是黑色。
3. 每个叶节点（NIL节点）都是黑色。
4. 如果一个节点是红色的，那么它的两个子节点都必须是黑色的。
5. 从根节点到任何叶节点的路径上，黑色节点的数量必须相同。

# 2. 红黑树理论基础

### 2.1 红黑树的定义和性质

红黑树是一种自平衡二叉搜索树，它通过维护一组特定的性质来确保树的高度近似平衡，从而提高了搜索、插入和删除操作的效率。

#### 2.1.1 5条性质

红黑树必须满足以下 5 条性质：

1. **每个节点要么是红色，要么是黑色。**
2. **根节点始终是黑色。**
3. **每个叶节点（NIL）都是黑色。**
4. **如果一个节点是红色的，那么它的两个子节点都必须是黑色的。**
5. **从任何一个节点到其后代叶节点的所有路径上，黑色节点的数量必须相同。**

#### 2.1.2 平衡因子

平衡因子定义为一个节点的黑色子树高度与另一个子树高度之间的差值。对于一个平衡的红黑树，所有节点的平衡因子必须为 0 或 -1。

### 2.2 红黑树的插入和删除操作

红黑树的插入和删除操作是通过一系列旋转操作来维护平衡的。这些操作确保了红黑树的性质始终得到满足。

#### 2.2.1 插入操作

插入操作的步骤如下：

1. 像在普通二叉搜索树中一样插入新节点。
2. 如果新节点的父节点是红色的，则执行以下操作之一：
- **左旋转：**如果新节点是其父节点的左子节点，并且其父节点的右子节点是红色的。
- **右旋转：**如果新节点是其父节点的右子节点，并且其父节点的左子节点是红色的。
3. 如果新节点的父节点是黑色，则不需要进行旋转。

#### 2.2.2 删除操作

删除操作的步骤如下：

1. 像在普通二叉搜索树中一样删除节点。
2. 如果被删除节点是红色的，则不需要进行旋转。
3. 如果被删除节点是黑色的，则执行以下操作之一：
- **左旋转：**如果被删除节点的兄弟节点是红色的，并且其兄弟节点的左子节点是黑色的。
- **右旋转：**如果被删除节点的兄弟节点是红色的，并且其兄弟节点的右子节点是黑色的。
- **双旋转：**如果被删除节点的兄弟节点是黑色的，并且其兄弟节点的两个子节点都是黑色的。

# Python 中红黑树的插入操作

class RedBlackTree:
    def insert(self, key):
        # 像在普通二叉搜索树中一样插入新节点
        new_node = Node(key)
        self._insert(new_node)

        # 执行旋转操作以维护平衡
        while new_node != self.root and new_node.parent.color == 'red':
            if new_node.parent == new_node.parent.parent.left:
                uncle = new_node.parent.parent.right
                if uncle.color == 'red':
                    # 叔叔节点是红色的，执行左旋转和右旋转
                    self._left_rotate(new_node.parent.parent)
                    self._right_rotate(new_node.parent)
                else:
                    # 叔叔节点是黑色的
                    if new_node == new_node.parent.right:
                        # 新节点是其父节点的右子节点，执行左旋转
                        self._left_rotate(new_node.parent)
                    # 执行右旋转
                    self._right_rotate(new_node.parent.parent)
            else:
                uncle = new_node.parent.parent.left
                if uncle.color == 'red':
                    # 叔叔节点是红色的，执行右旋转和左旋转