前言
原来只是在从应用以及简单的思想理解方面给大家介绍了红黑树的创建与使用。这段时间就想要深入研究一下红黑树，主要参考了维基百科内容，加上自己的一些理解与学习，尝试真正的实现这一数据结构。今天小泉就带大家手撸一下红黑树吧！废话不多说，我们的红黑树之旅即将启程。
定义
老规矩，还是要跟大家说一下红黑树的定义，下面来看一下红黑树在维基百科上的介绍。
维基百科
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在O(log n)时间内完成查找、插入和删除，这里的n是树中元素的数目。
性质：
- 节点只有红色或者黑色
- 根节点一定是黑色
- 叶子节点一定是黑色空节点（NULL节点）
- 红色节点的左右子节点均为黑色节点
- 任一节点到其叶子节点上的黑色节点数目一致
红黑树的五点性质是重中之重，一定要在后面过程中牢记。
算法启程
下面小泉要带着各位小伙伴开始我们的红黑树之旅，坐好，坐好，发车了。
那么第一站就是我们的节点首先介绍一下，我们红黑树的基础细节操作。
红黑树的节点
节点属性
根据红黑树的性质，我们知晓红黑树的节点至少要有属性：存储值，左、右子节点、节点颜色、父节点。
从这一点看来，好像也只是比一般二叉树多了一个颜色，除此之外，我们知道二叉树最讨厌的就是记录节点之前的节点（比如某一节点的父节点、叔叔节点等等），因此为了达到高效的目的，红黑树的节点还包含了5\. 父节点。
- 存储值
- 左子节点
- 右子节点
- 节点颜色
- 父节点
寻找相关节点
- 寻找祖父节点
- 寻找叔节点
- 寻找兄弟节点
这一波操作其实很容易理解，主要还是为了各种“旋转”操作作准备的，即旋转过程中必定会牵扯到三代“人”（节点）的事情。所以这三个寻找相关节点的操作是有必要的。
后续为了简洁描述，节点命名如下：
当前节点 N，父节点P，祖父节点GP，叔节点U，兄弟节点S，空节点NIL（注意不是空NULL）。
代码——节点
class Node{
public Node parent = null;
public Node left = null, right = null;
public int val = 0;
public COLOR color = COLOR.RED;
public Node(){
}
public Node(Node parent, Node left, Node right, int val) {
this.parent = parent;
this.left = left;
this.right = right;
this.val = val;
}
Node grandParent() {
if (parent == null){
return null;
} else {
return parent.parent;
}
}
Node uncle() {
if (parent == grandParent().left) {
return grandParent().right;
} else {
return grandParent().left;
}
}
Node sibling() {
if (this == parent.left) {
return parent.right;
} else {
return parent.left;
}
}
}
第一种左旋
左旋：N节点上浮，P节点下沉，N节点的左子树变做P节点的右子树，P节点则成为N节点的左子节点。然后N成为GP节点的左子节点（或者右子节点）。
这里只给出初始状态P是GP左子节点的情况，右子树也是一样的，不再赘述。
第一种右旋
右旋：N节点上浮，P节点下沉，N节点的右子树变做P节点的左子树，P节点则成为N节点的右子节点。然后N成为GP节点的左子节点（或者右子节点）。
这里同样给出初始状态P是GP左子节点的情况，右子树不再赘述。
上述左右旋是以最深节点为基准N，其次还有一种以上述中间P节点作为N节点进行旋转。这样的好处是不需要引入祖父节点（因为每次都需要调用函数去寻找）。
第二种左旋
左旋：NR（N的右子节点）节点上浮，N节点下沉，NR节点的右子树变做N节点的左子树，N节点则成为NR节点的右子节点。然后NR成为P节点的左子节点（或者右子节点）。
这里同给出初始状态N是P左子节点的情况，右子树不再赘述。
第二种右旋
右旋：NL节点上浮，N节点下沉，NL节点的右子树变做N节点的左子树，N节点则成为NL节点的右子节点。然后NL成为P节点的左子节点（或者右子节点）。
这里也是给出初始状态N是P左子节点的情况。
关于左旋右旋，小泉的原则都以最深节点作为基准节点 N，即第一种左右旋。
代码——旋转
public void rotate_right(Node n) {
Node gp = n.grandParent();
Node p = n.parent;
p.left = n.right;
if (n.right != NIL) {
n.right.parent = p;
}
n.right = p;
p.parent = n;
if (root == p) {
root = n;
}
n.parent = gp;
if (gp != null) {
if (gp.left == n.parent) {
gp.left = n;
} else {
gp.right = n;
}
}
}
public void rotate_left(Node n) {
Node gp = n.grandParent();
Node p = n.parent;
p.right = n.left;
if (n.left != NIL) {
n.left.parent = p;
}
n.left = p;
p.parent = n;
if (root == p) {
root = n;
}
n.parent = gp;
if (gp != null) {
if (gp.left == n.parent) {
gp.left = n;
} else {
gp.right = n;
}
}
}
红黑树的创建
介绍完红黑树的基础操作之后，我们就继续发车来到红黑树的创建。
一个数据结构，我们主要从三方面的效率来衡量它：查询、插入、删除。同样这三方面也是创建数据结构的三个不可避免的操作。
查询
查询过程其实相对是简单的，就是按照二叉搜索树的规则进行时间复杂度O(logn)进行查询即可。查询操作不是我们的主要关注点。
下面插入、删除操作就需要考虑到最后树的结构是否还符合红黑树的五个性质，然后进行相应的树结构调整。
坐稳了，要加速咯！
插入
- 为了保证性质5（任一节点到叶子节点路径中黑色节点个数相同），因此默认插入的节点都是红色节点。
- 插入节点替代的是NIL节点，后续在进行树结构的调整。（这样就可以简化我们的插入情形的分类，不需要考虑自身子节点的问题）
两点插入规则十分重要，并且注意后续情形均是插入后再调整树结构，否则对于情形的分类你会感到迷惑。
由浅入深，插入操作分了很多种情况，我们从最简单的入手。
情形1. 插入的新节点N在根节点位置
插入根节点位置，左右子节点赋为NIL节点，父节点为空。
由于新节点均是红色，而根据性质一，根节点颜色必是黑色，因此还需要进行一个变色操作即可结束插入操作。
情形2. 插入新节点N，其父节点P为黑色
插入在黑色P节点之后，由于插入的节点为红色节点，因此在这种情况下，插入操作没有破坏任何一个性质，结束。
情形3. 插入的新节点N，其父节点P为红色，叔节点U也为红色
对于插入的N节点，如果它的P节点与U节点均是红色节点，N节点也为红色，那么违背了性质4，又因为U节点也为红色，那么此时将GP节点变成红色，P、U节点变色为黑色这样可使得树结构符合性质4并且路径黑色节点数均保持一致即也没有违背性质5。
但是这样就会引入问题，GP的父节点可能是红色或者GP为根节点，那么此时又需要对GP节点进行插入调整操作（相当于插入一个红色新节点）。
情形4. 插入新节点N，其父节点P为红色，叔节点U为黑色，P为GP左(右)子节点，N为P右(左)子节点
对于情形4，我们先做一个左(右)旋，将位置调整为上述位置，然后进入到情形5一并处理。此时性质5依然满足，只是不满足性质4。
情形5. 插入新节点N，其父节点P为红色，叔节点U为黑色，P为GP左(右)子节点，N为P左(右)子节点
对于情形5，我们先对P进行一个右旋，使得P上浮，GP下沉，这样会使得旋转后的P的左右两边黑色节点数不相同（由于黑色GP节点下沉，因此旋转后P左子树到达叶子节点比右子树到达叶子节点会少经过一个黑色），所以再进行变色操作，P变色为黑色，GP变色为红色即可满足性质4，5。
至此，插入操作就讲解完毕了，从最简单的插入根节点，到根据父节点、叔节点颜色进行分情形讨论已经涵盖了所有情况。 下面就要全速前进了，系好安全带，相对更为复杂的删除操作即将开始。
代码——插入
private void insert(Node n, int data) {
if (n.val >= data) {
if (n.left != NIL)
insert(n.left, data);
else {
Node tmp = new Node();
tmp.val = data;
tmp.left = tmp.right = NIL;
tmp.parent = n;
n.left = tmp;
insertAdjust(tmp);
}
} else {
if (n.right != NIL)
insert(n.right, data);
else {
Node tmp = new Node();
tmp.val = data;
tmp.left = tmp.right = NIL;
tmp.parent = n;
n.right = tmp;
insertAdjust(tmp);
}
}
}
private void insertAdjust(Node n) {
//情形1： 插入点为根结点
if (n.parent == null){
root = n;
n.color = COLOR.BLACK;
return;
}
//情形2： 父节点是黑色，插入红色节点不会有影响
if (n.parent.color == COLOR.RED) {
//情形3：父亲节点是红色，叔节点是红色====》变色
if (n.uncle().color == COLOR.RED) {//
n.grandParent().color = COLOR.RED;
n.parent.color = n.uncle().color = COLOR.BLACK;
insertAdjust(n.grandParent());
} else {
//情形4：父节点红色，叔节黑色。父节点是左子树，该节点是右子树 ====》先左旋，进入到情形5
if (n.parent.right == n && n.grandParent().left == n.parent) {
rotate_left(n);
insertAdjust(n.left);
} else if (n.parent.left == n && n.grandParent().right == n.parent) {
//情形4：父节点红色，叔节点黑色。父节点是右子树，该节点是左子树 ====》先右旋，进行到情形5
rotate_right(n);
insertAdjust(n.right);
}else if (n.parent.left == n && n.grandParent().right == n.parent) {
//情形5：父节点红色，叔节点黑色。父节点是左子树，该节点是左子树 ====》变色，然后右旋
n.grandParent().color = COLOR.RED;
n.parent.color = COLOR.BLACK;
rotate_right(n.parent);
} else {
n.grandParent().color = COLOR.RED;
n.parent.color = COLOR.BLACK;
rotate_left(n.parent);
}
}
}
}
删除
对于删除操作，红黑树采取了一种小技巧，如果要删除某个节点，就需要将该节点左子树中最大值或者右子树中最小值替换到该节点，然后删除用来替换的节点，即该节点相当于被转移到了只有一个孩子（子节点为空节点NIL的也可以认为只有1个孩子节点）的节点上。
在本文，小泉采用的是右子树的最小值。
ok，那么我们就知道了，最后都转化为了处理只有单孩子节点的节点即可。因此后文讨论的大多是删除之后，应当如何根据原右子树最小值位置来调整树的结构。
如图，X存储值就是我们要删除的值（前期替换值工作已经做好），N节点则是这一X节点的子节点，因此我们删除X，N会顶替X的位置，后续讲解也都是基于这样的先决条件。
那么当删除的节点是黑色，依然从简到繁分几种情形进行讨论。
情形1. 删除节点X是根节点
删除根就很简单了，不需要什么额外的操作，上面的替换顶替工作已经完成了。
情形2. 删除节点X是黑色，其子节点N为红色
这里直接将子节点颜色变成黑色即可满足五点性质。
情形3. 删除节点X后，X子节点N，N的S节点为红色，且N为父节点P的左（右）子节点
先进行一个左旋操作，使得S成为N新的GP节点，然后P节点颜色变红，S节点颜色变黑，这样从S到达各个叶子节点的黑色节点数量一致。
但是现在依然存在问题，从P到叶子节点路径有数量不一致情况，即P-X-N现在是P-N，即少一个黑色节点。到这一步，情形继续往下推，放到下面的情形去解决即可。
情形4. 删除节点X后，X子节点N的P节点、S节点、SL节点、SR节点为黑色，且N为父节点P的左（右）子节点
对于这一情况，由于P-N路径其余路径少一个黑色节点，那么将S节点变色为红色，就可以使得经过P的到达的路径之间黑色节点相同。
但是经过P与不经过P之间的黑色节点却依然相差1，因此要对P节点进行调整结构。
情形5. 删除节点X后，P节点为红色，S节点、SL节点、SR节点为黑色，且N为父节点P的左（右）子节点
对于这种情况，我们直接选择变色，P节点变成黑色，填补N路径上缺少的X黑色节点，S节点变成红色与P节点进行互补。
情形6. 删除节点X后，S节点为黑色，SL节点为红色，SR节点为黑色，且N为父节点P的左（右）子节点
这种情况，我们通过右旋，然后然后将SL与S的颜色对换，使得该情况向情形6进行。
情形7. 删除节点X后，S节点、SL节点为黑色，SR节点为红色，且N为父节点P的左（右）子节点
情形7情况下，直接左旋S，将SR变色，然后P节点下沉变色，S节点保持与原P节点颜色一致。这样经过原P节点路径的黑色节点填补充足，右子树黑色节点数没有改变，维持性质5。
至此，我们的红黑的构建就告于段落，文章尽可能列全了所有插入与删除操作，并还原其过程，有些根据前文红黑树的基本操作加上图片就比较好理解，因此没有过多的解释，对于插入与删除操作，我们多考虑第四、第五点性质然后变色+旋转多数都可以解决。
代码——删除
private Node getSmallestChild(Node n) {
if (n.left== NIL) {
return n;
}
return getSmallestChild(n.left);
}
private boolean delete(Node n, int data) {
if (n.val > data) {
if(n.left == NIL) {
return false;
}
return delete(n.left, data);
} else if (n.val < data) {
if (n.right == NIL) {
return false;
}
return delete(n.right, data);
} else if (n.val == data){
if (n.right == NIL) {
deleteOneChild(n);
return true;
}
Node smallest = getSmallestChild(n.right);
int tmp = n.val;
n.val = smallest.val;
smallest.val = tmp;
deleteOneChild(smallest);
return true;
} else {
return false;
}
}
private void deleteOneChild(Node n) {
Node child = n.left == NIL ? n.right:n.left;//n节点只有一个子树
if (n.parent == null && n.left == NIL && n.right == NIL) {
//情形1：删除根节点，且无左右子节点；
n = null;
root = n;
return;
}
if (n.parent == null) {
//情形1：删除根节点，且有左子节点或者右子节点（但只有一个子节点）。
child.parent = null;
root = child;
root.color = COLOR.BLACK;
return;
}
//删除节点X
if(n.parent.left == n) {
n.parent.left = child;
} else {
n.parent.right = child;
}
child.parent = n.parent;
if(n.color == COLOR.BLACK) {
// 被删除节点X是红色，其实不需要其他操作，如果是黑色，那么意味着通过该节点到叶子节点的路径会少一个黑色节点
if (child.color == COLOR.RED) {
//情形2：被删除节点X是黑色节点，且其子节点是红色节点，那么子节点变黑即可。
child.color = COLOR.BLACK;
} else {
//调整树结构
deleteAdjust(child);
}
}
}
private void deleteAdjust(Node n){
if (n.parent == null) {
n.color = COLOR.BLACK;
return;
}
//情形3：删除节点X后其子节点N是黑色节点，那么看其兄弟节点S的颜色
//如果是红色，那么可以先旋转，然后再变色，S变黑，P变红，N依然是P的子节点。
// 但是这样之后，从P开始，经过N与没有经过N到叶子节点的路径还是会相差一个节点（我们删除的节点） P-X-N =》 P-N
//进入到后续情形
if (n.sibling().color == COLOR.RED){
n.parent.color = COLOR.RED;
n.sibling().color = COLOR.BLACK;
if (n == n.parent.left) {
rotate_left(n.sibling());
} else {
rotate_right(n.sibling());
}
}
//情形4：删除节点X后其子节点N是黑色节点，父节点和兄弟节点S及S的子节点的颜色都是黑的,变色完，再对n的父节点进行调整
if (n.parent.color == COLOR.BLACK && n.sibling().color == COLOR.BLACK
&& n.sibling().left.color == COLOR.BLACK && n.sibling().right.color == COLOR.BLACK) {
n.sibling().color = COLOR.RED;
deleteAdjust(n.parent);
} else if (n.parent.color == COLOR.RED && n.sibling().color == COLOR.BLACK
&& n.sibling().left.color == COLOR.BLACK && n.sibling().right.color == COLOR.BLACK){
//情形5：删除节点X后其子节点N是黑色节点，父节点为红色，兄弟节点S及S的子节点的颜色都是黑的,那么改变P和S颜色即可，补足P-N路径中的黑色节点。
n.sibling().color = COLOR.RED;
n.parent.color = COLOR.BLACK;
} else {
if (n.sibling().color == COLOR.BLACK) {
//情形6：N为P的左子节点，S节点的左子节点为红色，右子节点为黑色，那么变色+左旋，然后进入到情形7
if (n == n.parent.left && n.sibling().left.color == COLOR.RED && n.sibling().right.color == COLOR.BLACK) {
n.sibling().color = COLOR.RED;
n.sibling().left.color = COLOR.BLACK;
rotate_left(n.sibling().left);
} else if (n == n.parent.right && n.sibling().right.color == COLOR.RED && n.sibling().left.color == COLOR.BLACK) {
n.sibling().color = COLOR.RED;
n.sibling().right.color = COLOR.BLACK;
rotate_left(n.sibling().right);
}
}
//情形7：N为P的左子节点，S节点的左子节点为黑色，右子节点为红色，那么右旋+变色
n.sibling().color = n.parent.color;
n.parent.color = COLOR.BLACK;
if (n == n.parent.left) {
n.sibling().right.color = COLOR.BLACK;
rotate_left(n.sibling());
} else {
n.sibling().left.color = COLOR.BLACK;
rotate_right(n.sibling());
}
}
}
写在最后
大家看完有什么不懂的可以在下方留言讨论.
谢谢你的观看。
觉得文章对你有帮助的话记得关注我点个赞支持一下！
作者：涓涓清泉
链接：https://juejin.cn/post/6920321931229003789
网友评论