---
title: "07-红黑树"
created: 2025-12-02
tags:
  - Java
---
# 红黑树

> [!note] 定位说明
> Map 系列收尾的前置知识篇（独立数据结构讲解）：五大性质、旋转操作、为什么近似平衡。读懂它，TreeMap/TreeSet 源码不再神秘。

红黑树是一种高效的自平衡二叉搜索树，通过以下5条规则确保平衡性：

**五大核心规则**：

1. 节点非红即黑
2. 根节点必须为黑
3. 叶子节点（NIL）全黑
4. 红色节点不能有红子节点（无连续红）
5. 任意节点到叶子路径的黑色节点数相同

**平衡原理**：

通过约束黑色节点数量（规则5）和限制红色节点连续出现（规则4），确保最长路径不超过最短路径的两倍，从而维持近似平衡。当插入/删除破坏规则时，通过**颜色翻转+旋转**修复。

**插入操作示例**（插入后修复平衡）：

假设初始红黑树如下（B表示黑，R表示红）：

```
       B8
       / \
     R5  B10
    /  \
  B3   B7
```

**步骤1：插入红色节点6**

插入时新节点默认为红色，减少破坏规则5的可能性：

```
       B8
       / \
     R5  B10
    /  \
  B3   B7
         \
          R6  ← 新增节点
```

此时父节点7是黑色，不违反规则，插入完成。

**步骤2：触发颜色翻转（父节点为红，叔节点为红）**

假设插入节点4到3的右侧：

```
        B8
       / \
     R5  B10
    /  \
  B3   B7
 / \
NIL R4 ← 新增节点
```

此时父节点3为红，违反规则4。检查叔节点7：

- 父红、叔红 → 进行**颜色翻转**
- 父、叔变黑，祖父5变红
- 祖父5变为红后，检查其父节点8是否为红（此处8为根节点需保持黑）

调整后：

```
        B8
       / \
     B5  B10
    /  \
  R3   R7
 / \
NIL R4
```

**步骤3：触发旋转（父红叔黑，形成三角结构）**

假设继续插入节点2到3左侧：

```
        B8
       / \
     B5  B10
    /  \
  R3   R7
 / \
R2  R4 ← 新增节点2
```

此时父节点3为红，子节点2也为红，违反规则4。检查叔节点7（红）：

- 父红、叔红 → 颜色翻转（同步骤2）
- 父3、叔7变黑，祖父5变红
- 但祖父5的父节点8为黑，无需进一步调整

调整后：

```
        B8
       / \
     R5  B10
    /  \
  B3   B7
 / \
B2  B4
```

**关键修复操作总结**：

1. **颜色翻转**：当父节点和叔节点均为红时，将父、叔变黑，祖父变红。
2. **左旋/右旋**：当父红叔黑且形成"三角结构"时，通过旋转将问题转换为线性结构。
3. **旋转+变色**：线性结构下（如父红且同侧子红），旋转后调整颜色。

**对比AVL树**：

- 红黑树：通过颜色约束宽松平衡，减少旋转次数，适合频繁插入删除场景。
- AVL树：严格平衡（左右子树高度差≤1），查找更快但维护成本高。

通过上述机制，红黑树在动态数据场景下以较低维护成本维持高效操作（O(log n)）。
---
⬅️ [[06-TreeMap源码解析|TreeMap源码解析]] 🏠 [[00-Java|00-Java]] ➡️ [[00-容器选型总对比|00-容器选型总对比]]