红黑树（R-B Tree），它是二叉树中，最经典也是最复杂的数据结构。也是一种常见的自平衡二分搜索树。说到自平衡就涉及到旋转，这是红黑树最难的地方之一。我在一开始接触时也是云里雾里，不知道为什么红黑树相比普通的二叉树要设置这么多条件，更别说红黑树的翻转过程了，随着工作和学习的加深逐渐多了一些理解，故此记录一下。红黑树的应用场景非常广泛，特别是一些高性能的底层实现中：
- 广泛应用于 C++ 的 STL 中， map 和 set 是用红黑树实现的；
- Linux 的进程调度，使用红黑树管理进程控制块，进程的虚拟内存空间都存储在一颗红黑树上，每个虚拟内存空间都对应红黑树的一个结点，左指针指向相邻的虚拟内存空间，右指针指向相邻的高地址虚拟内存空间；
- IO 多路复用的 epoll 采用红黑树组织管理 sockfd，以支持快速的增删改查；
- Nginx 中采用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
- Java 中的 TreeMap 和 TreeSet 也是采用红黑树实现；JDK8开始，HashMap 也新增了红黑树，链表与红黑树可以互转；
红黑树的特性
- 每个节点或者是黑色，或者是红色；
- 根节点是黑色；
- 每个叶子节点（NIL）是黑色； 【注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！】
- 如果一个节点是红色的，则它的子节点必须是黑色的；
- 从任意一个节点到叶子节点，经过的黑色节点是一样的（所谓的黑平衡）
这些特性不用死记，它们的目的只有一个，就是保证红黑树的平衡。因为只有平衡的树效率才最稳定。而为了保证红黑树的平衡，在插入和删除节点时，就比普通的二叉树要复杂的多
- 插入节点时，可能违反规定，从而需要递归来【旋转+重新着色】；
- 删除节点时，与插入节点类似的调整，只是在调整前，需要先找到一个后继节点来替换；
旋转
红黑树的节点定义如下，与AVL不同，红黑树的平衡因子通过颜色来维护，而不是高度，因此其成员变量中需要一个color，初始化默认为红色：为了简化思考，这里我们只关注旋转，先不管着色
public class RBTree {
private TreeNode root;
public RBTree(TreeNode root) {
this.root = root;
}
public static class TreeNode {
public static final int BLACK = 0;
public static final int RED = 1;
public int value;
public int color = BLACK;
public TreeNode parent;
public TreeNode left;
public TreeNode right;
public TreeNode(int value) {
this.value = value;
}
public TreeNode(int value, TreeNode parent) {
this.value = value;
this.parent = parent;
}
}
}假设有如下一颗红黑树
这是一个已经平衡的红黑树，下面旋转操作都是基于这颗树：
左旋是基于某个节点，整体（该节点连同其左、右子树）向左旋转；
右旋是基于某个节点，整体（该节点连同其左、右子树）向右旋转；
左旋
对于左旋，我的理解是把这颗树想象成一串用绳子串起来的玻璃珠，每个珠子上有数字。当我拎起20这颗珠子时，展现的结构如上图，需要左旋时，我就拎起数字为10这颗珠子，这时20这颗珠子就会往下沉。但此时10这颗珠子下挂着3颗珠子，不满足红黑树的性质，因此需要调整，把16这颗珠子下沉到20上。最后过程如下图
代码实现：
public class RBTree {
private TreeNode root;
/*****************************************************************************************************************
* (1) | (2)
* g(10) u(20) | g g
* / \ / \ | / /
* p(5) u(20) => g(10) z(22) | p => u
* / \ / \ / \ | \ /
* c(2) x(8) y(16) z(22) p(5) y(16) | u p
* / \ |
* c(2) x(8) |
* |
*****************************************************************************************************************/
public void rotateLeft(TreeNode parent) {
TreeNode right = parent.right; // u
//【右子左节点】挂到【父的右节点】
parent.right = right.left; // g.右节点 = y
if (right.left != null) {
right.left.parent = parent; // y.父节点 = g
}
// 【祖父】与【左子 or 右子】
right.parent = parent.parent; // u.父节点 = g.父节点
if (parent.parent != null) {
if (parent.parent.left == parent) {
parent.parent.left = right; // 祖父节点.左节点 = u
} else {
parent.parent.right = right;
}
} else {
root = right;
}
// 【父】与【右子】替换
parent.parent = right; // g.父节点 = u
right.left = parent; // u.左节点 = g
}
}右旋
右旋和左旋的思路差不多
代码实现如下
public class RBTree {
private TreeNode root;
/*****************************************************************************************************************
* (1) | (2)
* g(10) p(5) | p g
* / \ / \ | / / \
* p(5) u(20) => c(2) g(10) | g => x p
* / \ / \ / \ | /
* c(2) x(8) y(16) z(22) x(8) u(20) | x
* / \ |
* y(16) z(22) |
* |
*****************************************************************************************************************/
private void rotateRight(TreeNode parent) {
TreeNode left = parent.left; // p
// 【左子右节点】挂到【父的左节点】
parent.left = left.right; // g.左节点 = x
if (left.right != null) {
left.right.parent = parent; // x.父节点 = g
}
// 【祖父】与【左子 or 右子】
left.parent = parent.parent; // p.父节点 = g.父节点
if (parent.parent != null) {
if (parent.parent.left == parent) {
parent.parent.left = left;
} else {
parent.parent.right = left;
}
} else {
root = left;
}
// 【父】与【左子】替换
parent.parent = left; // g.父节点 = p
left.right = parent; // p.右节点 = g
}
}时机
红黑树翻转的过程理解了，另一个问题是，我怎么知道什么时候需要翻转呢？这就是红黑树与其他AVL不同的地方，一般首先想到的是通过树的高度来判断是否需要翻转，但红黑树既然有红黑两种节点，就可用通过这个属性来快速判断,，判断逻辑如下
/**
* 保持（黑）平衡并翻转颜色
*
* @return
*/
public Node<K, V> refresh() {
Node<K, V> self = this;
// 左子树为红，表示不为空，无需判空
if (isRed(self.left) && isRed(self.left.left)) {
self = self.rightRotate();
}
if (!isRed(self.left) && isRed(self.right)) {
self = self.leftRotate();
}
if (isRed(self.left) && isRed(self.right)) {
self.flipColor();
}
return self;
}
