【数据结构与算法】系列十六 - 红黑树-添加节点

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

添加节点一共有12种情况，只需要把12种情况处理好就行。

一、添加节点

B树中，新元素必定是添加到叶子节点中。4阶B树所有节点的元素个数x都符合1 ≤ x ≤ 3，所以建议新添加的节点默认为RED，这样能够让红黑树的性质尽快满足(性质 1、2、3、5 都满足，性质 4 不一定)。

如果添加的是根节点，染成BLACK即可。

以下有4种情况满足红黑树的性质4：parent为BLACK（同样也满足4阶B树的性质（黑色节点和红色子节点合并为超级节点），因此不用做任何额外处理）。

以下有8种情况不满足红黑树的性质4：parent为RED（连个连续的红色，违背红黑树性质）。其中前4种属于B树节点上溢的情况。

1.1. 修复性质4 – LL\RR

如上图中的新增的52和60节点，不满足红黑树。如果把46(黑)-50(红)-52(红)看作一棵B树子树，要想让46-50-52合并在一个节点中，需要把50(红)染成50(黑)，把46(黑)染成46(红)，这样才可以合并成一个B树节点46(红)-50(黑)-52(红)。同理，把60(红)-72(红)-76(黑)染成60(红)-72(黑)-76(红)。

但是在B树中，黑色节点永远是父节点，所以我们还需要对祖父节点进行旋转。

实现思路：

判定条件:uncle不是RED

  1. parent染成BLACK，grand染成RED
  2. grand进行单旋（LL/RR）操作

1.2. 修复性质4 – LR\RL

如上图中的新增的48和74节点，不满足红黑树。但根据上面的单旋处理方法，我们也可以对新增节点的父节点和祖父节点进行LR/RL。例如对50进行右旋，再对46进行左旋，此时48就是46和50的父节点，所以48是黑色节点，46和50是红色节点。同理对新增的74节点树进行LR，然后对节点着色。

实现思路：

判定条件:uncle不是RED

  1. 自己染成BLACK，grand染成RED
  2. 进行双旋（LR/RL）操作

为什么要判断uncle是不是RED？因为8种情况的前4种新增节点的uncle节点都是RED，而后4种新增节点的uncle不是红色（空节点是黑色）。

1.3. 修复性质4 – 上溢 – LL

把17-25-33看作一个B树，而4阶B树最多存储3个元素，如果继续往该节点新增节点10，就会出现上溢。解决上溢就需要把中间的元素（17或25）取出向上合并，我们选择把节点25向上合并，因为节点25本身就是节点38的子节点，并且分割节点也更加容易（17和33本身就是25的子节点）。然后把分割子节点为10-17和33，同时为了满足红黑树的性质，节点38也需要染成黑色，节点25染成红色，节点17和节点33染成黑色。节点25向上合并会引发节点38和节点55的染色情况，所以把节点25作为新添加的元素（染成红色）来处理即可。

实现思路：
判定条件:uncle是RED

  1. parent、uncle染成BLACK
  2. grand向上合并，并且染成RED，当做是新添加的节点进行处理
  3. grand向上合并时，可能继续发生上溢，若上溢持续到根节点，只需将根节点染成BLACK

上溢是LL情况，但不需要旋转。

1.4. 修复性质4 – 上溢 – RR

RR上溢和LL上溢基本一致。

实现思路：
判定条件:uncle是RED

  1. parent、uncle染成BLACK
  2. grand向上合并，并且染成RED，当做是新添加的节点进行处理
  3. grand向上合并时，可能继续发生上溢，若上溢持续到根节点，只需将根节点染成BLACK

1.5. 修复性质4 – 上溢 – LR

新增节点20如果上溢，向上合并的节点25就需要染成红色，分割后的节点17和节点33需要染成黑色。

实现思路：
判定条件:uncle是RED

  1. parent、uncle染成BLACK
  2. grand向上合并，并且染成RED，当做是新添加的节点进行处理

1.6. 修复性质4 – 上溢 – RL

RL和LR情况也基本一致。

实现思路：
判定条件:uncle是RED

  1. parent、uncle染成BLACK
  2. grand向上合并，并且染成RED，当做是新添加的节点进行处理

1.7. 总结

添加一共有12种情况：

  • 4种情况（parent为BLACK）
    • 不需要做任何处理。
  • 8种情况（parent为RED）
    • 4种情况（uncle不是红色）
      • 单旋
        • parent染成BLACK，grand染成RED
        • grand进行单旋（LL/RR）操作
      • 双旋
        • 自己染成BLACK，grand染成RED
        • 进行双旋（LR/RL）操作
    • 4种情况（uncle是RED）
      • 上溢
        • parent、uncle染成BLACK
        • grand向上合并，并且染成RED，当做是新添加的节点进行处理（grand向上合并时，可能继续发生上溢，若上溢持续到根节点，只需将根节点染成BLACK）

上溢合并仅仅是把对应的代码看做B树处理，但实际上不需要合并和分割，所以上溢情况仅仅是染色而已。

二、具体代码

添加的代码其实很简单，只需要把上面的几种情况列出来即可。

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
@Override
protected void afterAdd(Node<E> node) {
  Node<E> parent = node.parent;
  
  // 添加的是根节点 或者 上溢到达了根节点
  // 此处代码不能放到if (isBlack(parent)) return;的后面，因为默认添加的节点是红色，而colorOf方法中节点如果是null直接判断是黑色
  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);
  }
}

建议：红黑树（RBTree）和AVL树（AVLTree）继承一个新的类平衡二叉搜索树（BBST），BBST继承二叉搜索树（BST），BST继承二叉树（BinaryTree）。