小菜鸟

java菜鸟号正在起航

0%

红黑树

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 6.4k 阅读时长 ≈ 6 分钟

红黑树：自平衡二叉查找树的高效实现

红黑树是一种自平衡的二叉查找树，通过一套特定的规则（颜色约束和旋转操作）保证树的高度始终维持在O(logn)级别，解决了普通二叉查找树在极端情况下退化为链表（查询效率降至O(n)）的问题。它广泛应用于 Java 的TreeMap、C++ 的map等集合类，以及数据库索引的底层实现。

二叉查找树的局限性与红黑树的诞生

二叉查找树的核心特性

二叉查找树（BST）满足：

  • 左子树所有节点值 < 根节点值；
  • 右子树所有节点值 > 根节点值；
  • 左右子树均为二叉查找树。

其查询、插入、删除的平均时间复杂度为O(logn)，但在有序插入时（如依次插入 1,2,3,4），会退化为单链表，此时操作复杂度飙升至O(n)。

根据二分查找树的特性来说，使用中序遍历可以得到一个由小到大的有序序列。

插入节点

  • 以根节点为当前节点开始搜索
  • 新节点的值与当前节点比较
  • 如果新节点大于当前节点，则以当前节点的右子节点作为新的当前节点；如果新节点小于当前节点，则以当前节点的左子节点作为新的当前节点
  • 重复上述操作，直到搜索到合适的叶子节点，将该新节点添加为叶子节点的左/右节点

删除节点

  • 如果删除的节点是叶子节点，只需将它从其父节点中删除
  • 如果不是叶子节点，且只有一个子节点，被删除的节点p只有左子树，将p的左子树pL添加为p的父节点的左子树；被删除的节点p只有右子树，将p的右子树pR添加为p的父节点的右子树
  • 如果被删除的p的左右节点都非空，有两种做法
    • 做法一：将pL设为p的父节点q的左或右子节点，将pR设为p节点的中序前驱结点s的右子节点(s是pL最右下节点)
    • 做法二：以p节点的中序前驱或后继替代p所指节点，然后再从原二叉查找树中删去中序前驱或后继节点(用大于p的最小节点或小于p的最大节点代替p节点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
static class TreeNode<E> {
    E data;
    TreeNode<E> parent;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E data) {
        this.data = data;
    }

    public TreeNode(E data, TreeNode<E> parent, TreeNode<E> left, TreeNode<E> right) {
        this.data = data;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        TreeNode<?> treeNode = (TreeNode<?>) o;

        if (!data.equals(treeNode.data)) return false;
        if (!parent.equals(treeNode.parent)) return false;
        if (!left.equals(treeNode.left)) return false;
        return right.equals(treeNode.right);
    }

    @Override
    public int hashCode() {
        int result = data.hashCode();
        result = 31 * result + parent.hashCode();
        result = 31 * result + left.hashCode();
        result = 31 * result + right.hashCode();
        return result;
    }
}

// 根节点
private TreeNode<E> root;

public LookBinTree(E root) {
    this.root = new TreeNode<>(root);
}

/**
 * 添加节点
 *
 * @param data
 * @return
 */
public void add(E data) {
    // 根节点为空，则为根节点
    if (root == null) {
        root = new TreeNode<>(data);
    } else {
        TreeNode<E> current = root;
        TreeNode<E> parent = null;
        // 从根节点往下搜索,找到合适的叶子节点
        int cmp = 0;
        do {
            parent = current;
            cmp = data.compareTo(parent.data);
            if (cmp > 0) { // 新节点大于当前节点
                current = current.right;
            } else { // 新节点小于当前节点
                current = current.left;
            }
        } while (current != null);
        // 创建新节点
        TreeNode<E> newNode = new TreeNode<>(data, parent, null, null);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }

    }
}

/**
 * 删除节点
 *
 * @param data
 */
public void remove(E data) {
    TreeNode<E> node = getNode(data);
    if (node == null) { // 没有该元素
        return;
    }

    if (node.left == null && node.right == null) { // 左右子树都是空的
        if (node == root) { // 如果是根节点
            root = null;
        } else {
            if (node.parent.left == node) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
            node.parent = null;
        }

    } else if (node.left == null && node.right != null) { // 左子树为空，右子树不为空
        if (node == root) { // 如果是根节点
            root = node.right;
        } else {
            // 被删除的节点是父节点的左子节点
            if (node.parent.left == node) {
                node.parent.left = node.right;
            } else { // 被删除的节点是父节点的右子节点
                node.parent.right = node.right;
            }
            node.right.parent = node.parent;
        }

    } else if (node.left != null && node.right == null) { // 左子树不为空，右子树为空
        if (node == root) { // 如果是根节点
            root = node.left;
        } else {
            // 被删除的节点是父节点的左子节点
            if (node.parent.left == node) {
                node.parent.left = node.left;
            } else { // 被删除的节点是父节点的右子节点
                node.parent.right = node.left;
            }
            node.left.parent = node.parent;
        }

    } else { // 左右子树都不为空
        TreeNode<E> leftMaxNode = node.left;
        // 找到左子树的最大值
        while (leftMaxNode.right != null) {
            leftMaxNode = leftMaxNode.right;
        }
        leftMaxNode.parent.right = null;
        leftMaxNode.parent = node.parent;
        if(node == node.parent.left){ // 被删除的是父节点的左子树
            node.parent.left = leftMaxNode;
        } else {
            node.parent.right = leftMaxNode;
        }

        leftMaxNode.left = node.left;
        leftMaxNode.right = node.right;
        node.parent = node.left = node.right = null;

    }
}

public TreeNode<E> getNode(E data) {
    // 从根节点往后搜索
    TreeNode<E> current = root;
    while (current != null) {
        int cmp = data.compareTo(current.data);
        if (cmp > 0) {
            current = current.right;
        } else if (cmp < 0) {
            current = current.left;
        } else {
            return current;
        }
    }
    return null;
}

红黑树的改进思路

红黑树在 BST 的基础上增加了颜色属性（红或黑）和平衡规则，通过插入 / 删除后的变色和旋转操作，确保树的高度始终为O(logn)，从而保证所有操作的时间复杂度稳定在O(logn)。

红黑树的五大核心特性

红黑树的节点除了 BST 的data、left、right、parent外，多了一个color属性（红 / 黑）。其必须满足以下规则：

  1. 颜色约束：每个节点要么是红色，要么是黑色。
  2. 根节点规则：根节点必须是黑色。
  3. 叶子节点规则：所有叶子节点（NIL 节点，空节点）必须是黑色。
  4. 红色节点规则：若一个节点是红色，则其两个子节点必须是黑色（不允许连续两个红色节点）。
  5. 黑色平衡规则：从任一节点到其所有叶子节点的路径中，黑色节点的数量必须相同（称为 “黑色高度”）。

红黑树

特性的作用

  • 规则 4 避免了 “红色链” 过长，规则 5 保证了各路径的黑色节点数均衡。
  • 两者结合，使得红黑树的最长路径长度不超过最短路径的 2 倍，从而保证树高为O(logn)。

红黑树的基本操作：变色与旋转

当插入或删除节点破坏红黑树的规则时，需通过变色和旋转恢复平衡。

1. 变色

将节点的颜色从红改为黑，或从黑改为红（通常用于调整黑色高度或避免连续红色节点）。

  • 例：若父节点和叔叔节点均为红色，可将两者改为黑色，祖父节点改为红色（避免连续红节点）。

2. 旋转

旋转分为左旋和右旋，用于调整节点的位置关系，不改变 BST 的有序性，仅调整树的结构以平衡高度。

（1）左旋（逆时针旋转）

将节点x旋转为其右孩子y的左孩子，y的左孩子成为x的右孩子。

1
2
3
4
5
6
左旋前：       左旋后：
  x           y
   \         /
    y   →   x
   /         \
  a           a

作用：将右子树的高度转移到左子树，减少右偏。

（2）右旋（顺时针旋转）

将节点y旋转为其左孩子x的右孩子，x的右孩子成为y的左孩子。

1
2
3
4
5
6
右旋前：       右旋后：
    y           x
   /           \
  x     →       y
   \           /
    a         a

作用：将左子树的高度转移到右子树，减少左偏。

红黑树的插入操作

插入的新节点默认是红色（若设为黑色，会直接破坏黑色平衡规则，调整成本更高）。插入后需根据父节点的颜色和叔叔节点的状态，分情况处理：

插入场景与处理策略

情况 1：新节点是根节点
  • 直接将其改为黑色（满足规则 2）。
情况 2：父节点是黑色
  • 新节点为红色，父节点为黑色，无连续红节点，无需调整（满足所有规则）。
情况 3：父节点是红色，叔叔节点也是红色
  • 问题：父节点（红）+ 新节点（红）→ 违反规则 4（连续红节点）。
  • 处理：
    1. 父节点和叔叔节点改为黑色；
    2. 祖父节点改为红色；
    3. 以祖父节点为新节点，递归向上调整（可能影响更高层的平衡）。
情况 4：父节点是红色，叔叔节点是黑色（或不存在）

  • 问题：连续红节点，且叔叔节点无法通过变色分担（叔叔为黑）。

  • 处理：根据新节点、父节点、祖父节点的位置关系，结合旋转 + 变色解决：

    | 子节点位置 | 父节点位置 | 操作步骤 |
    | ——————— | ———————— | —————————————————————————————— |
    | 父节点的左孩子 | 祖父节点的左孩子 | 1. 祖父节点右旋； 2. 父节点与祖父节点交换颜色（父变黑，祖父变红）。 |
    | 父节点的右孩子 | 祖父节点的左孩子 | 1. 父节点左旋（转为上一种情况）； 2. 按上一种情况处理。 |
    | 父节点的右孩子 | 祖父节点的右孩子 | 1. 祖父节点左旋； 2. 父节点与祖父节点交换颜色。 |
    | 父节点的左孩子 | 祖父节点的右孩子 | 1. 父节点右旋（转为上一种情况）； 2. 按上一种情况处理。 |

插入示例

插入节点10到红黑树中，假设父节点8为红，祖父节点15为黑，叔叔节点20为黑：

  1. 新节点10是父节点8的右孩子，父节点8是祖父节点15的左孩子 → 符合 “情况 4-2”；
  2. 先对父节点8左旋，将10变为8的父节点；
  3. 对祖父节点15右旋，10成为新的祖父节点；
  4. 交换10与15的颜色（10变黑，15变红），最终满足所有规则。

红黑树的删除操作

删除操作比插入更复杂，需先按 BST 的规则删除节点，再通过变色和旋转恢复红黑树规则。核心是处理 “删除黑色节点导致黑色平衡被破坏” 的场景，具体分为：

  • 被删节点是红色：直接删除，不影响平衡；
  • 被删节点是黑色：需通过 “借调兄弟节点的黑色” 或 “合并节点” 恢复黑色平衡（过程类似插入，但涉及更多旋转组合）。

红黑树与其他平衡树的对比

平衡树类型 核心平衡策略 优势 劣势 适用场景
红黑树 颜色规则 + 有限旋转 旋转操作少，插入删除效率高 平衡精度低于 AVL 树 集合类（TreeMap）、数据库索引
AVL 树 左右子树高度差≤1 严格平衡，查询效率略高 旋转操作多，插入删除效率低 查询密集场景

红黑树的应用场景

  • Java 集合：TreeMap、TreeSet底层基于红黑树实现，保证元素有序且操作高效。
  • Linux 内核：进程调度的 CFS（完全公平调度器）用红黑树管理进程优先级。
  • 数据库：部分索引结构（如 SQLite 的 B 树变体）借鉴红黑树的平衡思想。

总结

红黑树通过 “颜色约束” 和 “旋转操作” 实现自平衡，确保树高始终为O(logn)，从而在查询、插入、删除操作中保持O(logn)的稳定效率。其设计兼顾了平衡精度和操作成本，是实际应用中最广泛的平衡树结构之一

相关文章

欢迎关注我的其它发布渠道