数据结构：红黑树（代码）

引言

本篇文章将从代码的角度完全分析红黑树的插入和删除过程，主要以文字的方式来论述，如果大家有不理解的地方，自己把图画一画，我觉得应该可以完全理解。

数据结构

插入的结点我们全部默认为红色，如果有其他的情况，可以重新赋值

struct RBTNode {
int data;
RBTNode* left;
RBTNode* right;
RBTNode* parent;
int color;
RBTNode(int value, RBTNode* parent, RBTNode* left, RBTNode* right) :
data(value), left(left), right(right), parent(parent), color(RED)
{}
};

using RBTNodePtr = RBTNode*;

RBTNodePtr CreateNode(int value, RBTNodePtr parent, RBTNodePtr left, RBTNodePtr right) {
RBTNodePtr node = new RBTNode(value, parent, left, right);
if(node == nullptr) {
return nullptr;
}
return node;
}

代码

插入操作

首先对于插入操作来说，如果这是一棵空树，那么我们插入的结点必须是黑色。

而如果对于一颗非空树，我们插入的先是按照二叉树的插入，先找到要插入的父节点和子节点，然后直接把我们创建的结点插入进去。

这里我们就需要考虑一下不同的情况了，如果父节点是黑色，那话好说，直接返回，因为插入的红节点不会影响这棵树的任何性质。但是，如果是一颗红节点，那么就直接影响到了两个红色结点不能在一起的原则，所以我们需要进行额外的讨论和调整

RBTNodePtr Insert(RBTNodePtr root, int value) {
// 空树插入
if(root == nullptr) {
RBTNodePtr newNode = CreateNode(value, nullptr, nullptr, nullptr);
newNode->color = BLACK;
return newNode;
}
// 非空树插入
// 1、执行二叉排序树的插入过程
RBTNodePtr p = root;
RBTNodePtr pre = nullptr;
while(p != nullptr) {
pre = p;
if(value < p->data) {
p = p->left;
} else {
p = p->right;
}
}
RBTNodePtr newNode = CreateNode(value, pre, nullptr, nullptr);
if(value < pre->data) {
pre->left = newNode;
} else {
pre->right = newNode;
}

// p的颜色是红色的，并且p有父节点pre pre是红色，会破坏不红红，需要调整
if(pre->color == RED) {
root = FixUp(root, newNode); // 传树和罪魁祸首newNode
}
return root;
}

对于调整操作，我们一般要涉及到三个结点，罪魁祸首z，父节点p，叔叔结点u和爷爷结点g 首先我们要确定各个节点的相对位置关系，我们就拿第一个情况举例子。

因为父节点是红色，那么爷爷结点一定是黑色

如果叔叔结点是红色的（这里我们要说一下，叔叔结点不存在和叔叔结点是黑色是同一种情况，因为红黑树里面结点的叶子颜色就是黑色的，也就是nullptr），这一种情况其实很好调整，相当于是两层红色挨在了一起，然后上面一层是黑色，那这不就是把中间那一层变成黑色，然后旁边两层是红色就可以了。

我们的思想永远都是先解决眼前的困难，再往长远看，所以我们这三层的问题就解决了，然后我们上一层变成了红色，也有可能影响到上面的情况，但这个不用担心，因为这不就是相当于插入了一个红节点嘛~~~那怎么办呢？我们这不是正在解决嘛~~~所以只需要加一个while循环就可以了，不过要注意的是，如果p是空了，就停止循环，因为到根节点了，再往上没节点了。但是但是，如果传到了根，说明根的颜色已经被改成了红色，那肯定不对，因为根的颜色必须是黑色，所以我们呢在最后几行代码交代了这种情况的处理方式，就是把根节点变成黑色。

回到主要话题上面，如果叔叔结点是黑色（注意一下，这个地方叔叔不存在，是叶子结点，因为如果存在，那么原来就不满足红黑树的性质黑路同），那么就有着这两种调整方式，这个也就是AVL树的左旋和右旋，但是实现方面又有所区别，因为多了一个父子对应的关系。

当这个操作结束之后，我们会发现，原来的g结点虽然变了样，但是黑高没有变，这个结点的颜色还是黑色，所以这个操作结束之后，我们就直接break~~~

RBTNodePtr FixUp(RBTNodePtr root, RBTNodePtr z) {
// 以root为根的树中，z及其父亲破坏了不红红，需要调整
RBTNodePtr p = z->parent;
RBTNodePtr g = nullptr; // 因为爷爷结点在向上调整的过程中可能会不存在，比如说p是根节点，所以先不赋值
RBTNodePtr u = nullptr; // 叔叔可能不存在，所以先不赋值
while(p != nullptr && p->color == RED) { // p是红色的，需要调整，p向上调整的过程中可能不存在，因为会到根节点
// 此时爷爷一定存在，因为p是红色的，所以p一定有爷爷
g = p->parent;
if(p == g->left) { // 确定叔叔的位置
u = g->right;
if(u != nullptr && u->color == RED) {
p->color = BLACK;
u->color = BLACK;
g->color = RED;
z = g; // z指向新的罪魁祸首，这个其实没有必要，只是有助于理解，我们之前需要这个是因为要得到这个结点的父亲，现在我们已经有了
p = g->parent;
} else { // 叔叔是黑色的 (LR,LL)
if(z == p->right) { // LR
root = Leftrotation(root, p);
root = Rightrotation(root, g);
g->color = RED;
z->color = BLACK;
} else { // LL
root = Rightrotation(root, g);
g->color = RED;
p->color = BLACK;
}
break; // 这个调整完就结束了，不需要再循环向上调整了
}
} else {
u = g->left;
if(u != nullptr && u->color == RED) {
p->color = BLACK;
u->color = BLACK;
g->color = RED;
z = g; // z指向新的罪魁祸首
p = g->parent;
} else { // 叔叔是黑色的 (RL,RR)
if(z == p->left) { // RL
root = Rightrotation(root, p);
root = Leftrotation(root, g);
g->color = RED;
z->color = BLACK;
} else { // RR
root = Leftrotation(root, g);
g->color = RED;
p->color = BLACK;
}
break;
}
}
}
/*
如果p就不存在了，就相当于在空树中插入了一个根节点，说明循环已经调整到根节点，把根节点设置为黑色即可
因为你在调整的过程之中把根节点改成了红色
*/
if(p == nullptr) {
root->color = BLACK;
}
return root;
}

我们常规的操作就不过多说了，就是对于父节点的调整要注意，因为我们结点边了之后，x结点的父亲就找不到了，所以我们用fx记录一下，然后还要保证fx不是空，如果fx是空的话，那就是根节点了，然后就是基本的父子对应关系（不仅仅是孩子要连父亲，父亲也要连接孩子）

RBTNodePtr Rightrotation(RBTNodePtr root, RBTNodePtr x) { // 这里要传根的主要原因就是因为我们可能涉及到根节点的父亲，因为这里与AVL树最大的不同就是要维护父亲
RBTNodePtr y = x->left;
RBTNodePtr fx = x->parent; // x的父亲，因为之后交换了就找不到了
x->left = y->right;
if(y->right != nullptr) { // 防止y->right不存在
y->right->parent = x;
}
y->right = x;
x->parent = y;
// 处理y和fx的关系 y的父亲会变成fx
y->parent = fx;
if(fx == nullptr) {
root = y;
} else {
// fx如果存在，其孩子由x变成了y
if(fx->left == x) { // 对于结点父亲的结点调整
fx->left = y;
} else {
fx->right = y;
}
}
return root;
}

RBTNodePtr Leftrotation(RBTNodePtr root, RBTNodePtr x) {
RBTNodePtr y = x->right;
RBTNodePtr fx = x->parent;
x->right = y->left;
if(y->left != nullptr) {
y->left->parent = x;
}
y->left = x;
x->parent = y;
y->parent = fx;
if(fx == nullptr) {
root = y;
} else {
if(fx->left == x) {
fx->left = y;
} else {
fx->right = y;
}
}
return root;
}

以上就是我们插入操作的代码！！！

删除操作

删除操作比插入操作要复杂很多很多。

首先我们用递归的方式写一个排序二叉树的查找代码

RBTNodePtr FindNode(RBTNodePtr root, int value) {
if(root == nullptr || root->data == value) {
return root;
}
if(value < root->data) {
return FindNode(root->left, value);
} else {
return FindNode(root->right, value);
}
}

首先我们的删除还是基于二叉树的删除操作，这一部分我们就不说了

最后转化为删除一个结点，而这个结点的孩子要么是一个要么没有，而我们把这个孩子记作x（有可能为空，nullptr，但是是黑色的），x的父节点记成y，也就是说我们要删除y结点。

删除y结点前我们必须要记录一下y的颜色，因为这个会直接导致我们之后的代码走向，然后就是一些平常的替换，不过要注意父指针的替换，最后在不管颜色的情况之下，我们删除了y，把x接到了p的下面

然后就是颜色的问题了。如果删除的y是红色，那没有任何的问题，因为什么性质都没有影响。

而如果是黑色，直接就影响到了黑高，还有其他的性质。所以我们需要继续之后的讨论。

RBTNodePtr Delete(RBTNodePtr root, int value) {
if(root == nullptr) {
std::cout << "删除失败，树为空" << std::endl;
return nullptr;
}

// 1、找到目标结点
RBTNodePtr y = FindNode(root, value);

// 判断目标结点是否存在
if(y == nullptr) {
std::cout << "删除失败，结点不存在" << std::endl;
return root;
}

// 2、判断y的度是不是2
if(y->left != nullptr && y->right != nullptr) {
RBTNodePtr p = y->right;
while(p->left != nullptr) {
p = p->left;
}
y->data = p->data;
// y的指针指向真正被free的结点
y = p;
}

// 无论一开始y的度是几，到此处，y的度一定是0或1
RBTNodePtr p = y->parent;
RBTNodePtr x = nullptr;
if(y->left != nullptr) {
x = y->left;
} else {
x = y->right; // x指向y的唯一孩子
}

// x顶替y的位置
if(x != nullptr) {
x->parent = p->parent;
}
// 如果p存在，x要成为p的孩子
if(p != nullptr) {
if(y == p->left) {
p->left = x;
} else {
p->right = x;
}
} else {
root = x;
}

int colorY = y->color;
delete y;
y = nullptr;

if(root == nullptr) {
return root; // 删除完之后，成为空树，不需要调整
}
// ================到目前为止完成了二叉排序树的删除过程===============
// 如果是红色，就不需要任何的调整
if(colorY == BLACK) {
root = DE_FixUp(root, x, p); // 删除操作中的调整
}

return root;
}

首先我们要注意我们的讨论顺序，这样子可以节省很多的代码。因为把问题B转化成问题A，也就是之后只用写问题A的代码，所以我们先写问题B，之后就不需要重新写一些无所谓的代码了。

RBTNodePtr DE_FixUp(RBTNodePtr root, RBTNodePtr x, RBTNodePtr p) { // 罪魁祸首x和父亲p
// x可能是空的 p也可能是空的
RBTNodePtr w = nullptr; // 删除y之后，w是x的兄弟结点

// x是黑色，并且x不是根节点
while(x != root && (x == nullptr || (x != nullptr && x->color == BLACK))) {
// 删除结点y是黑色，顶替y位置的x也是黑色，并且x并不是根节点
if(x == p->right) {
// x是右孩子，w是左孩子
w = p->left; // w一定不是空的
// w为红色
if(w->color == RED) {
root = Rightrotation(root, p);
w->color = BLACK;
p->color = RED;
w = p->left;
}
// 到此处，x的兄弟w一定是黑色的，转化为x的兄弟是黑色的情况
// w的两个孩子都是黑色的
if(w->left == nullptr || (w->left != nullptr && w->left->color == BLACK) &&
(w->right == nullptr || (w->right != nullptr && w->right->color == BLACK))) {
w->color = RED;
x = p; // p变成了新的调整地结点
p = x->parent; // 继续循环向上调整
} else {
RBTNodePtr red = nullptr;
// 至少有一个红色孩子red
// w的红色孩子是右孩子，red就是w的右孩子 LR
// 这里不可以直接判断右孩子是红色是因为如果左孩子也是红色，我们为了方便让左孩子当red，所以这里我们必须保证左孩子是黑色
if(w->left == nullptr || (w->left != nullptr && w->left->color == BLACK)) {
// LR
red = w->right;
root = Leftrotation(root, w);
w->color = RED;
red->color = BLACK;
RBTNodePtr t = w;
w = red;
red = t;
}
// 到此处，一定是LL情况
red = w->left;
w->color = p->color;
red->color = BLACK;
root = Rightrotation(root, p);
break;
}
} else {
w = p->right;
if(w->color == RED) {
root = Leftrotation(root, p);
w->color = BLACK;
p->color = RED;
w = p->right;
}
if(w->left == nullptr || (w->left != nullptr && w->left->color == BLACK) &&
(w->right == nullptr || (w->right != nullptr && w->right->color == BLACK))) {
w->color = RED;
x = p;
p = x->parent;
} else {
RBTNodePtr red = nullptr;
if(w->left == nullptr || (w->left != nullptr && w->left->color == BLACK)) {
// RL
red = w->right;
root = Rightrotation(root, w);
w->color = RED;
red->color = BLACK;
RBTNodePtr t = w;
w = red;
red = t;
}
// RR
red = w->left;
w->color = p->color;
red->color = BLACK;
root = Leftrotation(root, p);
break;
}
}
}

// x是红色
if(x != nullptr && x->color == RED) {
x->color = BLACK;
}
return root;
}

总结

本篇文章就到这里结束了！！！红黑树的代码确实很不好写，需要写代码的时候配合着图来解决代码的问题，所以也希望大家多多努力~~~~