◼ 红黑树也是一种自平衡的二叉搜索树
以前也叫做平衡二叉B树（Symmetric Binary B-tree）
◼ 红黑树必须满足以下 5 条性质
- 节点是
RED或者 BLACK - 根节点是 BLACK
- 叶子节点（外部节点，空节点）都是 BLACK
-
RED节点的子节点都是 BLACK
RED节点的 parent 都是 BLACK
从根节点到叶子节点的所有路径上不能有 2 个连续的RED节点 - 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点
红黑树的等价变换
◼ 红黑树 和 4阶B树（2-3-4树）具有等价性
◼ BLACK 节点与它的 RED子节点融合在一起，形成1个B树节点
◼ 红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等
◼ 网上有些教程：用 2-3树 与 红黑树 进行类比，这是极其不严谨的，2-3树 并不能完美匹配 红黑树 的所有情况
后面展示的红黑树省略了 NULL 节点
红黑树 vs 2-3-4树
思考：如果上图最底层的 BLACK 节点是不存在的，在B树中是什么样的情形？
整棵B树只有1个节点，而且是超级节点
几个英文单词
◼ parent：父节点
◼ sibling：兄弟节点
◼ uncle：叔父节点（ parent 的兄弟节点）
◼ grand：祖父节点（ parent 的父节点）
添加结点
◼ 已知
B树中，新元素必定是添加到叶子节点中
4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3
◼ 建议新添加的节点默认为
RED，这样能够让红黑树的性质尽快满足（性质 1、2、3、5 都满足，性质 4 不一定）◼ 如果添加的是根节点，染成 BLACK 即可
添加的所有情况
1. 有 4 种情况满足红黑树的性质 4 ：parent 为 BLACK
同样也满足 4阶B树 的性质,因此不用做任何额外处理
2. 有 8 种情况不满足红黑树的性质 4 ：parent 为 RED（ Double Red ）
其中前 4 种属于B树节点上溢的情况
2.1 添加 – 修复性质4 – LL\RR
◼ 判定条件：uncle 不是 RED
-
parent染成 BLACK，grand染成RED -
grand进行单旋操作
LL：右旋转
RR：左旋转
2.2 添加 – 修复性质4 – LR\RL
◼ 判定条件：uncle 不是 RED
- 自己染成 BLACK，
grand染成RED - 进行双旋操作
LR：parent 左旋转， grand 右旋转
RL：parent 右旋转， grand 左旋转
2.3 添加 – 修复性质4 – 上溢 – LL
◼ 判定条件：uncle 是 RED
-
parent、uncle染成 BLACK -
grand向上合并
染成RED，当做是新添加的节点进行处理
◼ grand 向上合并时，可能继续发生上溢
若上溢持续到根节点，只需将根节点染成 BLACK
2.4 添加 – 修复性质4 – 上溢 – RR
◼ 判定条件：uncle 是 RED
-
parent、uncle染成 BLACK -
grand向上合并
染成RED，当做是新添加的节点进行处理
2.5 添加 – 修复性质4 – 上溢 – LR
◼ 判定条件：uncle 是 RED
-
parent、uncle染成 BLACK -
grand向上合并
染成RED，当做是新添加的节点进行处理
2.6 添加 – 修复性质4 – 上溢 – RL
◼ 判定条件：uncle 是 RED
-
parent、uncle染成 BLACK -
grand向上合并
染成RED，当做是新添加的节点进行处理
代码实现
普通二叉树代码
package com.njf;
import java.util.LinkedList;
import java.util.Queue;
import com.njf.BinaryTree.Node;
import njf.printer.BinaryTreeInfo;
@SuppressWarnings("unchecked")
public class BinaryTree<E> implements BinaryTreeInfo {
protected int size;
protected Node<E> root;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
root = null;
size = 0;
}
public void preorder(Visitor<E> visitor) {
if (visitor == null) return;
preorder(root, visitor);
}
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
visitor.stop = visitor.visit(node.element);
preorder(node.left, visitor);
preorder(node.right, visitor);
}
public void inorder(Visitor<E> visitor) {
if (visitor == null) return;
inorder(root, visitor);
}
private void inorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
inorder(node.left, visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
inorder(node.right, visitor);
}
public void postorder(Visitor<E> visitor) {
if (visitor == null) return;
postorder(root, visitor);
}
private void postorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
postorder(node.left, visitor);
postorder(node.right, visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
}
public void levelOrder(Visitor<E> visitor) {
if (root == null || visitor == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (visitor.visit(node.element)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
public boolean isComplete() {
if (root == null) return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf()) return false;
if (node.left != null) {
queue.offer(node.left);
} else if (node.right != null) {
return false;
}
if (node.right != null) {
queue.offer(node.right);
} else { // 后面遍历的节点都必须是叶子节点
leaf = true;
}
}
return true;
}
public int height() {
if (root == null) return 0;
// 树的高度
int height = 0;
// 存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) { // 意味着即将要访问下一层
levelSize = queue.size();
height++;
}
}
return height;
}
public int height2() {
return height(root);
}
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
protected Node<E> creatNode(E element, Node<E> parent) {
return new Node<>(element, parent);
}
protected Node<E> predecessor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中（left.right.right.right....）
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null
// node == node.parent.right
return node.parent;
}
protected Node<E> successor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中（right.left.left.left....）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
public static abstract class Visitor<E> {
boolean stop;
/**
* @return 如果返回true，就代表停止遍历
*/
abstract boolean visit(E element);
}
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;
}
}
/*****************************二叉树的打印***************/
@Override
public Object root() {
return root;
}
@Override
public Object left(Object node) {
return ((Node<E>)node).left;
}
@Override
public Object right(Object node) {
return ((Node<E>)node).right;
}
@Override
public Object string(Object node) {
return node;
}
}
相较于AVL树增加了获取兄弟结点的接口
public Node<E> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
二叉搜索树代码
package com.njf;
import java.util.Comparator;
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
private Comparator<E> comparator;
public BST() {
this(null);
}
public BST(Comparator<E> comparator) {
this.comparator = comparator;
}
public void add(E element) {
elementNotNullCheck(element);
// 添加第一个节点
if (root == null) {
root = creatNode(element, null);
size++;
// 新添加节点之后的处理
afterAdd(root);
return;
}
// 添加的不是第一个节点
// 找到父节点
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
do {
cmp = compare(element, node.element);
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
node.element = element;
return;
}
} while (node != null);
// 看看插入到父节点的哪个位置
Node<E> newNode = creatNode(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 新添加节点之后的处理
afterAdd(newNode);
}
/**
* 添加node之后的调整
* @param node 新添加的节点
*/
protected void afterAdd(Node<E> node) {}
/**
* remove node之后的调整
* @param node 移除节点
*/
protected void afterRemove(Node<E> node,Node<E> replacement) {}
public void remove(E element) {
remove(node(element));
}
public boolean contains(E element) {
return node(element) != null;
}
private void remove(Node<E> node) {
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<E> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
afterRemove(node,replacement);
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
afterRemove(node,null);
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
afterRemove(node,null);
}
}
private Node<E> node(E element) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
/**
* @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
*/
private int compare(E e1, E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>)e1).compareTo(e2);
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
}
RBTree
package com.njf;
import java.util.Comparator;
import com.njf.BinaryTree.Node;
public class RBTree<E> extends BST<E>{
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> grand = parent.parent;
// 叔父节点
Node<E> uncle = parent.sibling();
if (isRed(uncle)) {// 叔父节点是红色【B树节点上溢】
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点
afterAdd(red(grand));
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) {//L
if (node.isLeftChild()) {//LL
black(parent);
red(grand);
rotateRight(grand);
}else {//LR
black(node);
red(grand);
rotateLeft(parent);
rotateRight(grand);
}
}else {//R
if (node.isLeftChild()) {//RL
black(node);
red(grand);
rotateRight(parent);
rotateLeft(grand);
}else {//RR
black(parent);
red(grand);
rotateLeft(grand);
}
}
}
@Override
protected Node<E> creatNode(E element, Node<E> parent) {
return new RBNode<E>(element, parent);
}
/**
* 左旋转
* @param grand 高度最低的那个不平衡节点
*/
private void rotateLeft(Node<E> grand) {
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
//让parent成为这棵子树的根节点
afterRotate(grand, parent, child);
}
/**
* 右旋转
* @param grand 高度最低的那个不平衡节点
*/
private void rotateRight(Node<E> grand) {
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = parent.right;
parent.right = grand;
afterRotate(grand, parent, child);
}
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
//让parent成为这棵子树的根节点
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
}else if (grand.isRightChild()) {
grand.parent.right = parent;
}else {
root = parent;
}
//更新child的parent
if (child != null) {
child.parent = grand;
}
//更新grand的parent
grand.parent = parent;
//更新结点的高度
}
private Node<E> color(Node<E> node, boolean color) {
if (node == null) return null;
((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);
}
private Boolean colorOf(Node<E> node){
return node == null ? BLACK : ((RBNode<E>) node).color;
}
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
public static class RBNode<E> extends Node<E> {
public boolean color;
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();
}
}
}
代码调用
package com.njf;
import njf.printer.BinaryTrees;
public class Main {
static void test1() {
Integer data[] = new Integer[] {
67, 52, 92, 96, 53, 95, 13, 63, 34, 82, 76, 54, 9, 68, 39
};
RBTree<Integer> rb = new RBTree<>();
for (int i = 0; i < data.length; i++) {
rb.add(data[I]);
}
BinaryTrees.println(rb);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
test1();
}
}
结果如下:
┌─────────67─────────┐
│ │
┌─────52────┐ ┌─95─┐
│ │ │ │
┌─R_13─┐ ┌─54─┐ ┌─R_82─┐ 96
│ │ │ │ │ │
9 34─┐ R_53 R_63 ┌─76 92
│ │
R_39 R_68
删除结点（情况较复杂）
◼ B树中，最后真正被删除的元素都在叶子节点中
1. 删除 – RED节点
◼ 直接删除，不用作任何调整
2. 删除 – BLACK节点
◼ 有 3 种情况
1. 拥有 2 个 RED 子节点的 BLACK 节点
不可能被直接删除，因为会找它的子节点替代删除
因此不用考虑这种情况
2. 拥有 1 个 RED 子节点的 BLACK 节点
3. BLACK 叶子节点
2.1 删除 – 拥有1个RED子节点的BLACK节点
◼ 判定条件：用以替代的子节点是 RED
◼ 将替代的子节点染成 BLACK 即可保持红黑树性质
2.2 删除 – BLACK叶子节点 – sibling为BLACK
◼BLACK叶子节点被删除后，会导致B树节点下溢（比如删除88）
◼ 如果 sibling 至少有 1 个 RED 子节点
进行旋转操作
旋转之后的中心节点继承 parent 的颜色
旋转之后的左右节点染为 BLACK
2.3 删除 – BLACK叶子节点 – sibling为BLACK
◼ 判定条件：sibling没有 1 个 RED 子节点
◼ 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质
如果
parent 是 BLACK会导致
parent 也下溢这时只需要把
parent 当做被删除的节点处理即可
2.3 删除 – BLACK叶子节点 – sibling为RED
◼ 如果 sibling 是 RED
sibling 染成 BLACK，parent 染成 RED，进行旋转
于是又回到 sibling 是 BLACK 的情况
删除结点代码如下：
@Override
protected void afterRemove(Node<E> node, Node<E> replacement) {
// 如果删除的节点是红色
if (isRed(node)) return;
//用以取代删除节点的子节点是红色
if (isRed(replacement)) {
black(replacement);
return;
}
Node<E> parent = node.parent;
//删除的是根结点
if (parent == null) return;
// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) {// 被删除的节点在左边，兄弟节点在右边
if (isRed(sibling)) {//兄弟结点为红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
red(sibling);
black(parent);
if (parentBlack) {
afterRemove(parent, null);
}
}else {// 兄弟节点至少有1个红色子节点，向兄弟节点借元素
if (isBlack(sibling.right)) {
// 兄弟节点的左边是黑色，兄弟要先旋转
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(parent);
black(sibling.right);
rotateLeft(parent);
}
}else {// 被删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) {//兄弟结点为红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean isParentBlack = colorOf(parent);
red(sibling);
black(parent);
if (isParentBlack) {
afterRemove(parent, null);
}
}else {// 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(parent);
black(sibling);
rotateRight(parent);
}
}
}
代码调用
package com.njf;
import njf.printer.BinaryTrees;
public class Main {
static void test4() {
Integer data[] = new Integer[] {
55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50
};
RBTree<Integer> rb = new RBTree<>();
for (int i = 0; i < data.length; i++) {
rb.add(data[I]);
}
BinaryTrees.println(rb);
for (int i = 0; i < data.length; i++) {
rb.remove(data[I]);
System.out.println("---------------------------------------");
System.out.println("【" + data[i] + "】");
BinaryTrees.println(rb);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
test4();
}
}
删除结果打印如下：
┌────70───┐
│ │
┌─56─┐ ┌─87─┐
│ │ │ │
┌─R_22─┐ 62─┐ 74 ┌─96
│ │ │ │
20 ┌─55 R_68 R_90
│
R_50
---------------------------------------
【55】
┌────70───┐
│ │
┌─56─┐ ┌─87─┐
│ │ │ │
┌─R_22─┐ 62─┐ 74 ┌─96
│ │ │ │
20 50 R_68 R_90
---------------------------------------
【87】
┌────70───┐
│ │
┌─56─┐ ┌─90─┐
│ │ │ │
┌─R_22─┐ 62─┐ 74 96
│ │ │
20 50 R_68
---------------------------------------
【56】
┌───70──┐
│ │
┌─62─┐ ┌─90─┐
│ │ │ │
┌─R_22─┐ 68 74 96
│ │
20 50
---------------------------------------
【74】
┌───62───┐
│ │
┌─R_22─┐ ┌─70─┐
│ │ │ │
20 50 68 90─┐
│
R_96
---------------------------------------
【96】
┌───62───┐
│ │
┌─R_22─┐ ┌─70─┐
│ │ │ │
20 50 68 90
---------------------------------------
【22】
┌─62─┐
│ │
┌─50 ┌─70─┐
│ │ │
R_20 68 90
---------------------------------------
【62】
┌─50─┐
│ │
R_20 68─┐
│
70─┐
│
R_90
---------------------------------------
【20】
50─┐
│
68─┐
│
70─┐
│
R_90
---------------------------------------
【70】
50─┐
│
68─┐
│
90
---------------------------------------
【68】
50─┐
│
R_90
---------------------------------------
【90】
50
红黑树的平衡
◼ 最初遗留的困惑：为何那5条性质，就能保证红黑树是平衡的？
那5条性质，可以保证 红黑树 等价于 4阶B树
◼ 相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍
◼ 是一种弱平衡、黑高度平衡
◼ 红黑树的最大高度是
2 * log(n + 1) ，依然是 O(logn) 级别
AVL树 vs 红黑树
◼ AVL树
- 平衡标准比较严格：每个左右子树的高度差不超过
1 - 最大高度是
1.44 ∗ log( n +2) − 1.328（100W个节点，AVL树最大树高28） - 搜索、添加、删除都是
O(logn)复杂度，其中添加仅需O(1)次旋转调整、删除最多需要O(logn)次旋转调整
◼ 红黑树
- 平衡标准比较宽松：没有一条路径会大于其他路径的
2倍 - 最大高度是
2 ∗ log(n + 1)（100W个节点，红黑树最大树高40） - 搜索、添加、删除都是
O(logn)复杂度，其中添加、删除都仅需O(1)次旋转调整
◼ 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
◼ 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
◼ 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树
BST vs AVL Tree vs Re d Black Tree
例如：
10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 6 , 41, 37, 24, 96
BST
AVL
RB
