红黑树

• 红黑树也是一种自平衡二叉搜索树
• 以前也叫做平衡二叉B树（Symmetric Binary B-tree）

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

1. 节点是Red或者Black
2. 根节点必须是Black
3. 叶子节点（外部节点、空节点）都是Black，强制每个节点度为2，子节点挂一个null节点（空想，不需要实际添加空节点）
4. Red节点的子节点，必须都是Black
   • Red节点的父节点，必须都是Black
   • 从根节点到叶子节点的所有路径上不能有2个连续的Red节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的Black节点

问题

为什么在这5条性质的约束下，就能保证二叉树的平衡

判断红黑树

请问下面这颗是红黑树吗

不是红黑树

• 满足大部分红黑树的性质
• 不满足从任一节点到叶子节点的所有路径都包含相同数目的Black节点
  • 将红黑树的null节点补齐
  • 可观察到38节点的子节点个数不同

红黑树与4阶B树等价变换

如图所示的红黑树，令所有红色节点向上提升一层

• 红黑树与4阶B树具有等价性
• Black节点与它的Red子节点融合在一起，形成1个B树节点
• 红黑树中Black节点的个数 = 4阶B树的节点总个数 （4阶B树的每个节点中，有且只有一个Black节点）

分类

具体的，又可以分为4种情况

红黑红

黑红

红黑

黑

红黑树术语

名称	说明
parent	父节点
sibling	兄弟节点：同层的其他节点
uncle	叔父节点：父节点的兄弟节点
grand	祖父节点：父节点的父节点

基本代码

判断节点颜色

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;

}

给节点着色

private RBNode<E> color(Node<E> node, boolean color) {

if (node != null) ((RBNode<E>) node).color = color;

return (RBNode<E>) node;

}

将节点染为黑色

private RBNode<E> black(Node<E> node) {

return color(node, BLACK);

}

将节点染为红色

private RBNode<E> red(Node<E> node) {

return color(node, RED);

}

返回节点的兄弟节点

public Node<E> sibling() {

if (isLeftChild()) return parentNode.rightNode;

if (isRightChild()) return parentNode.leftNode;

return null;

}

基本代码

/**

* 红黑树

*/

public class MyRedBlackTree<E> extends MyBinarySearchTree<E> {

private static final boolean RED = false;

private static final boolean BLACK = true;

public MyRedBlackTree() {

}

public MyRedBlackTree(Comparator<E> comparator) {

super(comparator);

}

@Override

protected void afterAdd(Node<E> node) {

super.afterAdd(node);

}

@Override

protected void afterRemove(Node<E> node) {

super.afterRemove(node);

}

// 判断节点颜色

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;

}

// 给节点着色

private RBNode<E> color(Node<E> node, boolean color) {

if (node != null) ((RBNode<E>) node).color = color;

return (RBNode<E>) node;

}

// 将节点染为黑色

private RBNode<E> black(Node<E> node) {

return color(node, BLACK);

}

// 将节点染为红色

private RBNode<E> red(Node<E> node) {

return color(node, RED);

}

private static class RBNode<E> extends Node<E> {

boolean color = RED; // 默认为红色

public RBNode(E element, Node<E> parentNode) {

super(element, parentNode);

}

// 返回节点的兄弟节点

public Node<E> sibling() {

if (isLeftChild()) return parentNode.rightNode;

if (isRightChild()) return parentNode.leftNode;

return null;

}

public boolean isLeftChild() {

return parentNode != null && this == parentNode.leftNode;

}

public boolean isRightChild() {

return parentNode != null && this == parentNode.rightNode;

}

}

}

添加节点

关键

心中有B树

已知：

• B树中，新元素必定添加到叶子节点中
• 4阶B树所有节点的元素个数x ∈ [1, 3]
• 推荐新添加的节点默认为Red，这样能够让红黑树的性质尽快满足（性质——Red节点的父子节点必定是Black不一定满足）
• 如果添加的节点是根节点，将节点染色为Black

添加的所有情况

如图所示，一共有12种情况

不需要做处理的4种情况（parent为Black）

• 默认新添加的节点颜色为Red
• 如果新节点的父节点为Black，则满足红黑树Red节点parent节点为Black的性质，一共有4种情况（5、10、11、12）可以满足
• 同样满足4阶B树的性质（新添加的Red节点融入原本的B树节点）
• 因此不需要做任何额外处理

8种不满足红黑树Red父子节点为Black、出现连续红节点情况（parent为Red）

出现连续Red节点，Double Red

• 一共8种情况（1、2、3、4、6、7、8、9）
• 其中，4种情况满足新节点的uncle为Red，4种情况满足uncle不是Red
  • 1、2、3、4，新节点的uncle为Red
  • 5、6、7、8，新节点的uncle不是Red

添加——修正连续红色节点——uncle不是Red

LL|RR 单旋 (2种情况)

对应情况7、8

解决：

判定条件：uncle不是Red

RR：

• 将parent染为Black （图中50染为黑色）
• grand染为Red （图中46染为红色）
• grand左旋（grand grand parent指向parent） （图中46左旋，46成为50的左子树，38指向50）

LL：

• 将parent染为Black
• grand染为Red
• grand右旋

LR|RL 双旋 (2种情况)

对应情况6、9

判定条件：uncle不是Red

1. 新节点自己染为Black
2. grand染为Red
3. 旋转
   • RL：parent右旋；grand左旋
   • LR：parent左旋；grand右旋

添加——修正连续红色节点——uncle是Red（红黑红）——上溢

LL 染色

对应情况1，此处对根节点进行简化，方便理解

• 根据4阶B树性质，发生上溢，需要将一个节点向上合并，原先的节点发生分裂

先处理分裂后的左右子树

• 新节点的parent从Red染为Black （图中17）
• uncle从Red染为Black （图中33）

再处理向上合并节点

• grand向上合并 （图中25）

重要思路

• grand的向上合并，看一看做是对上层节点添加一个新节点的操作
• 根据这个思路，可以将合并节点染为Red，之后无非就是红黑树添加的12种情况，可以重复处理，即递归

合并的实现

• 将grand染为Red，递归添加即可

注意

• grand向上合并时，可能发生上溢
• 若上溢持续到根节点，只需将根节点染为Black

RR 染色

与LL染色一样

• parent染黑、uncle染黑
• grand向上合并，染红，递归添加

LR 染色

同理

RL 染色

同理

添加代码实现

• 重写afterAdd(Node<E> newNode)方法
• 处理不需要额外操作的4种情况，即parent为Black的情况
  • 不作处理，直接返回
• 处理uncle不是Red的4种情况，需要旋转
  • 旋转实现方式与AVL树一模一样，代码可以直接复用
  • LL—— grand右旋，parent染为Black，grand染为Red
  • RR—— grand左旋，parent染为Black，grand染为Red
  • LR——parent左旋、grand右旋、自己染为Black，grand染为Red
  • RL—— parent右旋，grand左旋、自己染为Black，grand染为Red
• 处理uncle是Red的4种情况，仅需染色
  • parent染为Black
  • uncle染为Black
  • grand向上合并：将grand当做新添加的节点，添加到上层节点中，即，grand染为Red再递归添加

重写afterAdd方法，其中旋转操作是对AVL树代码的复用

@Override

protected void afterAdd(Node<E> newNode) {

RBNode<E> parentNode = (RBNode<E>) newNode.parentNode;

if (parentNode == null) {

black(newNode); // 添加的是根节点，设置为黑色

return;

}

// 处理不需要额外操作的4种情况，即parent为black的情况

if (isBlack(parentNode)) return;// 父节点为黑，不需要做任何处理

// 叔父节点

RBNode<E> uncle = (RBNode<E>) parentNode.sibling();

// 祖父节点

RBNode<E> grand = (RBNode<E>) parentNode.parentNode;

// 处理uncle不是red的4种情况

if (isRed(uncle)) { // 如果uncle是红色

// 仅需染色

// parent、uncle染为黑色

black(parentNode);

black(uncle);

// grand作为新节点添加上上层节点

// 染为红色，递归添加

afterAdd(red(grand));

return;

}

// uncle不是Red的4中情况，涉及旋转，旋转实现与AVL树一模一样

if (parentNode == grand.leftNode) { // L

if (newNode == parentNode.leftNode) { // LL

// parent染为黑色，grand染为红色

black(parentNode);

red(grand);

// grand右旋

rotateRight(grand);

} else if (newNode == parentNode.rightNode) { // LR

// 自己染为黑色，grand染为红色，

black(newNode);

red(grand);

// parent左旋，grand右旋

rotateLeft(parentNode);

rotateRight(grand);

}

} else if (parentNode == grand.rightNode) { // R

if (newNode == parentNode.leftNode) { // RL

// 自己染为黑色，grand染为红色，

black(newNode);

red(grand);

// parent右旋，grand左旋

rotateRight(parentNode);

rotateLeft(grand);

} else if (newNode == parentNode.rightNode) { // RR

// parent染为黑色，grand染为红色

black(parentNode);

red(grand);

// grand左旋

rotateLeft(grand);

}

}

}

注意

重写createNode方法，实例化红黑树节点，默认实例化的是Node节点，在染色方法中会触发强制类型转换异常

重写createNode方法

@Override

protected Node<E> createNode(E element, Node<E> parentNode) {

return new RBNode<>(element, parentNode);

}

测试

重写string方法，这个方法是打印二叉树工具类的那个方法

• 对于红黑树的打印，我们希望观察节点的颜色
• 打印红节点的颜色，黑色节点默认不打印颜色

重写string方法，打印红黑树节点的颜色

@Override

public Object string(Object node) {

RBNode<E> rbNode = (RBNode<E>) node;

StringBuilder sb = new StringBuilder();

sb.append(rbNode.element);

if (isRed(rbNode))

sb.append("R");

return sb.toString();

}

测试代码

private static void addTest() {

Integer[] data = new Integer[]{

85, 19, 69, 3, 7, 99, 95, 2, 1, 70, 44, 58, 11, 21, 14, 93, 57, 4, 56

};

MyRedBlackTree<Integer> rbt = new MyRedBlackTree<>();

MyBinarySearchTree<Integer> bst = new MyBinarySearchTree<>();

for (Integer d : data) {

rbt.add(d);

bst.add(d);

}

BinaryTrees.println(bst);

System.out.println("---------------");

BinaryTrees.println(rbt);

}

运行结果

┌────────85────────┐

│ │

┌──────19──────┐ ┌─99

│ │ │

┌─3─┐ ┌─69─┐ ┌─95

│ │ │ │ │

┌─2 ┌─7─┐ ┌─44─┐ 70 93

│ │ │ │ │

1 4 11─┐ 21 ┌─58

│ │

14 ┌─57

│

56

--------------------------------------------

┌────────69────────┐

│ │

┌───19R───┐ ┌─95─┐

│ │ │ │

┌─7─┐ ┌─44─┐ ┌─85─┐ 99

│ │ │ │ │ │

┌─2R─┐ 11─┐ 21 ┌─57─┐ 70R 93R

│ │ │ │ │

1 3─┐ 14R 56R 58R

│

4R

将这颗红黑树整理成4阶B树的形式

---

删除节点（维持红黑树）

注意：再次强调

在B树中，最终实际在内存层面上删除的，都是叶子节点

与添加类似，叶子节点这一层，会出现红黑红、红黑、黑红、黑，四种情况

删除红色节点

不需要做任何处理，因为不会破坏红黑树的5条性质

删除黑色节点

一共有3种情况：

1. 拥有2个Red节点的Black节点 （红黑红）
   • 不可能被直接删除，因为会找它的子节点替代删除（本质上讲，是其前驱或后继节点）
   • 其两个子节点都是Red，而Red的删除不需要做任何处理
   • 故，直接删除，不需要做任何处理
2. 拥有1个Red节点的Black节点 （黑红 | 红黑）
3. 删除的是Black叶子节点

删除拥有一个红色子节点的黑色节点（红黑|黑红）

对应图中46和76

判定条件：用以替代的子节点是Red （前驱 | 后继为Red）

• 删除节点
• 将替代节点染为Black即可

删除黑色叶子节点

特点

分为两大情况

1. 被删除节点的兄弟节点sibling为黑色
2. 被删除节点的兄弟节点sibling为红色

第一类——兄弟节点为黑色

• 首先考虑：整个树中只有一个黑色节点，即，它是根节点，也是叶子节点——直接删除不做额外处理
• 删除真正的黑色叶子节点：如图中46、88节点，会发生下溢，需要从同辈兄弟节点哪里借节点
  • 存在同辈兄弟节点的情况：且同辈兄弟节点必须为黑色（红色同辈节点实际上是4阶B树中的父节点，不是同辈兄弟节点）且同辈兄弟节点至少具有一个红色子节点
    • 同辈为 黑红
    • 同辈为 红黑
    • 同辈为 红黑红
  • 存在同辈兄弟节点的情况：且同辈兄弟节点必须为黑色，但孤苦伶仃，没有任何红色子节点
    • 同辈为 黑

• 判定条件：如果兄弟sibling至少有1个Red子节点
  • 进行旋转操作
  • 旋转之后的中心节点继承被删除节点的parent的颜色
  • 旋转之后，中心节点的左右子节点都保证是Black，不是Black就进行染色染成黑色

如下图所示

同辈为 黑红，要删除88，被借用元素为78，被借用元素属于被删除节点88的父节点80的L R，因此对78的p 76进行左旋，78的grand 80进行右旋，之后78称为中心节点，继承被删除节点88的父节点80的颜色（此处为红色），最后确保78的左右节点76、80都为黑色，因为80是红色，故将80染黑

---

同辈为 红黑，要删除88，被借用元素为72，被借用元素属于被删除元素88的父节点80的L L，因此对72的grand 80进行右旋，之后76称为中心节点，需要继承被删除元素88的父节点80的颜色，此处80为红色，故将76从黑染红，最后，确保76的左右节点72、80都为黑色，此处72、80都是红色，故将72、80都染色为黑色

---

同辈为 红黑红，既可以按照LL处理，也可以按照LR处理

• 由于LL进行一次右旋，LR进行一次左旋一次右旋，方便起见，按照LL处理
• 按照LL与LR处理的结果并不相同，但结果都满足红黑树的性质

要删除88，被借用元素为72，是被删除节点88的父节点80的LL，故对72的grand 80进行右旋，之后76成为中心节点，要继承被删除节点88的父节点80的颜色（此处为红色），故将76从黑染红，最后，确保76的左右子节点72、80都为黑色，此处72、80都为红色，故将72、80染黑

---

判定条件：如果兄弟sibling没有一个Red子节点

• 对应B树中，兄弟没得借的情况，按照B树的处理方式，应当将父节点中的元素向下合并
• 将sibling染成Red，被删除节点的parent染成Black，维持红黑树的性质

• 如果被删除节点的parent也是Black
• 下溢，触发parent向下合并，导致parent的位置也发生下溢
• 此时，将parent视作一个被删除的节点处理即可 （递归）

---

第二类——兄弟节点为红色

• 如果sibling为Red
• 被借用节点不是sibling的红色子节点，而是看sibling的黑色子节点有没有红色的子节点（很难获取）
• 解决：强行让sibling的子节点变成被删除节点的兄弟节点sibling
  • parent进行旋转（根据红色sibling是被删除节点的具体位置确定旋转方式）
  • sibling染为Black；parent染为Red
  • 旋转之后，sibling发生了变化，现在变成了parent.leftNode
• 再次回到sibling为Black的情况

删除代码实现（维持红黑树）

删除拥有一个红色子节点的黑色节点 （红黑 | 黑红）

注意

为了方便实现，对afterRemove(Node<E> node)方法进行修改，添加一个参数replacement用来传递代替节点

• 对二叉搜索树中调用afterRemove方法的代码进行相应调整
• AVL树重写afterRemove方法的代码进行相应调整

二叉搜索树修改afterRemove方法,添加一个参数

protected void afterRemove(Node<E> node, Node<E> replacement) {

}

在二叉搜索树中，对调用afterRemove的代码进行相应调整

/**

* 删除指定节点

*

* @param node 要删除的节点

*/

private void remove(Node<E> node) {

if (node == null) return;

// 3. 删除度为2的节点

if (node.hasTwoChildren()) { // 度为2

// 找到前驱节点

Node<E> predecessor = predecessor(node);

// 前驱节点的值覆盖到要删除节点

node.element = predecessor.element;

// 删除前驱节点，先让引用node指向前驱节点predecessor

// 之后再删除node即可

node = predecessor;

}

// 删除node节点，node度必然为0或1

// 找到子节点

Node<E> replacementNode = node.leftNode != null ? node.leftNode : node.rightNode;

// 2. 删除度为1的节点

if (replacementNode != null) {

replacementNode.parentNode = node.parentNode; // 更改parent

// 更改node.parent的左或右子节点

if (node.parentNode == null) { // node为度为1 的 根 节点

// 根节点指向replacement

rootNode = replacementNode;

} else if (node == node.parentNode.leftNode)

node.parentNode.leftNode = replacementNode;

else

node.parentNode.rightNode = replacementNode;

// afterRemove 删除平衡

afterRemove(node, replacementNode);

} else if (node.parentNode == rootNode) { // 是根节点的叶子节点

rootNode = null;

// afterRemove 删除平衡

afterRemove(node, null);

} else { // 1. 删除叶子节点 度为0, 但不是根节点

if (node.parentNode.rightNode == node)

node.parentNode.rightNode = null;

else

node.parentNode.leftNode = null;

// afterRemove 删除平衡

afterRemove(node, null);

}

size--;

}

在红黑树中，重写afterRemove(Node<E> node, Node<E> replacement)方法

• 先被删除节点的颜色，删除Red节点不需要做任何处理
• 具有一个Red子节点的Black节点，直接删除Black节点，将替代节点染为黑色Black
  • 此处不需要判断红黑红的情况，即要删除的Black具有2个Red子节点的情况，因为在删除度为2的黑色节点时，node最终指向了要删除黑色节点的替代节点（前驱节点或后继节点），而这个替代节点必然是红色，根据上一条，代码直接return不做任何处理

红黑树重写afterRemove方法，实现删除具有1个红色子节点的黑色节点功能

@Override

protected void afterRemove(Node<E> node, Node<E> replacement) {

// 先判断被删除节点的颜色，如果删除的是红色节点，则不需要做任何处理

if (isRed(node)) return;

// 来到这里：删除的是 黑色 节点

// 用来取代node的子节点是红色节点 （红黑 或 黑红情况）

if (isRed(replacement)) {

black(replacement);

return;

}

// 来到这里：删除的是 黑色叶子 节点

...

}

删除黑色叶子节点

1. 获取兄弟节点sibling
   • 叶子节点的删除，一定经历了被删除节点的parent的左节点或右节点被设置为null（利用引用计数、垃圾回收机制删除），因此被删除节点的parent的左右节点已经被修改（因为被删掉的节点就是parent的一个子节点，已经被删了），不能准去获取当前被删除node的兄弟节点，sibling()方法结果不准确
   • 反过来思考，可以根据当前node的parent的子节点是否为空来确定，如果parent的左子节点为null，说明node之前是parent的左，即parent.leftNode，如果是parent的右子节点为null，说明node之前是parent.rightNode，我们取parent相反方向的子节点就是node的兄弟节点了
   • 还要兼容被删除node的parent是黑色节点，触发连续下溢递归调用afterRemove方法的情况，这种情况下node指向的是连续下溢传进去的原先的parent，这个节点并没有被真正删除，只是进行B树调整，因此应当使用node.isLeftChild()或者node.isRightChild()方法来帮助确定sibling
2. 判断兄弟节点sibling的位置，是node的左兄弟，还是node的右兄弟；之后的旋转操作具有对称性，相反方向就采用相反旋转即可
3. 判断兄弟节点sibling的颜色（按照node为右，sibling为左来书写）
   • sibling为Red—— 通过旋转、染色，转化为sibling为Black的情况
     • sibling染黑；parent染红
     • parent右旋
     • 右旋之后，node的sibling发生变化，应当更新为parent.leftNode
   • sibling为Black——观察兄弟节点有没有红色子节点可以借过来用
     • sibling有Red子节点可供借用——对应黑红、红黑、红黑红三种情况——判定条件：sibling至少有1个Red子节点
       • 进行旋转：
         • 黑红——LR：sibling左旋，parent右旋——判定条件：sibling的左节点不是红
         • 红黑——LL：parent右旋——sibling左节点是红色
         • 红黑红——LL：parent右旋——sibling左节点是红色
         • Tips:经过分析，可以先处理黑红——LR情况，sibling经过一次左旋之后，接下来三种情况都是parent右旋，可以重用代码

         • 注意更新sibling

           Tips：红黑——LR情况下sibling发生了旋转，旋转过后，当前sibling指向的已经不是node的兄弟节点，所以要对sibling进行更新，更新为parent.leftNode

       • 进行染色：
         • 旋转过后，兄弟节点sibling变为中心节点，令其继承原先parent的颜色
         • 确保中心节点的左右子节点为黑色
     • sibling孤苦伶仃，没有Red子节点可以借用——对应黑一种情况——判定条件：sibling没有Red子节点
       • 先判断父节点parent的颜色
       • parent为红色：父节点parent向下与sibli
ng进行合并
         • parent染黑；sibling染红
       • parent本来就是黑色：parent节点向下合并会在parent这里再次触发下溢，进行递归调用
         • sibling染红
         • 递归调用afterRemove()，传入parent节点

实现

完整的红黑树afterRemove维持红黑特性代码

@Override

protected void afterRemove(Node<E> node, Node<E> replacement) {

// 先判断被删除节点的颜色，如果删除的是红色节点，则不需要做任何处理

if (isRed(node)) return;

// 来到这里：删除的是 黑色 节点

// 用来取代node的子节点是红色节点 （红黑 或 黑红情况）

if (isRed(replacement)) {

black(replacement);

return;

}

Node<E> parent = node.parentNode;

// 来到这里：删除的是 黑色叶子 节点

// 整个红黑树只有一个黑色节点。又是根节点，又是叶子节点

if (parent == null) return;

// 来到这里：删除的是 黑色叶子 节点，且不是 根节点

// 1. 获取兄弟节点`sibling`

// sibling()方法返回结果不准确，改为根据parent左右子节点哪个为空

// 来获取node的兄弟节点sibling

// tips: 还要兼容连续下溢触发的递归调用afterRemove，这种情况下

// parent.leftNode 或 parent.rightNode并没有被设置为null，因为递归传入

// 节点并没有被真正删除，其parent的子节点指针依然指向它

boolean isNodeLeftChild = parent.leftNode == null || ((RBNode<E>) node).isLeftChild();

Node<E> sibling = isNodeLeftChild ? parent.rightNode : parent.leftNode;

// 2. 判断sibiling是node的左兄弟还是右兄弟

if (!isNodeLeftChild) { // 说明node是右， sibling是左

// 3. 判断兄弟节点sibling的颜色

if (isRed(sibling)) { // 兄弟节点为红色

// 在这里将 sibling 为红色的情况，转化为sibling为黑色的情况处理

// 通过 旋转 、 染色 实现

black(sibling);

red(parent);

rotateRight((RBNode<E>) parent);

// 旋转之后，node的sibling发生了变化，现在应当是parent.leftNode

sibling = parent.leftNode;

}

// 来到这里：sibling一定是黑色，开始编写sibling为黑色的删除代码

// 判断sibling有没有红色节点可以拿出来借用

// 1. 没有 ， 父节点向下合并， 如果父节点本身也是 黑色 ， 则父节点也下溢，触发递归

if (isBlack(sibling.leftNode) && isBlack(sibling.rightNode)) { // 左右都是黑，没红

// 1.1 先判断parent的颜色

boolean isParentBlack = isBlack(parent);

// 1.2 如果是红色，则parent向下与sibling合并 -> parent染黑，sibling染红

if (isParentBlack) { // parent本来就是黑的

red(sibling);

afterRemove(parent, null);

} else {

// 1.3 如果本来就是黑色，parent合并触发parent也下溢

// 那么。sibling染红，递归调用afterRemove(parent)

red(sibling);

black(parent);

}

} else { // 2. 有，就拿出来给node借用，对应 红黑、黑红、红黑红 三种情况

// 2.1 旋转

// 2.1.1 确定 黑红 情况， 因为它属于 LR ，需要先对sibling进行一次左旋

// 2.1.1 判定 黑红 的条件： sibling的leftNode是黑色，不是红色

if (isBlack(sibling.leftNode)) {

rotateLeft((RBNode<E>) sibling);

// !!!!!!! sibling已经不是node的兄弟，更新sibling为当前pareng.leftNode

sibling = parent.leftNode;

}

// 2.1.2 黑红LR 红黑LL 红黑红 三种情况，统一为parent右旋

rotateRight((RBNode<E>) parent);

// 2.2 染色

// 2.2.1 sibling称为中心节点，继承parent的颜色

color(sibling, colorOf(parent));

// 2.2.2 确保中心节点sibling的左右节点都为黑色

/* black(sibling.leftNode);

black(sibling.parentNode);*/

black(sibling.leftNode);

black(sibling.rightNode);

}

} else { // sibling 是右

// 与sibling 在左的代码，完全对称

// 3. 判断兄弟节点sibling的颜色

if (isRed(sibling)) { // 兄弟节点为红色

// 在这里将 sibling 为红色的情况，转化为sibling为黑色的情况处理

// 通过 旋转 、 染色 实现

black(sibling);

red(parent);

rotateLeft((RBNode<E>) parent);

// 旋转之后，node的sibling发生了变化，现在应当是parent.rightNode

sibling = parent.rightNode;

}

// 来到这里：sibling一定是黑色，开始编写sibling为黑色的删除代码

// 判断sibling有没有红色节点可以拿出来借用

// 1. 没有 ， 父节点向下合并， 如果父节点本身也是 黑色 ， 则父节点也下溢，触发递归

if (isBlack(sibling.leftNode) && isBlack(sibling.rightNode)) { // 左右都是黑，没红

// 1.1 先判断parent的颜色

boolean isParentBlack = isBlack(parent);

// 1.2 如果是红色，则parent向下与sibling合并 -> parent染黑，sibling染红

if (isParentBlack) { // parent本来就是黑的

red(sibling);

afterRemove(parent, null);

} else {

// 1.3 如果本来就是黑色，parent合并触发parent也下溢

// 那么。sibling染红，递归调用afterRemove(parent)

red(sibling);

black(parent);

}

} else { // 2. 有，就拿出来给node借用，对应 红黑、黑红、红黑红 三种情况

// 2.1 旋转

// 2.1.1 确定 红黑 情况， 因为它属于 RL ，需要先对sibling进行一次右旋

// 2.1.1 判定 红黑 的条件： sibling的rightNode是黑色，不是红色

if (isBlack(sibling.rightNode)) {

rotateRight((RBNode<E>) sibling);

// !!!!!!! sibling已经不是node的兄弟，更新sibling为当前parent.rightNode

sibling = parent.rightNode;

}

// 2.1.2 黑红LR 红黑LL 红黑红 三种情况，统一为parent左旋

rotateLeft((RBNode<E>) parent);

// 2.2 染色

// 2.2.1 sibling称为中心节点，继承parent的颜色

color(sibling, colorOf(parent));

// 2.2.2 确保中心节点sibling的左右节点都为黑色

/* black(sibling.rightNode);

black(sibling.parentNode);*/

black(sibling.rightNode);

black(sibling.leftNode);

}

}

}

测试

测试代码

红黑树删除测试

private static void deleteTest() {

Integer[] data = new Integer[]{

55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50

};

MyRedBlackTree<Integer> rbt = new MyRedBlackTree<>();

for (Integer d : data) {

rbt.add(d);

}

BinaryTrees.println(rbt);

for (Integer d : data) {

System.out.println("删除 => " + d);

rbt.remove(d);

BinaryTrees.println(rbt);

System.out.println("------------------------");

}

}

运行结果

┌────70───┐

│ │

┌─56─┐ ┌─87─┐

│ │ │ │

┌─22R─┐ 62─┐ 74 ┌─96

│ │ │ │

20 ┌─55 68R 90R

│

50R

删除 => 55

┌────70───┐ 删除度为1的黑色节点，剩下的红色节点50染为黑色

│ │

┌─56─┐ ┌─87─┐

│ │ │ │

┌─22R─┐ 62─┐ 74 ┌─96

│ │ │ │

20 50 68R 90R

------------------------

删除 => 87

┌────70───┐ 1. 找到87的前驱节点，74，将74这个值覆盖87

│ │ 2. 删除原先的74节点，sibling为96，sibling有一个左红90

┌─56─┐ ┌─90─┐ 3. sibling在右，RL，sibling 96右旋，原先sibling的左

│ │ │ │ 红90变为当前被删除节点的新sibling

┌─22R─┐ 62─┐ 74 96 4. parent 87(值已经为74)进行左旋，sibling 90成为中心节点

│ │ │ 5. sibling 90继承parent87(74)的颜色（黑色）

20 50 68R 6. sibling 90的左右子节点都染黑，87(74)、96染黑

------------------------

删除 => 56

┌────70───┐ 1. 找到前驱节点50，将56的值用50覆盖

│ │ 2.删除真正的50节点，它是黑色叶子节点

┌─50─┐ ┌─90─┐ 3. 50的sibling为 20，也是个黑色叶子节点，没有任何红子节点

│ │ │ │ 4. 无法借用，触发父节点22向下与sibling20合并

┌─22 62─┐ 74 96 5. 父节点22染黑，sibling20染红

│ │

20R 68R

------------------------

删除 => 74

┌──70─┐

│ │

┌─50R─┐ 90─┐

│ │ │

┌─22 62─┐ 96R

│ │

20R 68R

------------------------

删除 => 96

┌─70─┐

│ │

┌─50R─┐ 90

│ │

┌─22 62─┐

│ │

20R 68R

------------------------

删除 => 22

┌─70─┐

│ │

┌─50R─┐ 90

│ │

20 62─┐

│

68R

------------------------

删除 => 62

┌─70─┐

│ │

┌─50R─┐ 90

│ │

20 68

------------------------

删除 => 20

┌─70─┐

│ │

50─┐ 90

│

68R

------------------------

删除 => 70

┌─68─┐

│ │

50 90

------------------------

删除 => 68 1. 找到68的前驱节点50，替换68的值

50─┐ 2. 删除原先的50，sibling为90，是黑色叶子节点，且没有红色子节点

│ 3. 没法从sibling借，父节点68（已经是50）向下合并，sibling染红

90R 4. 父节点68（50）也是个黑色节点，继续触发下溢，递归afterRemove

------------------------ 5. 68(50)是根节点，进入afterRemove，获取它的parent为null

删除 => 90 不进行任何处理，直接return

50

------------------------

删除 => 50

------------------------

// 到这里树删没了

优化删除节点后的维持红黑树方法

注意

这部分优化是为了代码形式上的统一，并不强制要求

原先的代码更利于思路上的理解

优化afterRemove(Node<E> node, Node<E> replacement)方法，去除replacement参数，使得方法形式统一

• 修改二叉搜索树代码，afterRemove方法移除replacement参数
• AVL树代码做响应调整
• 修改二叉搜索树remove方法，其中对afterRemove()方法的调用，都只传node，但在删除度为1节点的代码部分对afterRemove进行调用时，传递replacement参数，不传node
  • 分析传replacement和传node的区别
    1. 对于AVL树，没有区别，因为AVL的调整逻辑是，顺着传入的节点，一直向上找祖先节点，直到找到第一个失衡节点，维护高度，恢复平衡
    2. 对于红黑树，有区别，因为红黑树删除节点时，传递replacement只发生在删除度为1的节点时，这种情况下，replacement需要从红色被染为黑色，afterRemove第一行就是判断节点颜色为红色，直接返回，不做任何处理
  • 解决：将afterRemove一开始的判断红色移除，同之后判断replacement颜色并染黑的代码合并

删除前

@Override

protected void afterRemove(Node<E> node, Node<E> replacement) {

// 先判断被删除节点的颜色，如果删除的是红色节点，则不需要做任何处理

if (isRed(node)) return;

// 来到这里：删除的是 黑色 节点

// 用来取代node的子节点是红色节点 （红黑 或 黑红情况）

if (isRed(replacement)) {

black(replacement);

return;

}

...

}

删除、合并后

@Override

protected void afterRemove(Node<E> node) {

// 先判断被删除节点的颜色，如果删除的是红色节点，则不需要做任何处理

// if (isRed(node)) return;

// 来到这里：删除的是 黑色 节点

// 用来取代node的子节点是红色节点 （红黑 或 黑红情况）

if (isRed(node)) {

black(node);

return;

}

...

}

合并后，针对先前直接删除红色节点的情况，多做了一次染色，但是这个被染色的节点实际上没有引用，会被垃圾回收机制清除，因此也对程序没有结果上的影响

修改二叉搜索树remove方法，调用afterRemove时只传递node参数，在删除度为1节点代码部分调用afterRemove时，传递replacement

/**

* 删除指定节点

*

* @param node 要删除的节点

*/

private void remove(Node<E> node) {

if (node == null) return;

// 3. 删除度为2的节点

if (node.hasTwoChildren()) { // 度为2

// 找到前驱节点

Node<E> predecessor = predecessor(node);

// 前驱节点的值覆盖到要删除节点

node.element = predecessor.element;

// 删除前驱节点，先让引用node指向前驱节点predecessor

// 之后再删除node即可

node = predecessor;

}

// 删除node节点，node度必然为0或1

// 找到子节点

Node<E> replacementNode = node.leftNode != null ? node.leftNode : node.rightNode;

// 2. 删除度为1的节点

if (replacementNode != null) {

replacementNode.parentNode = node.parentNode; // 更改parent

// 更改node.parent的左或右子节点

if (node.parentNode == null) { // node为度为1 的 根 节点

// 根节点指向replacement

rootNode = replacementNode;

} else if (node == node.parentNode.leftNode)

node.parentNode.leftNode = replacementNode;

else

node.parentNode.rightNode = replacementNode;

// afterRemove 删除平衡

afterRemove(replacementNode); // !! 传replacement

} else if (node.parentNode == null) { // 是根节点的叶子节点

rootNode = null;

// afterRemove 删除平衡

afterRemove(node);

} else { // 1. 删除叶子节点 度为0, 但不是根节点

if (node.parentNode.rightNode == node)

node.parentNode.rightNode = null;

else

node.parentNode.leftNode = null;

// afterRemove 删除平衡

afterRemove(node);

}

size--;

}

红黑树的平衡

回到最初的问题

为什么红黑树必须满足的5条性质，就可以保证红黑树是平衡二叉搜索树?

• 红黑树的5条性质，可以绝对保证红黑树等价于4阶B树
• 从B树的角度看，红黑树是平衡的
• 从二叉搜索树的角度看，红黑树并不像AVL那么平衡，是一种比较宽泛的平衡，但也是平衡的，能够确保树不会退化成线性表
  • 红黑树宽泛平衡的准确描述：相比AVL树，红黑树没有一条路径会大于其他路径的二倍，即最极端情况下，红黑树的最长路径不会超过最短路径的二倍
  • 满足上述平衡特性的原因：
    1. 红黑树所有路径上黑色节点的数目相同，推出路径长度的区别一定是因为红色节点的数目不同
    2. 红黑树不允许出现连续红色节点，因此一个路径上n个黑色节点之间最多额外添加n个红色节点，即整个路径最多不超过2n个节点；最短路径一定是只有黑色节点的路径，根据上一条，纯黑色节点路径的长度一定是n，综上：可推出红黑树的宽泛平衡特性

• 红黑树可视为弱平衡，或称黑高度平衡——只算路径上的黑色节点的话，满足严格平衡
• 红黑树的最大数高是 2 * log(n + 1)，依然是O(logn)级别

平均时间复杂度

决定因素

• 作为平衡二叉搜索树，其平均时间复杂度依然取决于树的具体高度
• 出现递归调用，会传播多大的节点规模

操作	红黑树 时间复杂度	AVL树 时间复杂度
搜索	O(logn)	O(logn)
添加	O(logn), O(1)次旋转	O(logn), O(1)次旋转
删除	O(logn), O(1)次旋转	O(logn), 最多需要O(logn)次旋转操作

红黑树删除操作时的afterRemove方法递归调用，根据红黑树的5条性质，基于统计学，发生概率极低，最多递归3次，故认为复杂度为O(1)

红黑树 对比 AVL树

特征	AVL	红黑树
平衡 标准	强平衡：任一节点左右子树高度差不超过1	弱平衡：最长路径不会长于最短路径的2倍
最大 高度	1.44 * log(n + 2) - 1.328 (100万个节点高度不超过28)	2 * log(n + 1) (100万个节点高度不超过40)
时间 复杂度	搜索、添加、删除O(logn)，添加O(1)旋转，删除最多O(logn)旋转	搜索、添加、删除O(logn)；添加、删除设计的旋转操作复杂度都为O(1)

AVL树与红黑树的选择

• 搜索次数远远大于插入和删除——选择AVL树
  • 树高比红黑树低，搜索更快
  • 避免了AVL删除时旋转复杂度高的弱势
• 搜索、插入、删除次数几乎差不多——选择红黑树
  • 相对AVL数来讲，树高没有明显增长，依然保证了平衡性
  • 优秀的插入和删除性能

• 相对于AVL树，红黑树牺牲了部分平衡性以换取插入、删除操作时更低的旋转复杂度
• 总体上讲，红黑树性能优于AVL树，实际中更多采用红黑树