红黑树
定义
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
- 如果一个节点是红色的，则它的子节点必须是黑色的。
-
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
红黑树的应用
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
红黑树的自平衡
当我们对红黑树进行插入或者删除的时候，为了保证红黑树能够保持特点4（如果一个节点是红色的，则它的子节点必须是黑色的）和特点5（从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点），在每次进行操作的时候，都会做平衡操作，这些平衡操作就是红黑树的左旋和右旋
左旋
当对节点x进行左旋时，有三个步骤
- 将x的右子树指向y的左子树
- 将x的父节点改成y的父节点
- 将y的左子树指向x
//具体代码
private void rotateLeft(Tree p) {
if (p != null) {
//先保存一份y
Tree r = p.right;
//将x的右子树指向y的左子树
p.right = r.left;
if (r.left != null)
r.left.parent = p;
//将x的父节点改成y的父节点
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
//将y的左子树指向x
r.left = p;
p.parent = r;
}
}
右旋
右旋的原理基本和左旋相同，明白了左旋，右旋也就不难理解了，具体也是3个步骤
- 将y的左子树指向x的右子树
- 将y的父节点改成x的父节点
- 将x的右子树指向y
//具体代码
private void rotateRight(Tree p) {
if (p != null) {
//保存一份x(即y的左子树)
Tree l = p.left;
//将y左子树指向x的右子树
p.left = l.right;
if (l.right != null) l.right.parent = p;
//将y的父节点改成x的父节点
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
//将x的右子树指向y
l.right = p;
p.parent = l;
}
}
在了解了红黑树的自平衡操作之后，我们就可以对红黑树进行增删了
插入结点
如何在红黑树中插入一个节点呢？
- 首先，我们需要按照二叉查找树的方式插入一个节点，因为红黑树本身就是二叉查找树，所以我们插入节点之后它依旧是一课二叉查找树
- 根据插入的不同情况进行后续操作
2.1.1 情况一：插入节点是根节点，直接标黑无需调整
2.1.2 情况二，插入节点的父节点是黑节点，直接标红无需调整
2.1.2 情况三：插入节点的父节点是红节点，将插入节点标为红色并进行自平衡调整
插入调整
在进行插入调整时又分为几种情况，让我们从简单到复杂一一说明
情况一：叔叔节点是黑色
这种情况下，又分为两种情况
-
插入为左节点
-
插入为右节点
因为插入为右节点时，可以直接通过右旋p节点变为情况一，所以也可以总结为一种情况
这种情况下，插入节点的父节点为红节点，叔叔节点为黑节点，那么祖父节点（G节点）一定是黑节点，所以我们对祖父节点进行右旋，然后将它标红，再将父节点标黑，就完成平衡了
这样做的原因很好理解，插入的节点是红节点，插入节点的父节点也是红节点，这样就违背了定义4（如果一个节点是红色的，则它的子节点必须是黑色的），但是又不能直接将插入节点改为黑节点（因为要满足定义5：从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点），所以我们就以祖父节点为根节点进行调整，调整之前和调整之后祖父节点这条线上的黑色节点总数没变，所以调整完祖父节点就完成平衡了
情况二：叔叔节点为红节点
这种情况稍微比情况一复杂，具体分为几个步骤
- 将插入节点的父节点和叔叔节点标位黑色
- 将插入节点的祖父节点标位红色
- 以插入节点的祖父节点为新的插入节点，然后循环步骤1到步骤3，如果这个过程中出现了情况一，就按照情况一的处理方式进行处理
//具体代码可以参考java中TreeMap的写法
private void fixAfterInsertion(Entry<K,V> x) {
//先将插入节点标位红节点
x.color = RED;
//如果插入节点不是根节点，并且插入节点的父节点是红色
while (x != null && x != root && x.parent.color == RED) {
//parentOf(x)是表示x的父节点
//如果x的父节点是祖父节点的左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//保存x祖父节点的右节点为y（即y是x的叔叔节点）
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果叔叔节点是红色
if (colorOf(y) == RED) {
//将x的父节点和叔叔节点都设置为黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
//将x的祖父节点设置为红色
setColor(parentOf(parentOf(x)), RED);
//将x的祖父节点作为新的插入节点进行平衡调整
x = parentOf(parentOf(x));
} else {
//如果叔叔节点是黑色
if (x == rightOf(parentOf(x))) {
//如果x是父节点的右节点，那么对x父节点进行左旋（情况一的子情况2）
x = parentOf(x);
rotateLeft(x);
//经过这两行代码的处理，子情况2则变成了子情况1
}
//将x的父节点设为黑色，x的祖父节点设为红色，对x的祖父节点进行右旋（情况一的子情况1）
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
//如果x的父节点是祖父节点的右节点
//保存x祖父节点的左节点为y（即y是x的叔叔节点）
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//如果叔叔节点是红色
if (colorOf(y) == RED) {
//将x的父节点和叔叔节点都设置为黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
//将x的祖父节点设置为红色
setColor(parentOf(parentOf(x)), RED);
//将x的祖父节点作为新的插入节点进行平衡调整
x = parentOf(parentOf(x));
} else {
//如果叔叔节点是黑色
if (x == leftOf(parentOf(x))) {
//如果x是父节点的左节点，那么对x父节点进行右旋（情况一的子情况2的镜像情况）
x = parentOf(x);
rotateRight(x);
}
//将x的父节点设为黑色，x的祖父节点设为红色，对x的祖父节点进行右旋（情况一的子情况1的镜像情况）
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
