🦆哒哒哒 ~ 亚亚鸭来啦~
🌙最近，由于我刷算法题发现红黑树涉及的知识点比较杂乱，网上找不到对新手友好的文章（我看的都快怀疑人生了呜呜呜），因此自己在各类网站以及教科书搜集了一些信息，总结出了该文章。
⭐如有错误请在评论区指点一下或私信我，新手请多多关照O(∩_∩)O
文章目录
前言
跟着亚亚鸭的脚步慢慢去深入理解红黑树吧！
我们先来看一下红黑树的定义。
红黑树是一种自平衡二叉查找树。
再来看一下平衡二叉查找树的定义。
平衡二叉搜索树是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（红黑树就是平衡二叉搜索树的一种，AVL树是最先发明的自平衡二叉查找树，所以下面我们会一起学习一下AVL树）
再再来看一下二叉搜索树的定义。
二叉查找树（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
Ⅰ、二叉搜索树
1.性质
1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树。
2.结点属性
一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为NULL。
3.复杂度
若含有n个元素，则复杂度为O(logn)。
4.算法解析与实现
查找
通过递归查找是否存在key。
二叉搜索树的查找思路：
①如果要查找的值等于当前结点的值，那么，就找到了；
②如果要查找的值小于当前结点的值，那么，就往当前结点的左子树走；
③如果要查找的值大于当前结点的值，那么，就往当前结点的右子树走；
最终，如果走到空了还没有找到，就说明不存在这个key。
下面是C++伪代码：
//递归查找key结点
Node* bstree_search(BSTree root, int key){
if (root==NULL||root->key==key)
return root;
if(key<root->key)
return bstree_search(root->left,key);
else
return bstree_search(root->right,key);
}
插入
思路和查找一样的，只是我们这次要进行的是插入操作，那么我们还需要一个parent结点，来时刻记录当前结点的父结点即：
①如果要插入的值等于当前结点的值，那么，无法插入（不可出现重复的key）；
②如果要插入的值小于当前结点的值，那么，就往当前结点的左子树走；
③如果要插入的值大于当前结点的值，那么，就往当前结点的右子树走；
最终，如果走到空了，就说明不存在重复的key，只要往双亲节点的后面插就好了，就是合适的位置，具体往左边还是右边插入，需要比较待插入节点的key和parent的key。
下面是C++伪代码：
// 二叉查找树的插入操作
void bstree_insert(node* root, int val) {
if (root == null) { //如果是空树直接插入
root->key = val;
}
node valNode; //定义一个要插入的结点valNode
valNode->key=val;
node cur=root; //cur为当前遍历结点
node parent=null; //parent为cur的父结点
while(true){
if (cur == null) { //在遍历过程中，找到了合适的位置，就指针插入（没有重复节点）
if (parent->key < val) {
parent->right = valNode;
} else {
parent->left = valNode;
}
return;
}
if (val < cur->key) {
parent = cur;
cur = cur->left;
} else if (val > cur->key) {
parent = cur;
cur = cur->right;
} else {
cout<<("插入失败，已经存在key");
}
}
}
删除
①叶子结点直接删；
②仅仅仅有左或右子树的结点：结点删除后，子承父业，直接上移；
③左右子树都有的结点：找到该结点p的直接前驱或者直接后继s来代替p，然后删除结点s。（直观点这个s就是p的右子树中值最小的那个结点，将s取出填补p的位置，如图：）
具体操作：
首先，需要先找到是否存在key节点，如果存在，则删除，如果不存在则删除错误。
对于，如果存在，则分为三种情况：
①要删除的节点，没有左孩子
Ⅰ：要删除的节点为根节点：root = delete.right;
Ⅱ：要删除的节点为其双亲节点的左孩子：parent.left = delete.right;
Ⅲ：要删除的节点为其双亲节点的右孩子：parent.right = delete.right;
②要删除的节点，没有右孩子
Ⅰ：要删除的节点为根节点：root = delete.left;
Ⅱ：要删除的节点为其双亲节点的左孩子：parent.left = delete.left;
Ⅲ：要删除的节点为其双亲节点的右孩子：parent.right = delete.left;
③要删除的节点，既有左孩子又有右孩子：
此时我们需要找到整颗二叉树中第一个大于待删除节点的节点，然后替换他俩的值，最后，把找到的节点删除
Ⅰ：找到的节点的双亲节点为待删除的节点：delete.key = find.key; findParent.right = find.right;
Ⅱ：找到的节点的双亲节点不是待删除的节点：delete.key = find.key; findParent.left = find.right;
/**
* 删除树中节点
*
* 思路如下：
*/
void bstree_remove(node* root, int val) {
if (root == null) {
cout<<("为空树，删除错误！")<<endl;
}
node cur = root;
node parent = null;
//查找是否存在val节点的位置
while (cur != null) {
if (val < cur->key) {
parent = cur;
cur = cur->left;
} else if (val > cur->key) {
parent = cur;
cur = cur->right;
} else {
break;
}
}
if (cur == null) {
cout<<("找不到key，输入key不合法")<<endl;
}
//此时的cur为待删除的节点
//parent 为待删除的节点的父节点
/*
* 情况1：如果待删除的节点没有左孩子
* 其中
* ①待删除的节点有右孩子
* ②待删除的节点没有右孩子
* 两种情况可以合并
*/
if (cur->left == null) {
if (cur == root) { //①如果要删除的是根节点
root = cur->right;
} else if (cur == parent->left) { //②如果要删除的是其父节点的左孩子
parent->left = cur->right;
} else { //③如果要删除的节点为其父节点的右孩子
parent>right = cur->right;
}
}
/*
* 情况2:如果待删除的节点没有右孩子
*
* 其中:待删除的节点必定存在左孩子
*/
else if (cur->right == null) { //①如果要删除的是根节点
if (cur == root) {
root = cur->left;
} else if (cur == parent->left) { //②如果要删除的是其父节点的左孩子
parent->left = cur->left;
} else { //③如果要删除的节点为其父节点的右孩子
parent->right = cur->left;
}
}
/*
* 情况3:如果待删除的节点既有左孩子又有右孩子
*
* 思路:
* 因为是排序二叉树,要找到整颗二叉树第一个大于该节点的节点,只需要,先向右走一步,然后一路往最左走就可以找到了
* 因此:
* ①先向右走一步
* ②不断向左走
* ③找到第一个大于待删除的节点的节点,将该节点的值,替换到待删除的节点
* ④删除找到的这个节点
* ⑤完成删除
*
*/
else {
node nextParent = cur; //定义父节点,初始化就是待删除的节点
node next = cur->right; //定义next为当前走到的节点,最终目的是找到第一个大于待删除的节点
while (next->left != null) {
nextParent = next;
next = next->left;
}
cur->key = next->key; //找到之后,完成值的替换
if (nextParent == cur) { //此时的父节点就是待删除的节点,那么说明找到的节点为父节点的右孩子(因为此时next只走了一步)
nextParent->right = next->right;
} else { //此时父节点不是待删除的节点,即next确实往左走了,且走到了头.
nextParent->left = next->right;
}
}
}
Ⅱ、平衡二叉查找树
1.介绍
平衡二叉搜索树是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。它能在O(log n)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。
常见的平衡二叉搜索树有：
①AVL树
②红黑树
③Treap
④节点大小平衡树
Ⅲ、AVL树
我们来学习一下平衡搜索二叉树的起源AVL树吧！学完这个，红黑树想看懂就不在话下啦~
二叉搜索树在某些情况下会出现极度不平衡，其树形结构便退化成了链表，查找效率也会下降。于是出现了 AVL 树，AVL 树保证了二叉搜索树的平衡，引入了平衡监督机制，也就是在插入结点时，树中某一部分不平衡度超过一个阈值后将出发平衡调整操作，这样便保证了树的平衡度在可接受的范围内，最大的好处就是提高了搜索的效率。
1.定义
在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
2.性质
AVL树本质上还是一棵二叉搜索树，它的特点是：
①本身首先是一棵二叉搜索树。
②带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
如下图就是一棵平衡二叉树，任何节点的两个子树的高度最大差别为1：
而下图不是平衡二叉树，因为结点3的两颗子树高度相差为2：
3.复杂度
AVL 树的查找、插入和删除在平均和最坏情况下均为 O(logn)。
4.算法解析与实现
失衡
在 AVL 树中进行插入或删除节点后，可能导致 AVL 树失去平衡。这种失衡可以概括为4种情况：
（1）LL 失衡：LeftLeft，也称为“左左”。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致“根的左子树的高度”比“根的右子树的高度”大 2，导致 AVL 树失去了平衡。如下图：
（2)LR 失衡：LeftRight，也称为“左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致“根的左子树的高度”比“根的右子树的高度”大 2，导致 AVL 树失去了平衡。如下图：
（3）RL 失衡：RightLeft，称为“右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致“根的右子树的高度”比“根的左子树的高度”大 2，导致 AVL 树失去了平衡。如下图：
（4）RR 失衡：RightRight，称为“右右”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致“根的右子树的高度”比“根的左子树的高度”大 2，导致 AVL 树失去了平衡。如下图：
旋转
如果在 AVL 树种插入或删除节点后，使得高度之差大于 1。此时，AVL 树的平衡状态就被破坏，不再是平衡二叉树，为了维持一个平衡状态，需要对失衡的树进行旋转处理。
（1）LL旋转：LL 失衡的情况，可以通过一次左旋转将 AVL 树恢复平衡，如下图：
下面是C++伪代码：
AVLTreeNode<T> *leftLeftRotation(AVLTreeNode<T> *&k2)
{
AVLTreeNode<T> *k1 = k2->m_leftChild;
k2->m_leftChild = k1->m_rightNode;
k1->m_rightNode = k2;
k2->m_height = std::max(height(k2->m_leftChild), height(k2->m_rightNode)) + 1;
k1->m_height = std::max(height(k1->m_leftChild), k2->m_height) + 1;
return k1;
}
（2）RR旋转：
下面是C++伪代码：
AVLTreeNode<T> *rightRightRotation(AVLTreeNode<T> *&k1)
{
AVLTreeNode<T> *k2 = k1->m_rightNode;
k1->m_rightNode = k2->m_leftChild;
k2->m_leftChild = k1;
k1->m_height = std::max(height(k1->m_leftChild), height(k1->m_rightNode)) + 1;
k2->m_height = std::max(height(k2->m_rightNode), k1->m_height) + 1;
return k2;
}
（3）LR旋转：第一次旋转是围绕 k1 进行的 RR 旋转，第二次旋转是围绕 k3 进行的 LL 旋转。
下面是C++伪代码：
AVLTreeNode<T> *leftRightRotation(AVLTreeNode<T> *&k3)
{
k3->m_leftChild = rightRightRotation(k3->m_leftChild);
return leftLeftRotation(k3);
}
（4）RL旋转：第一次旋转是围绕 k3 进行的 LL 旋转，第二次是围绕 k1 进行的 RR 旋转。
下面是C++伪代码：
AVLTreeNode<T> *rightLeftRotation(AVLTreeNode<T> *&k1)
{
k1->m_rightNode = leftLeftRotation(k1->m_rightNode);
return rightRightRotation(k1);
}
Ⅳ、红黑树
👏看完上面的内容，恭喜你成功一半啦！你真的很棒！下面就是我们最复杂的红黑树啦(●ˇ∀ˇ●)~
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
1.起源
红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。
2.性质
红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 [3] 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
① 结点是红色或黑色。
② 根结点是黑色。
③ 所有叶子都是黑色。（叶子是NIL结点）
④ 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
⑤ 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
3.算法解析
插入
o 如果插入前是空树，那么新元素将成为根结点，根结点必须染成黑色；
o 如果插入前树非空，若新结点被染成黑色，将违反红黑树的特性，所有从根到外部结点的路径上的黑色结点个数不等。因此，新插入的结点将染成红色，但这又可能违反红黑树的特性，出现连续两个红色结点，因此需要重新平衡。
设新插入的结点为u，它的父结点和祖父结点分别是pu和gu。
若pu是黑色结点，再插入红色结点，则特性没有破坏，结束重新平衡的过程。
若pu是红色结点，则出现连续两个红色结点的情形，这时还要考查pu的兄弟结点。
情况1：如果pu的兄弟结点gr是红色结点，此时结点pu的父结点gu是黑色结点，它有两个红色子女结点。交换结点gu和它的子女结点的颜色。
情况2：如果pu的兄弟结点gr是黑色结点，此时又有两种情况。
（1）u是pu的左子女，pu是gu的左子女。在这种情况下只要对pu做一次右单旋转，交换pu和gu的颜色，就可恢复红黑树的特性，并结束重新平衡过程。
（2）u是pu的右子女，pu是gu的左子女。在这种情况下对pu做先左后右的双旋转，再交换u与gu的颜色，就可恢复红黑树的特性，结束重新平衡过程。
当结点u是pu的右子女的情形与u是pu的左子女的情形是镜像的，只要左右指针互换即可。
删除
红黑树的删除算法与二叉搜索树的删除算法类似，不同之处在于，在红黑树中执行一次二叉搜索树的删除运算，可能会破坏红黑树的特性，需要重新平衡。
在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。若设被删除为p，其唯一的子女为s。结点p被删除后，结点s取代了它的位置。
o 如果被删结点p是红色的，删去它不存在问题。因为树中各结点的黑高度都没有改变，也不会出现连续两个红色结点，红黑树的特性仍然保持，不需执行重新平衡过程；
o 如果被删结点p是黑色的，一旦删去它，红黑树将不满足特性的要求，因为在这条路径上黑色结点少了一个，从根到外部结点的黑高度将会降低。因此必须通过旋转变换和改变结点的颜色，消除双重黑色结点，恢复红黑树的特性。
设u是被删结点p的唯一的子女结点。
如果u是红色结点，可以把结点u染成黑色，从而恢复红黑树的特性；
如果被删结点p是黑色结点，它的唯一的子女结点u也是黑色结点，就必须先将结点p摘下，将结点u链到其祖父结点g的下面。假设结点u成为结点g的右子女，v是u的左兄弟。根据v的颜色，分以下两种情况：
情况1：结点v是黑色结点，若设结点v的左子女结点为w。根据w的颜色又需分两种情况讨论：
（1）结点w是红色结点，此时作一次右单旋转，将w、g染成黑色，v染成红色，如图所示，就可消除结点u的双重黑色，恢复红黑树的性质。
（2）结点w是黑色结点，还要看结点w的右兄弟结点r。根据结点r的颜色，又要分两种情况：
①结点r是红色结点，可通过一次先左后右的双旋转，并将g染成黑色，就可消除结点u的双重黑色，恢复红黑树的特性。
②结点r是黑色结点，这时还要看结点g的颜色。如果g是红色结点，只要交换结点g和其子女结点v的颜色就能恢复红黑树的特性，如图（a）。如果g是黑色结点，可做一次右单旋转，如图（b）。
情况2：结点υ是红色结点。考查v的右子女结点r。根据红黑树的特性，r一定是黑色结点。再看结点r的左子女结点s。根据s的颜色，可以分为两种情况讨论。
（1）结点s是红色结点。通过一次先左后右双旋转，让r上升，使包含u的路径的黑高度增1，从而消除结点u的双重黑色，恢复红黑树的特性。
（2）结点s是黑色结点，再看结点s的右兄弟结点t。根据结点t的颜色又可分为两种情况进行讨论。
①若结点t为红色结点，先以t为旋转轴，做左单旋转，以t替补r的位置；然后再以t为旋转轴，做一次先左后右的双旋转，可消除结点u的双重黑色，恢复红黑树的特性。
②若结点t为黑色结点，以v为旋转轴，做一次右单旋转，并改变υ和r的颜色，即可消除结点u的双重黑色，恢复红黑树的特色。
当结点u是结点g的左子女的情况与上面讨论的情况是镜像的，只要左、右指针互换就可以了。
4.算法实现C++代码
1 typedef enum { RED = 0, BLACK } Color;
2 //红黑树结点类型
3 template <typename Type>
4 struct RBTNode
5 {
6 Color color; //颜色
7 Type key; //关键字
8 RBTNode* left; //左孩子
9 RBTNode* right; //右孩子
10 RBTNode* parent; //父结点
11 };
12
13 //红黑树类型
14 template<typename Type>
15 class RBTree
16 {
17 public:
18 //构造函数
19 RBTree()
20 {
21 Nil = BuyNode();
22 root = Nil;
23 Nil->color = BLACK;
24 }
25 //析构函数
26 ~RBTree()
27 {
28 destroy(root); //销毁创建的非Nil结点
29 delete Nil; //最后删除Nil结点
30 Nil = NULL;
31 }
32
33 //中序遍历
34 void InOrder() { InOrder(root); }
35
36 //插入
37 //1.BST方式插入
38 //2.调整平衡
39 bool Insert(const Type &value)
40 {
41 RBTNode<Type>* pr = Nil; //pr用来记住父节点
42 RBTNode<Type>* s = root; //定义变量s指向根
43 while (s != Nil)
44 {
45 if (value == s->key)
46 {
47 return false;
48 }
49 pr = s; //每次记住s的父节点
50 if (value < s->key)
51 {
52 s = s->left;
53 }
54 else
55 {
56 s = s->right;
57 }
58 }
59 //循环后s==Nil
60 s = BuyNode(value); //申请结点
61 if (pr == Nil) //如果父节点pr是根节点，第一次root指向Nil，所以pr==Nil
62 {
63 root = s;
64 root->parent = pr;
65 }
66 else //如果父节点不是根节点
67 {
68 if (value < pr->key)
69 {
70 pr->left = s;
71 }
72 else
73 {
74 pr->right = s;
75 }
76 s->parent = pr; //设置新结点s的父节点
77 }
78 //调整平衡
79 Insert_Fixup(s);
80 return true;
81 }
82
83 //删除key结点(先查找，再调用内部删除)
84 void Remove(Type key)
85 {
86 RBTNode<Type>* t;
87 if ((t = Search(root, key)) != Nil)
88 {
89 Remove(t);
90 }
91 else
92 {
93 cout << "Key is not exist." << endl;
94 }
95 }
96
97 //中序遍历打印结点详细的结点颜色
98 void InOrderPrint() { InOrderPrint(root); }
99
100 protected:
101 //申请结点结点，将结点的颜色初始化为红色，初始化结点的关键字，其他的初始化为空
102 RBTNode<Type>* BuyNode(const Type &x = Type())
103 {
104 RBTNode<Type>* s = new RBTNode<Type>();
105 assert(s != NULL);
106 s->color = RED;
107 s->left = s->right = s->parent = Nil;
108 s->key = x;
109 return s;
110 }
111
112 //中序遍历
113 void InOrder(RBTNode<Type>* root)
114 {
115 if (root != Nil)
116 {
117 InOrder(root->left);
118 cout << root->key << " ";
119 InOrder(root->right);
120 }
121 }
122
123 //左转，对z结点左转
124 // zp zp
125 // / \
126 // z z
127 // / \ / \
128 // lz y lz y
129 // / \ / \
130 // ly ry ly ry
131 void LeftRotate(RBTNode<Type>* z)
132 {
133 RBTNode<Type>* y = z->right; //用y指向要转动的z结点
134 z->right = y->left;
135 if (y->left != Nil) //y所指结点的左结点不为空
136 {
137 y->left->parent = z;
138 }
139 y->parent = z->parent;
140 if (root == z) //z就是根节点
141 {
142 root = y;
143 }
144 else if (z == z->parent->left) //z在左结点
145 {
146 z->parent->left = y;
147 }
148 else //z在右结点
149 {
150 z->parent->right = y;
151 }
152 y->left = z;
153 z->parent = y;
154 }
155
156 //右转，对z结点进行右转
157 // zp zp
158 // / \
159 // z z
160 // / \ / \
161 // y rz y rz
162 // / \ / \
163 // ly ry ly ry
164 void RightRotate(RBTNode<Type>* z)
165 {
166 RBTNode<Type>* y = z->left;
167 z->left = y->right;
168 if (y->right != Nil)
169 {
170 y->right->parent = z;
171 }
172 y->parent = z->parent;
173 if (root == z) //如果z是根结点
174 {
175 root = y;
176 }
177 else if (z == z->parent->left) //z在左结点
178 {
179 z->parent->left = y;
180 }
181 else //z在右结点
182 {
183 z->parent->right = y;
184 }
185 y->right = z;
186 z->parent = y;
187 }
188
189 //插入后的调整函数
190 void Insert_Fixup(RBTNode<Type>* s)
191 {
192 RBTNode<Type>* uncle; //叔结点（父结点的兄弟结点）
193 while (s->parent->color == RED) //父节点的颜色也为红色
194 {
195 if (s->parent == s->parent->parent->left) //父节点是左结点
196 {
197 uncle = s->parent->parent->right;
198
199 if (uncle->color == RED) //叔结点为红色
200 {
201 //父节点和叔结点都变为黑色
202 s->parent->color = BLACK;
203 uncle->color = BLACK;
204 //祖父结点变为红色
205 s->parent->parent->color = RED;
206 //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色
207 s = s->parent->parent;
208 }
209 else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑)
210 {
211 if (s == s->parent->right) //如果调整的结点在右结点
212 {
213 s = s->parent; //先将s指向s的父结点
214 LeftRotate(s); //再左转
215 }
216 //如果调整的结点在左结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转
217 s->parent->color = BLACK;
218 s->parent->parent->color = RED;
219 RightRotate(s->parent->parent);
220 }
221 }
222 else
223 {
224 if (s->parent == s->parent->parent->right) //父节点是右结点
225 {
226 uncle = s->parent->parent->left;
227 if (uncle->color == RED) //叔结点为红色
228 {
229 //父节点和叔结点都变为黑色
230 s->parent->color = BLACK;
231 uncle->color = BLACK;
232 //祖父结点变为红色
233 s->parent->parent->color = RED;
234 //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色
235 s = s->parent->parent;
236 }
237 else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑)
238 {
239 if (s == s->parent->left) //如果调整的结点在左结点
240 {
241 s = s->parent; //先将s指向s的父结点
242 RightRotate(s); //再右转
243 }
244 //如果调整的结点在右结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转
245 s->parent->color = BLACK;
246 s->parent->parent->color = RED;
247 LeftRotate(s->parent->parent);
248 }
249 }
250 }
251 }
252 root->color = BLACK; //最后始终将根节点置为黑色
253 }
254
255 //查找key结点
256 RBTNode<Type>* Search(RBTNode<Type>* root, Type key) const
257 {
258 if (root == Nil) //root为空，或key和根的key相同
259 {
260 return Nil;
261 }
262
263 if (root->key == key)
264 {
265 return root;
266 }
267 if (key<root->key)
268 {
269 return Search(root->left, key);
270 }
271 else
272 {
273 return Search(root->right, key);
274 }
275 }
276
277 //将u的子节点指针指向u改变指向v，将v的父节点改变为指向u的父节点
278 // up
279 // \
280 // u
281 // / \
282 // ul ur
283 // / \
284 // v ulr
285 // \
286 // rv
287 void Transplant(RBTNode<Type>* u, RBTNode<Type>* v)
288 {
289 if (u->parent == Nil) //u的父节点为空
290 {
291 root = v; //直接令根root为v
292 }
293 else if (u == u->parent->left) //u父节点不为空，且u在左子树
294 {
295 u->parent->left = v;
296 }
297 else //u在左子树
298 {
299 u->parent->right = v;
300 }
301 v->parent = u->parent;
302 }
303
304 //找到最左结点(最小)
305 // xp
306 // \
307 // x
308 // / \
309 // xl xr
310 // / \
311 // xll xlr
312
313 RBTNode<Type>* Minimum(RBTNode<Type>* x)
314 {
315 if (x->left == Nil)
316 {
317 return x;
318 }
319 return Minimum(x->left);
320 }
321
322 //删除红黑树结点z
323 void Remove(RBTNode<Type>* z)
324 {
325 RBTNode<Type>* x = Nil;
326 RBTNode<Type>* y = z; //y记住传进来的z结点
327 Color ycolor = y->color; //
328 if (z->left == Nil) //z只有右孩子
329 {
330 x = z->right;
331 Transplant(z, z->right);
332 }
333 else if (z->right == Nil) //z只有右孩子
334 {
335 x = z->left;
336 Transplant(z, z->left);
337 }
338 else //右左孩子和右孩子
339 {
340 y = Minimum(z->right); //y是z右子树的的最左子树
341 ycolor = y->color;
342 x = y->right;
343 if (y->parent == z) //z的右子结点没有左节点或为Nil
344 {
345 x->parent = y;
346 }
347 else //z的右子结点有左节点或为Nil
348 {
349 Transplant(y, y->right);
350 y->right = z->right;
351 y->right->parent = y;
352 }
353 Transplant(z, y);
354 //改变指向
355 y->left = z->left;
356 z->left->parent = y;
357 y->color = z->color;
358 }
359 if (ycolor == BLACK)
360 {
361 Remove_Fixup(x);
362 }
363 }
364
365 //红黑树删除调整
366 void Remove_Fixup(RBTNode<Type>* x)
367 {
368 while (x != root&&x->color == BLACK) //当结点x不为根并且它的颜色不是黑色
369 {
370 if (x == x->parent->left) //x在左子树
371 {
372 RBTNode<Type>* w = x->parent->right; //w是x的兄结点
373
374 if (w->color == RED) //情况1
375 {
376 w->color = BLACK;
377 x->parent->color = RED;
378 LeftRotate(x->parent);
379 w = x->parent->right;
380 }
381 if (w->left->color == BLACK&&w->right->color == BLACK) //情况2
382 {
383 w->color = RED;
384 x = x->parent;
385 }
386 else
387 {
388 if (w->right->color == BLACK) //情况3
389 {
390 w->color = RED;
391 w->left->color = BLACK;
392 RightRotate(w);
393 w = x->parent->right;
394 }
395 //情况4
396 w->color = w->parent->color;
397 w->parent->color = BLACK;
398 w->right->color = BLACK;
399 LeftRotate(x->parent);
400 x = root; //结束循环
401
402 }
403 }
404 else //x在右子树
405 {
406 RBTNode<Type>* w = x->parent->left;
407 if (w->color == RED) //情况1
408 {
409 w->parent->color = RED;
410 w->color = BLACK;
411 RightRotate(x->parent);
412 w = x->parent->left;
413 }
414 if (w->right->color == BLACK&&w->right->color == BLACK) //情况2
415 {
416 w->color = RED;
417 x = x->parent;
418 }
419 else
420 {
421 if (w->left->color == BLACK) //情况3
422 {
423 w->right->color = BLACK;
424 w->color = RED;
425 LeftRotate(w);
426 w = x->parent->left;
427 }
428 //情况4
429 w->color = x->parent->color;
430 x->parent->color = BLACK;
431 w->left->color = BLACK;
432 RightRotate(x->parent);
433 x = root; //结束循环
434 }
435 }
436 }
437 x->color = BLACK;
438 }
439
440 //销毁红黑树
441 void destroy(RBTNode<Type>* &root)
442 {
443 if (root == Nil)
444 {
445 return;
446 }
447 if (root->left != Nil)
448 {
449 destroy(root->left);
450 }
451 if (root->right != Nil)
452 {
453 destroy(root->right);
454 }
455 delete root;
456 root = NULL;
457 }
458
459 //中序遍历打印结点详细的结点颜色
460 void InOrderPrint(RBTNode<Type>* node)
461 {
462 if (node == Nil)
463 {
464 return;
465 }
466 if (node->left != NULL)
467 {
468 InOrderPrint(node->left);
469 }
470 cout << node->key << "(" << ((node->color == BLACK) ? "BLACK" : "RED") << ")" << " ";
471 if (node->right != Nil)
472 {
473 InOrderPrint(node->right);
474 }
475 }
476
477 private:
478 RBTNode<Type>* root; //根指针
479 RBTNode<Type>* Nil; //外部结点，表示空结点，黑色的
480 };
⭐你也太棒了8( •̀ ω •́ )y
🐇亚亚鸭为你鼓掌！👏
⭐恭喜你已经掌握红黑树啦~(●ˇ∀ˇ●)不要忘记点赞收藏喔~
参考资料：
二叉搜索树：
https://www.w3cschool.cn/article/32088898.html#:~:text=%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E5%B1%9E%E6%80%A7%EF%BC%9A%E8%A6%81%E6%89%BE%E5%88%B0%E4%B8%80%E9%A2%97%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E5%8F%AA%E9%9C%80%E8%A6%81%E7%9F%A5%E9%81%93%E8%BF%99%E9%A2%97%E6%A0%91%E7%9A%84%E6%A0%B9%E8%8A%82%E7%82%B9%E3%80%82%20public%20class%20BST%20%7B%20static%20class%20Node,%3D%20key%3B%20%7D%20%7D%20private%20Node%20root%3B%2F%2FBST%E7%9A%84%E6%A0%B9%E8%8A%82%E7%82%B9%20%7D
AVL树：https://wangkuiwu.github.io/2013/02/02/avltree-cpp
红黑树：https://blog.csdn.net/Linuxhus/article/details/113564855
基本性质：https://baike.baidu.com