红黑树
- 红黑树的基本操作
- 插入操作
- 删除操作
- 搜索操作
- 完整实现
红黑树（Red-Black Trees）是另一种平衡二叉搜索树，具有两种颜色的节点：红色和黑色。它是一种自平衡二叉搜索树，利用这些颜色在插入和删除操作期间维护平衡因子。因此，在红黑树操作期间，内存使用 1 bit 的存储空间来容纳每个节点颜色信息。
在红黑树（也称为 RB trees）中，为节点分配颜色时需要遵循不同的条件。
根节点始终为黑色。
不能有两个相邻的红色节点。
树中的每条路径（从根节点到叶节点）必须包含相同数量的黑色节点。
尽管 AVL 树比 RB 树更加平衡，AVL 树的平衡算法比 RB 树的更严格，但通过 RB 树可以更高效地进行多次快速的插入和删除操作。
图：红黑树
红黑树的基本操作
红黑树的操作包括通常在二叉搜索树上执行的所有基本操作。RB 树的一些基本操作包括：
插入
删除
搜索
插入操作
红黑树的插入操作遵循二叉搜索树的相同插入算法。元素按照二叉搜索属性插入，此外，节点被着色为红色和黑色，以根据红黑树属性平衡树。
按照以下步骤插入元素到红黑树中，同时维护二叉搜索树和红黑树属性。
情况 1 − 检查树是否为空；如果为空，则将当前节点设为根节点并将其着色为黑色。
情况 2 − 但如果树不为空，我们创建一个新节点并将其着色为红色。在此，我们面临两种不同的情况 −
如果新节点的父节点是黑色节点，则退出操作，树保持不变。
如果新节点的父节点是红色，且父节点的兄弟节点颜色为黑色或不存在，则应用合适的旋转并相应重新着色。
如果新节点的父节点是红色，且父节点的兄弟节点颜色为红色，则将父节点、兄弟节点和祖父节点重新着色为黑色。只有当祖父节点不是根节点时才重新着色祖父节点；如果它是根节点，则只重新着色父节点和兄弟节点。
示例
让我们为前 7 个整数构建一棵 RB 树，以详细理解插入操作 −
树被检查为空，因此第一个添加的节点是根节点并被着色为黑色。
现在，树不为空，因此我们创建一个新节点并添加下一个整数，颜色为红色，
节点没有违反二叉搜索树和 RB 树属性，因此我们继续添加另一个节点。
树不为空；我们为下一个整数创建一个新的红色节点并添加。但新节点的父节点不是黑色节点，
此时树违反了二叉搜索树和 RB 树属性；由于父节点的兄弟节点为 NULL，我们应用合适的旋转并重新着色节点。
现在 RB 树属性已恢复，我们向树中添加另一个节点 −
树再次违反了 RB 树平衡属性，因此我们检查父节点的兄弟节点颜色，此例中为红色，因此我们只需重新着色父节点和兄弟节点。
接下来插入元素 5，这使得树再次违反 RB 树平衡属性。
由于兄弟节点为 NULL，我们应用合适的旋转并重新着色。
现在，我们插入元素 6，但 RB 树属性被违反，需要应用插入情况之一 −
父节点的兄弟节点为红色，因此我们重新着色父节点、父节点的兄弟节点和祖父节点，因为祖父节点不是根节点。
现在，我们添加最后一个元素 7，但这个新节点的父节点是红色。
由于父节点的兄弟节点为 NULL，我们应用合适的旋转（RR 旋转）
最终的 RB 树已构建完成。
删除操作
红黑树上的删除操作必须以这样的方式执行，即必须恢复二叉搜索树和红黑树的所有性质。按照以下步骤在红黑树上执行删除操作 −
首先，我们基于二叉搜索树的性质进行删除。
情况 1 − 如果要删除的节点或该节点的父节点是红色的，直接删除它。
情况 2 − 如果节点是双黑色的，直接移除双黑色（双黑色发生在要删除的节点是黑色叶子节点时，因为它会累加视为黑色节点的 NULL 节点）
情况 3 − 如果双黑色的兄弟节点也是黑色节点且其子节点也是黑色的，按照以下步骤操作 −
移除双黑色
将父节点重新着色为黑色（如果父节点是红色节点，则变为黑色；如果父节点已经是黑色节点，则变为双黑色）
将父节点的兄弟节点重新着色为红色
如果双黑色节点仍然存在，则应用其他情况。
情况 4 − 如果双黑色的兄弟节点是红色的，我们执行以下步骤 −
交换父节点和父节点兄弟节点的颜色。
向双黑色的方向旋转父节点
重新应用其他适用的情况。
情况 5 − 如果双黑色的兄弟节点是黑色节点，但兄弟节点最靠近双黑色的子节点是红色的，按照以下步骤操作 −
交换双黑色兄弟节点和该兄弟节点相关子节点的颜色
向双黑色的反方向旋转兄弟节点（即如果双黑色是右子节点，则应用左旋转，反之亦然）
应用情况 6。
情况 6 − 如果双黑色的兄弟节点是黑色节点，但兄弟节点远离双黑色的子节点是红色的，按照以下步骤操作 −
交换双黑色父节点和兄弟节点的颜色
向双黑色的方向旋转父节点（即如果双黑色是右子节点，则应用右旋转，反之亦然）
移除双黑色
将红色子节点颜色改为黑色。
示例
考虑上述构建的相同的红黑树，让我们从树中删除几个元素。
从树中删除元素 4、5、3。
要删除元素 4，我们首先执行二叉搜索删除。
执行二叉搜索删除后，红黑树性质未被破坏，因此树保持原样。
然后，我们使用二叉搜索删除删除元素 5
但是执行二叉搜索删除后违反了红黑树性质，即树中所有路径不具有相同数量的黑色节点；因此我们交换颜色以平衡树。
然后，我们从获得树中删除节点 3 −
应用二叉搜索删除，我们正常删除叶子节点 3。而且由于 3 是黑色节点，我们得到一个双黑色节点。
我们应用情况 3 删除，因为双黑色的兄弟节点是黑色且其子节点也是黑色。这里，我们移除双黑色，重新着色双黑色的父节点和兄弟节点。
所有所需的节点已被删除，并且红黑树性质得到维护。
搜索操作
红黑树中的搜索操作遵循与二叉搜索树相同的算法。遍历树并将每个节点与要搜索的关键元素进行比较；如果找到则返回成功搜索。否则，返回不成功搜索。
完整实现
以下是各种编程语言中 Red Black Tree 的完整实现 −
// C++ Red Black Tree 算法程序
#include <iostream>
using namespace std;
struct Node {
int data;
Node *parent;
Node *left;
Node *right;
int color;
};
typedef Node *NodePtr;
class RedBlackTree {
private:
NodePtr root;
NodePtr TNULL;
void initializeNULLNode(NodePtr node, NodePtr parent) {
node->data = 0;
node->parent = parent;
node->left = nullptr;
node->right = nullptr;
node->color = 0;
}
// 前序遍历
void preOrderHelper(NodePtr node) {
if (node != TNULL) {
cout << node->data << " ";
preOrderHelper(node->left);
preOrderHelper(node->right);
}
}
// 中序遍历
void inOrderHelper(NodePtr node) {
if (node != TNULL) {
inOrderHelper(node->left);
cout << node->data << " ";
inOrderHelper(node->right);
}
}
// 后序遍历
void postOrderHelper(NodePtr node) {
if (node != TNULL) {
postOrderHelper(node->left);
postOrderHelper(node->right);
cout << node->data << " ";
}
}
NodePtr searchTreeHelper(NodePtr node, int key) {
if (node == TNULL || key == node->data) {
return node;
}
if (key < node->data) {
return searchTreeHelper(node->left, key);
}
return searchTreeHelper(node->right, key);
}
// 删除后平衡树
void deleteFix(NodePtr x) {
NodePtr s;
while (x != root && x->color == 0) {
if (x == x->parent->left) {
s = x->parent->right;
if (s->color == 1) {
s->color = 0;
x->parent->color = 1;
leftRotate(x->parent);
s = x->parent->right;
}
if (s->left->color == 0 && s->right->color == 0) {
s->color = 1;
x = x->parent;
} else {
if (s->right->color == 0) {
s->left->color = 0;
s->color = 1;
rightRotate(s);
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = 0;
s->right->color = 0;
leftRotate(x->parent);
x = root;
}
} else {
s = x->parent->left;
if (s->color == 1) {
s->color = 0;
x->parent->color = 1;
rightRotate(x->parent);
s = x->parent->left;
}
if (s->right->color == 0 && s->right->color == 0) {
s->color = 1;
x = x->parent;
} else {
if (s->left->color == 0) {
s->right->color = 0;
s->color = 1;
leftRotate(s);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = 0;
s->left->color = 0;
rightRotate(x->parent);
x = root;
}
}
}
x->color = 0;
}
void rbTransplant(NodePtr u, NodePtr v) {
if (u->parent == nullptr) {
root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
v->parent = u->parent;
}
void deleteNodeHelper(NodePtr node, int key) {
NodePtr z = TNULL;
NodePtr x, y;
while (node != TNULL) {
if (node->data