红黑树
一、前言
红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。考虑到红黑树是一种被广泛应用的数据结构，所以我们很有必要去弄懂它。
二、红黑树数据结构
红黑树是一棵二叉树， 有五大特征：
特征一： 节点要么是红色，要么是黑色（红黑树名字由来）。 特征二： 根节点是黑色的 特征三： 每个叶节点(nil或空节点)是黑色的。 特征四： 每个红色节点的两个子节点都是黑色的（相连的两个节点不能都是红色的）。 特征五： 从任一个节点到其每个叶子节点的所有路径都是包含相同数量的黑色节点。
三、红黑树代码实现
对于BST树和AVL树相比，红黑树在树节点的定义上又多了颜色特性，而且红黑树再创建新节点时，默认颜色是红色的，树节点代码结构如下：
package com.tree;
public class TreeNode<K, V> {
TreeNode<K, V> parent;
TreeNode<K, V> left;
TreeNode<K, V> right;
K key;
V value;
boolean color;
public TreeNode(K key, V value) {
this.key = key;
this.value = value;
this.color = true;
}
}
1.左旋与右旋
红黑树的左旋与右旋与AVL树的左旋与右旋是一样的，具体操作可以参考AVL树
2. 红黑树的插入
红黑树的节点插入和BST、AVL树的插入流程基本一致，不同的是红黑树完成节点插入后，需要从添加节点开始通过旋转、变色等操作维持红黑树的性质不变。
2.1 被调整节点是根节点
假设被调整节点为N，这种情况下，我们把 节点 N 的颜色由红色变为黑色 ，性质2（根是黑色）被满足。同时 N 被染成黑色后，红黑树所有路径上的黑色节点数量增加一个，性质5（ 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点 ）仍然被满足。
java实现代码如下：
// case1: 若当前节点为根节点,则不用走到下面的逻辑,直接将根节点的颜色赋值为黑色即可
if (node == root) {
root.color = BLACK;
return;
}
2.2 被调整节点的的父节点是黑色
假设N 的父节点是黑色，这种情况下， 性质4（每个红色节点必须有两个黑色的子节点）和性质5没有受到影响，不需要调整 。
java实现代码如下：
// case2: 若当前节点的父节点为黑色,则不用走到下面的逻辑,直接将根节点的颜色赋值为黑色即可
if (isBLACK(node.parent)) {
root.color = BLACK;
return;
}
2.3 被调整节点的父节点和叔叔节点都是红色
假设N 的父节点是红色（节点 P 为红色，其父节点必然为黑色），叔叔节点 U 也是红色。由于 P 和 N 均为红色，所以性质4被打破，此时需要进行调整。这种情况下， 先将 P 和 U 的颜色染成黑色，再将 G 的颜色染成红色 。此时经过 G 的路径上的黑色节点数量不变，性质5仍然满足。 但需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整 。
java实现代码如下：
if (isRED(uncle)) {
parent.color = BLACK;
uncle.color = BLACK;
grandParent.color = RED;
insertFixUp(grandParent);
}
2.4 被调整节点的父节点是红色，叔叔节点是黑色
2.4.1 左左
假设N 的父节点为红色，叔叔节点为黑色。 N 是 P 的左孩子，且节点 P 是 G 的左孩子 。 此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色 。经过这样的调整后，性质4被恢复，同时也未破坏性质5。
java实现代码如下：
if (parent == grandParent.left && node == parent.left) {
// 左左
parent.color = BLACK;
grandParent.color = RED;
rotateRight(grandParent);
}
2.4.2 左右
假设N 的父节点为红色，叔叔节点为黑色。 节点 N 是 P 的右孩子，且节点 P 是 G 的左孩子 。 此时先对节点 P 进行左旋，调整完之后，我们发现就将"左右"这个情况转化成了左左的情况 。进而继续使用左左的方法继续调整。
java实现代码如下：
if (parent == grandParent.left && node == parent.right) {
// 左右
rotateLeft(parent);
node.color = BLACK;
grandParent.color = RED;
rotateRight(grandParent);
}
2.4.3 右右
N 的父节点为红色，叔叔节点为黑色。 N 是 P 的右孩子，且节点 P 是 G 的右孩子 。 此时对 G 进行左旋，调整 P 和 G 的位置，并互换颜色 。经过这样的调整后，性质4被恢复，同时也未破坏性质5。
java实现代码如下：
if (parent == grandParent.right && node == parent.right) {
// 右右
parent.color = BLACK;
grandParent.color = RED;
rotateLeft(grandParent);
}
2.4.4 右左
N 的父节点为红色，叔叔节点为黑色。 节点 N 是 P 的左孩子，且节点 P 是 G 的右孩子 。 此时先对节点 P 进行右旋，调整完之后，我们发现就将"右左"这个情况转化成了右右的情况 。进而继续使用右右的方法继续调整。
java实现代码如下：
if (parent == grandParent.right && node == parent.left) {
// 右左
rotateRight(parent);
node.color = BLACK;
grandParent.color = RED;
rotateLeft(grandParent);
}
3. 红黑树的删除
红黑树的删除和BST树以及AVL树也基本一致，区别在于红黑树删除节点后，需要调整从被删除节点开始通过旋转和变色等操作维持红黑树的性质不变。接下来以被调整节点是父亲节点的左子树位例讲述，如果被调整节点是父亲节点的右子树和左子树形成轴对称，其变换原理类似。
3.1被调整节点是根节点或者是红色
若被调整节点是根节点，直接将颜色设置成黑色返回即可
java实现代码如下：
if (node == root || isRED(node)) {
node.color = BLACK;
return;
}
3.2 被调整节点是黑色，兄弟节点是红色
互换兄弟节点与父亲节点的颜色，并以父亲节点为轴进行左旋，并以当前节点继续递归调整红黑树( 这里的父亲节点可能是红色，调整后会违反性质4，此时需要继续递归进行调整 )。
java实现代码如下：
if (isRED(brother)) {
brother.color = BLACK;
parent.color = RED;
if (node == parent.left) {
rotateLeft(parent);
} else if (node == parent.right) {
rotateRight(parent);
}
deleteFixUp(node);
return;
}
#### 3.3 被调整节点是黑色，兄弟节点是黑色
若被调整的节点是黑色，则根据红黑树的性质5可知，其兄弟节点一定存在。此时根据兄弟节点孩子节点的颜色情况的不同，进行不同的调整； 若当前节点是父亲节点的右孩子则对称处理 。
3.3.1 兄弟节点的两个孩子节点都是黑色
此时将兄弟节点设置为黑色( 可能的情况是兄弟节点没有孩子，也有可能是兄弟节点两个孩子都是黑色 )，并以父亲节点继续递归调整红黑树。
java实现代码如下：
if (isBLACK(brother.left) && isBLACK(brother.right)) {
brother.color = RED;
deleteFixUp(parent);
return;
}
3.3.2 兄弟节点有一个孩子节点是红色
此时根据被调整节点是父亲的左孩子还是右孩子判断是需要左旋变色还是要右旋变色。
java实现代码如下：
// 当前节点是其父节点的左孩子
if (node == parent.left) {
if (isRED(brother.left)) {
brother.left.color = BLACK;
brother.color = RED;
rotateRight(brother);
// 注意这里在兄弟节点旋转后,兄弟节点变换成父节点的右节点了
brother = parent.right;
}
brother.color = parent.color;
parent.color = BLACK;
brother.right.color = BLACK;
rotateLeft(parent);
return;
}
if (node == node.parent.right) {
if (isRED(brother.right)) {
brother.right.color = BLACK;
brother.color = RED;
rotateLeft(brother);
// 注意这里在兄弟节点旋转后,兄弟节点变换成父节点的左节点了
brother = parent.left;
}
brother.color = parent.color;
parent.color = BLACK;
brother.left.color = BLACK;
rotateRight(node.parent);
return;
}
四、红黑叔完整代码
package com.tree;
/ **
* 红黑树实现，该实现核心逻辑由 TreeMap 源码修改而来
*/
public class RedBlackTree<K extends Comparable<K>, V> {
private final static boolean RED = true;
private final static boolean BLACK = false;
public TreeNode<K, V> root;
/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-. / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
private void rotateLeft(TreeNode<K, V> x) {
// 设置x的右孩子为y
TreeNode<K, V> y = x.right;
// 将 “y的左孩子” 设为 “x的右孩子”
// 如果y的左孩子不为空的话，将 “y的左孩子的父亲” 设为 “x”
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
// 将"y的父亲" 从 "x" 修改为 "x的父亲"
y.parent = x.parent;
// 如果 “x的父亲” 是空节点，则将 y 设为根节点
if (x.parent == null) {
this.root = y;
} else {
// 如果 x 是它父节点的左孩子，则将 y 设为 “x的父节点的左孩子”
if (x.parent.left == x) {
x.parent.left = y;
}
// 如果 x 是它父节点的左孩子，则将 y 设为 “x的父节点的左孩子”
if (x.parent.right == x) {
x.parent.right = y;
}
}
// 将 “x” 设为 “y的左孩子”
y.left = x;
// 将 “x的父节点” 设为 “y”
x.parent = y;
}
/*
* 对红黑树的节点(y)进行右旋转
*
* 右旋示意图(对节点y进行右旋)：
* py py
* / /
* y x
* / \ --(右旋)-. / \
* x ry lx y
* / \ / \
* lx rx rx ry
*
*/
private void rotateRight(TreeNode<K, V> y) {
// 设置x是当前节点的左孩子。
TreeNode<K, V> x = y.left;
// 将 “x的右孩子” 设为 “y的左孩子”
// 如果"x的右孩子"不为空的话，将 “x的右孩子的父亲” 设为 “y”
y.left = x.right;
if (x.right != null) {
x.right.parent = y;
}
// 将 “x的父亲” 从 "y" 修改为 “y的父亲”
x.parent = y.parent;
// 如果 “y的父亲” 是空节点，则将x设为根节点
if (y.parent == null) {
this.root = x;
} else {
// 如果 y 是它父节点的右孩子，则将 x 设为“y的父节点的右孩子”
if (y == y.parent.right) {
y.parent.right = x;
}
// 如果 y 是它父节点的左孩子，将x设为“x的父节点的左孩子”
if (y == y.parent.left) {
y.parent.left = x;
}
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
public void put(K key, V value) {
insert(key, value);
}
public void insert(K key, V value) {
if (root == null) {
root = new TreeNode(key, value);
root.color = BLACK;
return;
}
// 1. 索引出待插入元素位置，也就是插入到哪个父元素下
TreeNode<K, V> parent = root;
TreeNode<K, V> search = root;
while (search != null) {
parent = search;
if (key.compareTo(search.key) == 0) {
search.value = value;
return;
}
search = key.compareTo(search.key) < 0 ? search.left : search.right;
}
// 2. 创建节点并将节点设置为红色
TreeNode<K, V> node = new TreeNode(key, value);
if (key.compareTo(parent.key) < 0) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;
// 3. 将树重新修正为一颗红黑树
insertFixUp(node);
}
public void insertFixUp(TreeNode<K, V> node) {
if (node == null) {
return;
}
// case1: 若当前节点为根节点,则不用走到下面的逻辑,直接将根节点的颜色赋值为黑色即可
if (node == root) {
root.color = BLACK;
return;
}
// case2: 若当前节点的父节点为黑色,则不用走到下面的逻辑,直接将根节点的颜色赋值为黑色即可
if (isBLACK(node.parent)) {
root.color = BLACK;
return;
}
if (isRED(node.parent)) {
// 如果当前节点的父亲节点是红色,则一定存在祖父节点,且祖父节点一定是黑色
TreeNode<K, V> parent = node.parent;
TreeNode<K, V> grandParent = parent.parent;
TreeNode<K, V> uncle = parent == grandParent.left ? grandParent.right : grandParent.left;
// case3: 插入的节点的父节点是红色,且叔叔节点是红色
if (isRED(uncle)) {
parent.color = BLACK;
uncle.color = BLACK;
grandParent.color = RED;
insertFixUp(grandParent);
} else if (isBLACK(uncle)) { // case4: 插入的节点的父节点是黑色,且叔叔节点是黑色
if (parent == grandParent.left && node == parent.left) {
// 左左
parent.color = BLACK;
grandParent.color = RED;
rotateRight(grandParent);
} else if (parent == grandParent.left && node == parent.right) {
// 左右
rotateLeft(parent);
node.color = BLACK;
grandParent.color = RED;
rotateRight(grandParent);
} else if (parent == grandParent.right && node == parent.right) {
// 右右
parent.color = BLACK;
grandParent.color = RED;
rotateLeft(grandParent);
} else if (parent == grandParent.right && node == parent.left) {
// 右左
rotateRight(parent);
node.color = BLACK;
grandParent.color = RED;
rotateLeft(grandParent);
}
}
}
root.color = BLACK;
}
public V get(K key) {
TreeNode<K, V> treeNode = search(key);
return treeNode == null ? null : treeNode.value;
}
public TreeNode<K, V> search(K key) {
if (key == null) {
return null;
}
TreeNode<K, V> search = root;
while (search != null) {
if (key.compareTo(search.key) == 0) {
return search;
}
search = key.compareTo(search.key) < 0 ? search.left : search.right;
}
return null;
}
public void remove(K key) {
// 检索待删除节点
TreeNode<K, V> search = search(key);
if (search == null) {
return;
}
delete(search);
}
public void delete(TreeNode<K, V> node) {
// 待删除节点是叶子节点
if (node.left == null && node.right == null) {
// 恢复红黑树的性质
deleteFixUp(node);
if (node == root) {
root = null;
return;
}
if (node == node.parent.left) {
node.parent.left = null;
}
if (node == node.parent.right) {
node.parent.right = null;
}
node.left = null;
node.right = null;
node.parent = null;
return;
}
if (node.left != null && node.right != null) {
TreeNode<K, V> successor = node.right;
while (successor.left != null) {
successor = successor.left;
}
node.key = successor.key;
node.value = successor.value;
delete(successor);
return;
}
TreeNode<K, V> deleteNode = node.left == null ? node.right : node.left;
node.key = deleteNode.key;
node.value = deleteNode.value;
delete(deleteNode);
}
private void deleteFixUp(TreeNode<K, V> node) {
if (node == root || isRED(node)) {
node.color = BLACK;
return;
}
TreeNode<K, V> parent = node.parent;
TreeNode<K, V> brother = (node == node.parent.left) ? parent.right : parent.left;
// 兄弟节点是红色的
if (isRED(brother)) {
brother.color = BLACK;
parent.color = RED;
if (node == parent.left) {
rotateLeft(parent);
} else if (node == parent.right) {
rotateRight(parent);
}
deleteFixUp(node);
return;
}
if (isBLACK(brother.left) && isBLACK(brother.right)) {
brother.color = RED;
deleteFixUp(parent);
return;
}
// 当前节点是其父节点的左孩子
if (node == parent.left) {
if (isRED(brother.left)) {
brother.left.color = BLACK;
brother.color = RED;
rotateRight(brother);
// 注意这里在兄弟节点旋转后,兄弟节点变换成父节点的右节点了
brother = parent.right;
}
brother.color = parent.color;
parent.color = BLACK;
brother.right.color = BLACK;
rotateLeft(parent);
return;
}
if (node == node.parent.right) {
if (isRED(brother.right)) {
brother.right.color = BLACK;
brother.color = RED;
rotateLeft(brother);
// 注意这里在兄弟节点旋转后,兄弟节点变换成父节点的左节点了
brother = parent.left;
}
brother.color = parent.color;
parent.color = BLACK;
brother.left.color = BLACK;
rotateRight(node.parent);
return;
}
}
public boolean isRED(TreeNode<K, V> node) {
return node != null && node.color == RED;
}
public boolean isBLACK(TreeNode<K, V> node) {
return node == null || node.color == BLACK;
}
}