【数据结构与算法】系列十五 - 红黑树

发表于 | 分类于 ， ， ，
| 字数统计 2.1k 字 | 阅读时长 8 分钟

本章节展示的红黑树都会省略NULL节点。

一、红黑树

1.1. 基本概念

红黑树（Red Black Tree）也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树（Symmetric Binary B-tree）。

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

  1. 根节点是BLACK；
  2. 节点是RED或者BLACK；
  3. 叶子节点（也叫做外部节点或空节点，注意和二叉树的叶子节点概念不太一样）都是BLACK；
  4. RED节点的子节点都是 BLACK；
    • 推理1：RED节点的parent（父节点）都是BLACK
    • 推理2：从根节点到叶子节点的所有路径上不能有2个连续的RED节点
  5. 从任一节点到叶子节点（空节点）的所有路径都包含相同数目的BLACK节点。

注意：红黑树会把度为0或者1的节点，“添加”空节点后变为度为2的节点（变成了真二叉树，即节点的度只有0或2），空节点是假想的，仅仅是为了便于理解红黑树的性质，实际代码中不会增加空节点。

请问下面这棵是红黑树么？

解答：不是，因为不满足红黑树性质5（从任一节点到叶子节点（空节点）的所有路径都包含相同数目的BLACK节点），例如55-38-null(右子树)有2个BLACK节点，而其他路径都有3个BLACK节点。

红黑树是否计算空节点，取决于代码怎么写。如果空节点参与计算个数，就全部参与；如果不参与计数，则全部空节点都不计。

1.2. 红黑树的等价变换

  • 红黑树和4阶B树(2-3-4树)具有等价性
  • BLACK节点与它的RED子节点融合在一起，形成1个B树节点
  • 红黑树的BLACK节点个数与4阶B树的节点总个数相等

注意：有些资料用2-3树与红黑树进行类比，这是极其不严谨的，2-3树并不能完美匹配红黑树的所有情况。

1.3. 红黑树 vs 2-3-4树

红黑树的黑节点和它的红色子节点合并成一个节点后就是一颗4阶B树。并且合并后的节点有以下几种情况：

1. 红黑红：

2. 黑红：

3. 红黑：

4. 黑：

思考：如果上面的四种示例最底层的BLACK节点是不存在的，在B树中是什么样的情形?
解答：整棵B树只有1个节点，而且是超级节点。

二、操作（代码）

为了方便操作红黑树节点，我们需要增加节点几个概念：

  • sibling：兄弟节点
    • 例：17和33，25和46
  • parent：父节点
    • 例：17和33的父节点是25，50的父节点是46
  • uncle：叔父节点（parent的兄弟节点）
    • 例：25是50的叔父节点，46是17的叔父节点
  • grand：祖父节点（parent的父节点）
    • 例：38是17、33、50的祖父节点

辅助函数：

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
// 红黑树
public class RBTree<E> extends BBST<E> {
  // 定义红黑变量（非红即黑，所以使用boolean）
  private static final boolean RED = false;
  private static final boolean BLACK = true;

  public RBTree() {
    this(null);
  }

  public RBTree(Comparator<E> comparator) {
    super(comparator);
  }

  @Override
  // 添加节点后
  protected void afterAdd(Node<E> node) {
    Node<E> parent = node.parent;
    
    // 添加的是根节点 或者 上溢到达了根节点
    if (parent == null) {
      black(node);
      return;
    }
    
    // 如果父节点是黑色，直接返回
    if (isBlack(parent)) return;
    
    // 叔父节点
    Node<E> uncle = parent.sibling();
    // 祖父节点
    Node<E> grand = red(parent.parent);
    if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
      black(parent);
      black(uncle);
      // 把祖父节点当做是新添加的节点
      afterAdd(grand);
      return;
    }
    
    // 叔父节点不是红色
    if (parent.isLeftChild()) { // L
      if (node.isLeftChild()) { // LL
        black(parent);
      } else { // LR
        black(node);
        rotateLeft(parent);
      }
      rotateRight(grand);
    } else { // R
      if (node.isLeftChild()) { // RL
        black(node);
        rotateRight(parent);
      } else { // RR
        black(parent);
      }
      rotateLeft(grand);
    }
  }

  // 节点染色
  private Node<E> color(Node<E> node, boolean color) {
    if (node == null) return node;
    ((RBNode<E>)node).color = color;
    return node;
  }

  // 节点变成红色
  private Node<E> red(Node<E> node) {
    return color(node, RED);
  }

  // 节点变成黑色
  private Node<E> black(Node<E> node) {
    return color(node, BLACK);
  }

  // 获取节点颜色（红色false，黑色true）
  private boolean colorOf(Node<E> node) {
    return node == null ? BLACK : ((RBNode<E>)node).color;
  }

  // 是否黑色节点
  private boolean isBlack(Node<E> node) {
    return colorOf(node) == BLACK;
  }

  // 是否红色节点
  private boolean isRed(Node<E> node) {
    return colorOf(node) == RED;
  }

  @Override
  protected Node<E> createNode(E element, Node<E> parent) {
    return new RBNode<>(element, parent);
  }

  private static class RBNode<E> extends Node<E> {
    // 默认红色
    boolean color = RED;
    public RBNode(E element, Node<E> parent) {
      super(element, parent);
    }
    
    @Override
    public String toString() {
      String str = "";
      if (color == RED) {
        str = "R_";
      }
      return str + element.toString();
    }
  }
}

// 二叉树中的Node类
protected static class Node<E> {
  E element;
  Node<E> left;
  Node<E> right;
  Node<E> parent;
  public Node(E element, Node<E> parent) {
    this.element = element;
    this.parent = parent;
  }
  
  // 是否叶子节点
  public boolean isLeaf() {
    return left == null && right == null;
  }
  
  // 是否有两个子节点
  public boolean hasTwoChildren() {
    return left != null && right != null;
  }
  
  // 是否是左子节点
  public boolean isLeftChild() {
    return parent != null && this == parent.left;
  }
  
  // 是否是右子节点
  public boolean isRightChild() {
    return parent != null && this == parent.right;
  }
  
  // 获取兄弟节点
  public Node<E> sibling() {
    if (isLeftChild()) {
      return parent.right;
    }
    
    if (isRightChild()) {
      return parent.left;
    }
    
    return null;
  }
}

注意：B树仅仅是为了辅助理解红黑树。

三、平衡及对比

3.1. 红黑树的平衡

为何那5条性质，就能保证红黑树是平衡的？那5条性质，可以恰好保证红黑树等价于4阶B树，而B树高度又比较矮，所以整体上红黑树是平衡的。

疑问：B树展开后的红黑树高度就会变高，还平衡么？二叉搜索树平衡的概念是组成二叉树的高度越小就越平衡。所以高度只要不是太高（甚至退化成一个链表），就可以认为达到了平衡。

相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍（最短路径高度是B树的高度，而最长的路径是比最短的路径多红色，如果每个黑色都有一个红色子节点，最长路径肯定是最短路径的2倍，黑-黑 < 黑-红-黑-红）。

红黑树是一种弱平衡（相对AVL树）、黑高度平衡（只计算黑节点的高度时，高度都是一样的）。

红黑树的最大高度是2 ∗ log2(n + 1)，依然是O(logn)级别。

3.2. 平均时间复杂度

搜索：O(logn)

添加：O(logn)，O(1)次的旋转操作

删除：O(logn)，O(1)次的旋转操作

3.3. AVL树 vs 红黑树

3.3.1. AVL树

平衡标准比较严格：每个左右子树的高度差不超过1。

最大高度是1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28）。

搜索、添加、删除的复杂度都是O(logn)，其中添加仅需O(1)次旋转调整、删除最多需要O(logn)次旋转调整。

3.3.2. 红黑树

平衡标准比较宽松：没有一条路径会大于其他路径的2倍。

最大高度是2 ∗ log2(n + 1)（100W个节点，红黑树最大树高40）。

搜索、添加、删除的复杂度都是O(logn)，其中添加、删除都仅需O(1)次旋转调整。

3.3.3. 选择

搜索的次数远远大于插入和删除，选择AVL树。

搜索、插入、删除次数几乎差不多，选择红黑树。

相对于AVL树来说，红黑树牺牲了部分平衡性（牺牲高度）以换取插入/删除操作时少量的旋转操作，整体来说红黑树性能要优于AVL树。

红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树。

3.4. BST vs AVL Tree vs Red Black Tree

一棵树有以下节点：10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96。分别对比二叉搜索树、AVL树、红黑树。

二叉搜索树：

AVL树：

红黑树：

红黑树是在AVL树基础上优化后的版本。