《数据结构、算法与应用C++语言描述》-红黑树的C++实现-百万级数据量测试通过
2024-01-09 23:02:04
红黑树
完整可编译运行代码见仓库：GitHub - Jasmine-up/Data-Structures-Algorithms-and-Applications/_3matrix。
如有问题请在评论区指出。另外，Github仓库会根据我的学习情况持续更新，欢迎大家点star，谢谢。
基本概念
红-黑树（red-black tree）：树中每一个节点的颜色或者是黑色或者是红色。每一个空指针用一个外部节点代替。红黑树是一种二叉搜索树。
基于节点特点的等价
- RB1：根节点和所有外部节点都是黑色。
- RB2：在根至外部节点路径上，没有连续两个节点是红色。
- RB3：在所有根至外部节点的路径上，黑色节点的数目都相同。
基于指针颜色的等价：从父节点指向黑色孩子的指针是黑色的，从父节点指向红色孩子的指针是红色的。
- RB1’：从内部节点指向外部节点的指针是黑色的。
- RB2’：在根至外部节点路径上，没有两个连续的红色指针。
- RB3’：在所有根至外部节点路径上，黑色指针的数目都相同。
注意，如果知道指针的颜色，就能推断节点的颜色，反之亦然。
举例
在图15-10的红-黑树中，阴影的方块是外部节点，阴影的圆圈是黑色节点，白色圆圈是红色节点，粗线是黑色指针，细线是红色指针。注意，在每一条根至外部节点的路径上，都有两个黑色指针和三个黑色节点（包括根节点和外部节点），且不存在两个连续的红色节点或指针。
节点的阶：是从该节点到一外部节点的路径上黑色指针的数量，外部节点的阶是0。
定理
定理15-1设从根到外部节点的路径长度（length）是该路径上的指针数量。如果P和 Q是红-黑树中的两条从根至外部节点的路径，那么 l e n g t h ( P ) ≤ 2 l e n g t h ( Q ) length(P)\leq 2length(Q) length(P)≤2length(Q)。
证明：在红黑树中，指向外部节点的指针是黑色，没有两个连续的红色指针，但是可以有连续的黑色指针，如果一条路径都是黑色指针，另一条路径是红色黑色指针交叉，这样就可得到极限情况，也就是 l e n g t h ( P ) = 2 l e n g t h ( Q ) length(P)=2length(Q) length(P)=2length(Q)。
定理15-2令h是一棵红-黑树的高度（不包括外部节点），n是树的内部节点数量，而 r是根节点的阶，则
- 1） h ≤ 2 r h \leq 2r h≤2r。
- 2） n ≥ 2 r ? 1 n\geq 2^r-1 n≥2r?1。
- 3） h ≤ 2 l o g 2 ( n + 1 ) h\leq 2log_2(n+1) h≤2log2?(n+1)。
红黑树的描述
外部节点使用空指针描述。对于每个节点，需要存储左孩子、右孩子、父亲节点的指针，对于颜色可以存储该节点的颜色或指向它的两个孩子的指针颜色。存储每个节点的颜色只需要附加一位，而存储每个指针的颜色则需要两位。选择哪种方案可根据实际需求决定。
搜索
假设要查找关键字为theKey的元素。先从根开始查找。如果根为空，那么搜索树不包含任何元素，即查找失败。如果不空，则将 theKey与根的关键字相比较。如果 theKey小，那么就不必在右子树中查找，只要查找左子树。如果theKey大，则正好相反，只需查找右子树。如果 theKey等于根的关键字，则查找成功。时间复杂度为O(logn)。
这个和二叉搜索树的查找是一样的。
AVL树是高度最小的，因此，在以搜索操作为主的应用中，在最坏情况下AVL树的时间复杂度是最优的。
插入
以下思路是普通二叉搜索树的插入方法，红黑树需要调整是否平衡。
假设要在二叉搜索树中插人一个新元素thePair，首先要通过查找来确定，在树中是否存在某个元素，其关键字与thePair.first 相同。如果搜索成功，那么就用 thePair.second 替代该元素的值。如果搜索不成功，那么就在搜索中能找到键值与thePair.first相近的节点pp，当thePair.second < pp.second时，将thePair作为pp的左孩子；反之，将thePair作为pp的右孩子。在插入元素后，treeSize++。
对插入的新元素，需要上色。如果插人前的树是空的，那么新节点是根节点，颜色应是黑色（参看特征RB1）。假设插入前的树是非空的。
如果新节点的颜色是黑色，那么在从根到外部节点的路径上，将有一个特殊的黑色节点作为新节点的孩子。如果新节点是红色，那么可能出现两个连续的红色节点。把新节点赋为黑色将肯定不符合RB3，而把新节点赋为红色则可能违反，也可能符合 RB2，因此，应将新节点赋为红色。
如果将新节点赋为红色而引起特征 RB2的破坏，我们就说树的平衡被破坏了。不平衡的类型可以通过检查新节点u、其父节点pu及祖父节点gu来确定。RB2被破坏后的情况便是有两个连续的红色节点：一个是u，另一个一定是它的父节点，因此pu存在。因为pu是红色的，它不可能是根（根据特征RB1），所以u必定有一个祖父节点gu，并且是黑色的（根据特征RB2）。
LLb类型不平衡：当pu是gu的左孩子，u是pu的左孩子且gu的另一个孩子是黑色时（这另一个可以是外部节点）。
LLr类型不平衡：当pu是gu的左孩子，u是pu的左孩子且gu的另一个孩子是红色时（这另一个可以是外部节点）。
LRb类型不平衡：当pu是gu的左孩子，u是pu的右孩子且gu的另一个孩子是黑色时（这另一个可以是外部节点）。
LRr类型不平衡：当pu是gu的左孩子，u是pu的右孩子且gu的另一个孩子是红色时（这另一个可以是外部节点）。
RRb类型不平衡：当pu是gu的右孩子，u是pu的右孩子且gu的另一个孩子是黑色时（这另一个可以是外部节点）。
RRr类型不平衡：当pu是gu的右孩子，u是pu的右孩子且gu的另一个孩子是红色时（这另一个可以是外部节点）。
RLb类型不平衡：当pu是gu的右孩子，u是pu的左孩子且gu的另一个孩子是黑色时（这另一个可以是外部节点）。
RLr类型不平衡：当pu是gu的右孩子，u是pu的左孩子且gu的另一个孩子是红色时（这另一个可以是外部节点）。
XYr（X和Y既可以是L，也可以是R）类型的不平衡可以通过改变颜色来处理，而 XYb类型则需要旋转。当节点gu被改变颜色时，它和上一层的节点可能破坏了RB2特性。这时的不平衡需要重新分类，而且u变为gu，然后再次进行转换。旋转结束后，不再违反RB2特性，因此不需要再进行其他操作。
举例：黑色节点用阴影表示，红色节点没有阴影。加粗指针是黑色指针，较细指针是红色指针。
LLr型与LRr型不平衡调整：例如，在图15-11a中，gu是黑色，而pu和u是红色。gu的两个指针是红色。 g u R gu_R guR?是gu的右子树， p u R pu_R puR?是pu的右子树。**LLr 和 LRr颜色调整需要将pu和 gu的右孩子由红色改为黑色。另外，如果gu不是根，还要将gu的颜色由黑色改为红色。如果gu是根节点，那么颜色不变，这时，所有从根至外部节点路径上的黑色节点数量都增1。**如果将 gu的颜色改为红色而引起了不平衡，那么gu就变成了新的u节点，它的双亲就变成了新的pu，它的祖父节点就变成了新的gu，这时需要继续恢复平衡。如果gu是根节点或者gu节点的颜色改变没有违反规则RB2，那么工作就完成了。
LLb型和LRb型不平衡调整：图15-12是处理LLb 和 LRb不平衡时所做的旋转。在图15-12a 和图15-12b中，pu是 p u L pu_L puL?的根。注意，这些旋转与AVL树的插人操作所需要的LL（见图15-4）和LR（见图15-5所示）旋转有相似之处。指针的改变是相同的，但是，在LLb旋转中，不仅要改变指针，还要将gu的颜色由黑色改为红色，将pu的颜色由红色改为黑色。在LRb旋转中，需要将u的颜色由红色改为黑色，将gu的颜色由黑色改为红色。
删除
使用普通二叉搜索树的删除元素方法，三种情况：
1）p是树叶；
要删除的节点是叶节点。存储叶节点到temp，将叶节点的父节点的左孩子置为nullptr，释放叶节点temp空间。若是根节点，直接释放根节点空间，令根为 nullptr。
2）p只有一棵非空子树；
要删除的节点p只有一棵子树。如果p没有父节点（即p是根节点），则p的唯一子树的根节点成为新的搜索树的根节点。如果p有父节点pp，则修改pp的指针域，使得它指向p的唯一孩子，然后释放节点p。
3）p有两棵非空子树。
先将该节点的元素替换为它的左子树的最大元素或右子树的最小元素，然后把替换元素的节点删除。本文使用左子树的最大元素替换。
要在一个节点的左子树中查找关键字最大的元素，先移动到左子树的根，然后沿着右孩子指针移动，直到右孩子指针为nullptr的节点为止。类似地，要在一个节点的右子树中查找关键字最小的元素，先移动到右子树的根，然后沿着左孩子指针移动，直到左孩子指针为nullptr的节点为止。
调整红黑树
在红黑树中，如果删除的节点是红色节点，那么删除节点后依然满足红黑树特性，不需要重新调整平衡；如果删除的节点是黑色节点，则可能会出现违反RB3的情况。令y是替代被删除节点的节点，也就是y被删除节点的父节点新指向的节点。
当违反 RB3的情况出现时，以y为根的子树缺少一个黑色节点（或一个黑色指针），因此，从根至y子树的外部节点的路径与从根至其他外部节点的路径相比，前者所包含的黑色节点数量比后者的要少一个，这时的树是不平衡的。
不平衡的类型可以根据y的父节点py和兄弟节点v的特点来划分。当y是py的右孩子时，不平衡是R型的，否则是L型的。通过观察可以得知，如果y缺少一个黑色节点，那么v就肯定不是外部节点。如果v是一个黑色节点，那么不平衡是Lb或Rb型的；而当v是红色节点时，不平衡是Lr或Rr型的。首先考察Rb型的不平衡。Lb型不平衡的处理与之相似。根据v的红色孩子的数量，把Rb型不平衡细分为三种情况：Rb0、Rb1和Rb2。
情况一：y是py的右孩子时且v是黑色节点时，不平衡类型为Rb型，可以根据v的红色孩子数量分为三种情况：Rb0、Rb1和Rb2。
如图15-15，是Rb0型的不平衡，如果py在改变前是黑色的，那么颜色的改变将导致以py为根的子树缺少一个黑色节点。在图15-15b中，从根至v的外部节点路径上，黑色节点数量也减少了一个。因此，颜色改变后，无论是从根到v的外部节点的路径，还是从根到y的外部节点的路径，都会缺少一个黑色节点。如果py是整棵红-黑树的根，那么就不需要再做其他工作，否则，py就成新的y，y的不平衡需要重新划分，并且在新的y点需要再进行调整。
若改变颜色前py是红色，则从根到y的外部节点的路径上，黑色节点数量增加了一个，而从根到v的外部节点的路径上，黑色节点数量没有改变。整棵树达到平衡。
当不平衡类型是Rb1和Rb2时，需要进行旋转，如图15-16所示。在图中，带阴影的节点既可能是红色，也可能是黑色。这种节点的颜色在旋转后不会发生变化。因此，图15-16b中，子树的根在旋转前和旋转后，颜色保持不变——图15-16b中v的颜色与图15-16a 中py的颜色是一样的。可以证明，在旋转后，从根至y的外部节点的路径上，黑色节点（黑色指针）数量增加一个，而从根至其他外部节点路径上，黑色节点的数量没有变化。旋转使树恢复了平衡。
情况二：y是py的右孩子时且v是红色节点时，不平衡类型为Rr型，可以根据v的右孩子的红色孩子数量分为三种情况：Rr0、Rr1和Rr2。都可以通过一次旋转获得平衡。
由于y中缺少一个黑色节点并且v节点是红色，所以 v L v_L vL?和 v R v_R vR?都至少有一个黑色节点不是外部节点，因此，v的孩子都是内部节点。以下是这三种情况的旋转方法。
情况三：y是py的左孩子时且v是黑色节点时，不平衡类型为Lb型，可以根据v的红色孩子数量分为三种情况：Lb0、Lb1和Lb2。
Lb型的解决方案与Rb型的解决方案是基于y节点的父亲节点的完全镜像。
情况四：y是py的左孩子时且v是红色节点时，不平衡类型为Lr型，可以根据v的红色孩子数量分为三种情况：Lr0、Lr1和Lr2。
Lr型的解决方案与Rr型的解决方案是基于y节点的父亲节点的完全镜像。
代码
main.cpp
/*
Project name : _35Red_black_tree
Last modified Date: 2024年1月5日21点00分
Last Version: V1.0
Descriptions: main()主函数
*/
#include "RedBlackTree.h"
int main() {
RedBlackTreeTest();
return 0;
}
RedBlackTree.h
/*
Project name : _35Red_black_tree
Last modified Date: 2024年1月6日18点17分
Last Version: V1.0
Descriptions: 红黑树模板类
*/
#ifndef _35RED_BLACK_TREE_REDBLACKTREE_H
#define _35RED_BLACK_TREE_REDBLACKTREE_H
#include "RedBlackTreeNode.h"
#include "dictionary.h"
#include <stack>
void RedBlackTreeTest();
using namespace std;
template<class K, class E>
class RedBlackTree : public dictionary<K, E> {
public:
RedBlackTree() {
root = nullptr;
treeSize = 0;
}
[[nodiscard]] bool empty() const { return treeSize == 0; }
[[nodiscard]] int size() const { return treeSize; }
pair<K, E> *find(K theKey) const;
void insert(pair<K, E> &thePair);
void erase(K theKey);
/*中序遍历二叉树，使用函数指针的目的是是的本函数可以实现多种目的*/
void inOrder(void(*theVisit)(RedBlackTreeNode<pair<K, E>> *)) {
visit = theVisit;
/*是因为递归，所以才要这样的*/
inOrder(root);/*这里调用的是静态成员函数inOrder()*/
}
/*中序遍历---输出endl*/
void inOrderOutput() {
inOrder(output);
cout << endl;
}
/*前序遍历二叉树，使用函数指针的目的是是的本函数可以实现多种目的*/
void preOrder(void(*theVisit)(RedBlackTreeNode<pair<K, E>> *)) {
visit = theVisit;
int num = 0;
/*是因为递归，所以才要这样的*/
preOrder(root, num);/*这里调用的是静态成员函数preOrder()*/
cout << "num = " << num << endl;
}
/*中序遍历---输出endl*/
void preOrderOutput() {
preOrder(output);
cout << endl;
}
bool ISRBTree();
private:
RedBlackTreeNode<pair<K, E>> *root;// 指向根的指针
int treeSize;// 树的结点个数
static void (*visit)(RedBlackTreeNode<pair<K, E>> *);//是一个函数指针,返回值为void 函数参数为binaryTreeNode<pair<K, E>>*
static void output(RedBlackTreeNode<pair<K, E>> *t) { cout << *t << endl; }
static void inOrder(RedBlackTreeNode<pair<K, E>> *t);
static void preOrder(RedBlackTreeNode<pair<K, E>> *t, int& num);
void rotateLL(RedBlackTreeNode<pair<K, E>> *&x);
void rotateLR(RedBlackTreeNode<pair<K, E>> *&x);
void rotateRR(RedBlackTreeNode<pair<K, E>> *&x);
void rotateRL(RedBlackTreeNode<pair<K, E>> *&x);
void rotateRr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp);
void rotateLr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp);
bool _ISRBTree(RedBlackTreeNode<pair<K, E> > * root, int count, int BlackCount);
};
/*私有静态成员初始化*/
/*这里是静态函数指针成员的初始化，不初始化会引发LINK错误*/
template<class K, class E>
void (*RedBlackTree<K, E>::visit)(RedBlackTreeNode<pair<K, E>> *) = 0; // visit function
/*中序遍历 递归*/
template<class K, class E>
void RedBlackTree<K, E>::inOrder(RedBlackTreeNode<pair<K, E>> *t) {
if (t != nullptr) {
inOrder(t->leftChild);/*中序遍历左子树*/
visit(t);/*访问树根*/
inOrder(t->rightChild);/*中序遍历右子树*/
}
}
/*前序遍历 递归*/
template<class K, class E>
void RedBlackTree<K, E>::preOrder(RedBlackTreeNode<pair<K, E>> *t, int& num) {
if (t != nullptr) {
visit(t);/*访问树根*/
num++;
preOrder(t->leftChild, num);/*中序遍历左子树*/
preOrder(t->rightChild, num);/*中序遍历右子树*/
}
}
/* 查找元素
* 输入：theKey表示需要查找元素的键值
* 输出：键值为theKey的节点的pair地址
* 时间复杂度：O(logn)，n表示节点个数
*/
template<class K, class E>
pair<K, E> *RedBlackTree<K, E>::find(K theKey) const {
// 返回值是匹配数对的指针
// 如果没有匹配的数对，返回值为nullptr
// p从根节点开始搜索，寻找关键字等于theKey的一个元素
RedBlackTreeNode<pair<K, E> > *p = root;
while (p != nullptr)
// 检查元素 p->element
if (theKey < p->element.first)
p = p->leftChild;
else if (theKey > p->element.first)
p = p->rightChild;
else // 找到匹配的元素
return &p->element;
// 没找到匹配的元素
return nullptr;
}
/*
* LL旋转
* 输入：x是第一个L的父亲节点，插入元素和删除元素都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateLL(RedBlackTreeNode<pair<K, E>> *&x) {
// 记录祖父节点的父亲节点
RedBlackTreeNode<pair<K, E>> *Parent = x->parent;
RedBlackTreeNode<pair<K, E>> *b = x->leftChild;
x->leftChild = b->rightChild;
if(b->rightChild)
b->rightChild->parent = x;
b->rightChild = x;
// x的父亲节点变为b
x->parent = b;
// b的父亲节点变为原来x的父亲节点
b->parent = Parent;
// 这里就是原来祖父节点的父亲现在需要作为b的父亲，前提是祖父节点的父亲存在
if (Parent != nullptr) {
if (x == Parent->leftChild)
Parent->leftChild = b;
else
Parent->rightChild = b;
} else
root = b;// 祖父节点如果没有父亲的话就是根节点
x = b;// b节点将替换x节点
}
/*
* RR旋转
* 输入：x表示第一个R的父亲节点，在插入和删除时都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateRR(RedBlackTreeNode<pair<K, E>> *&x) {
// 记录祖父节点的父亲节点
RedBlackTreeNode<pair<K, E>> *Parent = x->parent;
RedBlackTreeNode<pair<K, E>> *b = x->rightChild;
x->rightChild = b->leftChild;
if(b->leftChild)
b->leftChild->parent = x;
b->leftChild = x;
x->parent = b;// x的父亲节点为b
// b的父亲节点为祖父节点的父亲节点
b->parent = Parent;
// 这里就是原来祖父节点的父亲现在需要作为b的父亲，前提是祖父节点的父亲存在
if (Parent != nullptr) {
if (x == Parent->leftChild)
Parent->leftChild = b;
else
Parent->rightChild = b;
} else
root = b;// 祖父节点如果没有父亲的话就是根节点
x = b;
}
/*
* LR旋转
* 输入：x表示L的父亲节点，插入元素和删除元素时都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateLR(RedBlackTreeNode<pair<K, E>> *&x) {
rotateRR(x->leftChild);
rotateLL(x);
}
/*
* RL旋转
* 输入：x表示R的父亲节点，插入元素和删除元素都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateRL(RedBlackTreeNode<pair<K, E>> *&x) {
rotateLL(x->rightChild);
rotateRR(x);
}
/*
* 删除节点时：对于Rr1(2)型和Rr2型的旋转使用
* 输入：替换被删除节点的y节点的父亲节点
* 输出：void
* 时间复杂度：O(1)
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateRr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp) {
RedBlackTreeNode<pair<K, E>> *Parent = pp->parent;
RedBlackTreeNode<pair<K, E>> *w = pp->leftChild->rightChild;
RedBlackTreeNode<pair<K, E>> *x = w->rightChild;
if(x != nullptr){
w->rightChild = x->leftChild;
if(x->leftChild)
x->leftChild->parent = w;// 父亲节点要及时更改
}
else{
cout << "rotateRr1_2and2 error!" << endl;
}
x->leftChild = pp->leftChild;
pp->leftChild->parent = x;
pp->leftChild = x->rightChild;
if(x->rightChild)
x->rightChild->parent = pp;
x->rightChild = pp;
pp->parent = x;
if(Parent->leftChild == pp)
Parent->leftChild = x;
else
Parent->rightChild = x;
x->parent = Parent;
pp = x;
}
/*
* 删除节点时，对于Lr1(2)型和Lr2型的旋转使用
* 输入：替换被删除节点的y节点的父亲节点
* 输出：void
* 时间复杂度：O(1)
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateLr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp) {
RedBlackTreeNode<pair<K, E>> *Parent = pp->parent;
RedBlackTreeNode<pair<K, E>> *w = pp->rightChild->leftChild;
RedBlackTreeNode<pair<K, E>> *x = w->leftChild;
if(x != nullptr){
w->leftChild = x->rightChild;
if(x->rightChild)
x->rightChild->parent = w;// 父亲节点要及时更改
}
else{
cout << "rotateLr1_2and2 error!" << endl;
}
x->rightChild = pp->rightChild;
pp->rightChild->parent = x;
pp->rightChild = x->leftChild;
if(x->leftChild)
x->leftChild->parent = pp;
x->leftChild = pp;
pp->parent = x;
if(Parent->leftChild == pp)
Parent->leftChild = x;
else
Parent->rightChild = x;
x->parent = Parent;
pp = x;
}
/*
* 插入元素
* 输入：const pair<K, E> thePair表示需要插入的键值对
* 输出：void
* 时间复杂度：O(logn)，表示节点个数
*/
template<class K, class E>
void RedBlackTree<K, E>::insert(pair<K, E> &thePair) {
// 当红黑树为空时，插入节点直接作为根节点，且其颜色为黑色
if (root == nullptr) {
root = new RedBlackTreeNode<pair<K, E> >(thePair, nullptr, nullptr, nullptr, false);
treeSize++;
return;
}
// 如果树非空. 如果该键值存在则覆盖元素
// 寻找插入位置
RedBlackTreeNode<pair<K, E> > *p = root,
*pp = nullptr;
while (p != nullptr) {// 检查元素 p->element
pp = p;
// 如果当前键值小于p的键值，则移到p的左孩子
if (thePair.first < p->element.first)
p = p->leftChild;
else// 如果当前键值大于p的键值，则移到p的右孩子
if (thePair.first > p->element.first)
p = p->rightChild;
else {// 如果键值相等，覆盖旧的值
p->element.second = thePair.second;
return;
}
}
// 为thePair建立一个节点，然后与pp链接，此时pp是叶子节，默认插入为红色节点
auto *newNode = new RedBlackTreeNode<pair<K, E> >(thePair);
// 如果thePair的键值小于pp的键值，则将thePair作为pp的左孩子，反之将其作为右孩子
if (thePair.first < pp->element.first) {
pp->leftChild = newNode;
newNode->parent = pp;
} else {
pp->rightChild = newNode;
newNode->parent = pp;
}
treeSize++;
p = newNode;
// 如果父亲节点存在且父亲节点是红色的，则需要对红黑树进行调整
while (pp && pp->isRed == true) {
// parent是红色，则其父节点一定存在
RedBlackTreeNode<pair<K, E> > *grandfather = pp->parent;
if (pp == grandfather->leftChild) {// parent是grandfather的左孩子
// LYr(Y可以是L或R)的情况
RedBlackTreeNode<pair<K, E> > *uncle = grandfather->rightChild;// 找到grandfather的右孩子，可以称为叔叔
if (uncle && uncle->isRed == true) {// 如果叔叔存在且为红色
// 将父亲节点和其叔叔节点的颜色更改为黑色
pp->isRed = uncle->isRed = false;
// 只有在祖父节点不为根节点时，将祖父节点的颜色更改为红色
if (grandfather != root)
grandfather->isRed = true;
else // 如果祖父节点已经是根节点了，那么就直接终止循环，因为不可能再向上处理了
break;
// 继续往上处理
p = grandfather;
pp = p->parent;
} else {// uncle不存在或者uncle存在且为黑色
// 如果当前节点是其父亲节点的左孩子
// LLb的情况：左孩子的左孩子
if (p == pp->leftChild) {
rotateLL(grandfather);// LL单旋
// 调整颜色
// 现在的grandfather指向的是原来的父亲节点，grandfather的右孩子指向的是原祖父节点
grandfather->isRed = false;
grandfather->rightChild->isRed = true;
} else {// LRb的情况
rotateLR(grandfather);
// 调整颜色
// 现在的grandfather指向的是原来的新节点u，u的左孩子是原来的父亲节点pu，u的右孩子是原来的祖父节点gu
grandfather->isRed = false;
grandfather->rightChild->isRed = true;
}
break;// 无需继续向上进行处理
}
} else {// parent是grandfather的右孩子
// RYr(Y可以是L或R)的情况
RedBlackTreeNode<pair<K, E> > *uncle = grandfather->leftChild;// 找到grandfather的左孩子，可以称为叔叔
if (uncle && uncle->isRed == true) {// 如果叔叔存在且为红色
// 将父亲节点和其叔叔节点的颜色更改为黑色
pp->isRed = uncle->isRed = false;
// 只有在祖父节点不为根节点时，将祖父节点的颜色更改为红色
if (grandfather != root)
grandfather->isRed = true;
else // 如果祖父节点已经是根节点了，那么就直接终止循环，因为不可能再向上处理了
break;
// 继续往上处理
p = grandfather;
pp = p->parent;
} else {// uncle不存在或者uncle存在且为黑色
// 如果当前节点是其父亲节点的右孩子
// RRb的情况：右孩子的右孩子
if (p == pp->rightChild) {
rotateRR(grandfather);// RR单旋
// 调整颜色
// 现在的grandfather指向的是原来的父亲节点，grandfather的左孩子指向的是原祖父节点
grandfather->isRed = false;
grandfather->leftChild->isRed = true;
} else {// LRb的情况
rotateRL(grandfather);
// 调整颜色
// 现在的grandfather指向的是原来的新节点u，u的右孩子是原来的父亲节点pu，u的左孩子是原来的祖父节点gu
grandfather->isRed = false;
grandfather->leftChild->isRed = true;
}
break;// 无需继续向上进行处理
}
}
}
}
/*
* 删除元素
* 输入：const K theKey表示需要删除元素的键值
* 输出：void
* 时间复杂度：O(logn)，n表示节点个数
*/
template<class K, class E>
void RedBlackTree<K, E>::erase(K theKey) {
// 删除关键字等于theKey的数对
// 查找关键字为theKey的节点
RedBlackTreeNode<pair<K, E> > *p = root,
*pp = nullptr;
while (p != nullptr && p->element.first != theKey)
{
pp = p;
if (theKey < p->element.first)
p = p->leftChild;
else
p = p->rightChild;
}
if (p == nullptr){
cout << theKey << " not exist!" << endl;
return; // 不存在与关键字theKey匹配的数对
}
// 重新组织树结构
// 当p有两个孩子时的处理
if (p->leftChild != nullptr && p->rightChild != nullptr)
{
// 两个孩子
// 在P的左子树中寻找最大元素
RedBlackTreeNode<pair<K, E> > *s = p->leftChild,
*ps = p; // s的父节点
while (s->rightChild != nullptr)
{// 移动到更大的pair
ps = s;
s = s->rightChild;// 右孩子比较大
}
// 将最大元素s移到p
// p->element = s->element 的键值是 const
// 当最大值就是p的左孩子时，new的元素不能直接指向p的左孩子，而要指向p的左孩子的左孩子(此时p的左孩子没有右孩子)，因为到时候s会被delete掉,这个问题在后面的p至多有一个孩子那里解决的
RedBlackTreeNode<pair<K, E> >* q = nullptr;
// 值用s的值替换，颜色和其他指针的指向都是p的
q = new RedBlackTreeNode<pair<K, E> >(s->element, p->leftChild, p->rightChild, p->parent, p->isRed);
if(p->leftChild)
p->leftChild->parent = q;
if(p->rightChild)
p->rightChild->parent = q;
// pp是p的父节点
// 如果p没有父节点
if (pp == nullptr)
root = q;
else if (p == pp->leftChild)// 如果p是pp的左孩子
pp->leftChild = q;
else// 如果p是pp的右孩子
pp->rightChild = q;
// 如果s的父节点就是p，说明p节点的左子树只有左子树没有右子树
// 那么删除p后pp就是其父节点
if (ps == p) pp = q;
else pp = ps;// 反之ps是其父节点
delete p;
p = s;
}
// p至多只有一个孩子
// 把孩子的指针存放到c
RedBlackTreeNode<pair<K, E> > *c;
if (p->leftChild != nullptr)
c = p->leftChild;
else
c = p->rightChild;
// 删除p
bool isLeft = false;// 记录p节点是左孩子还是右孩子
if (p == root)
root = c;
else
{// p是pp的左孩子还是右孩子
if (p == pp->leftChild){
pp->leftChild = c;
// 更新一下c节点的父亲节点
if(c != nullptr)
c->parent = pp;
isLeft = true;
}
else{
pp->rightChild = c;
// 更新一下c节点的父亲节点
if(c != nullptr)
c->parent = pp;
}
}
treeSize--;
// 之前就找到了y节点的父亲节点pp
// 如果被删除节点是红色的，则红黑树还是平衡的；如果被删除节点是黑色的，则红黑树需要调整
if(p->isRed == false){
// 父亲节点不为空，说明还需要继续调整
while(pp){
// 如果c节点不为空，则需要判断c节点是左孩子还是右孩子
// 这个主要是用于第二轮调整平衡，也就是c节点此时不再是p的孩子节点
if(c){
if(c == pp->leftChild)
isLeft = true;
else
isLeft = false;
}
if(isLeft){
// 找到被删除节点的兄弟
RedBlackTreeNode<pair<K, E> > *v = pp->rightChild;
// 如果兄弟节点是黑色节点 Lb型
// 如果c和v都为空的话，那么不用调整平衡
if(!c && !v)
break;
if(!v->isRed){
// 如果v的左右孩子都是红色节点，Lb2型;或者v的左孩子是红色节点，Lb1(2)型
if(v->leftChild && v->leftChild->isRed){
rotateRL(pp);// OK1
pp->isRed = pp->leftChild->isRed;
pp->leftChild->isRed = false;
break;
}
else if(v->rightChild && v->rightChild->isRed){// 如果v的左孩子是红色节点，Lb1(1)型
rotateRR(pp);// OK1
pp->isRed = pp->leftChild->isRed;// 这个节点的颜色不变
pp->leftChild->isRed = false;// 原来的祖先节点的颜色变为黑色节点
v->rightChild->isRed = false;// 将v的左孩子更改为黑色节点
break;// 不需要继续调整了
}
else{// 如果v的左右孩子都是黑色节点，Lb0型
// pp是红色节点，改变pp为黑色节点，改变v为红色节点
if(pp->isRed){
pp->isRed = false;// OK1
v->isRed = true;
break;// 终止循环，不需要再继续调整了
}
else{// pp是黑色节点，将v节点改变为红色节点，然后将pp节点作为新的y节点，也就是程序中的p节点
v->isRed = true;//OK1
// 继续调整平衡
c = pp;
pp = c->parent;
}
}
}
else{// 如果兄弟节点是红色节点 Lr型，则兄弟节点一定有左右孩子
// 找到被删除节点的兄弟的左孩子
RedBlackTreeNode<pair<K, E> > *vL = v->leftChild;
// 如果vL的左右孩子都是红色节点，Lr2型 或者 如果v的左孩子是红色节点，Lr1(2)型
if(vL && vL->leftChild && vL->leftChild->isRed){
rotateLr1_2and2(pp);// OK1
pp->isRed = false;
break;
}
else if(vL && vL->rightChild && vL->rightChild->isRed){// 如果v的右孩子是红色节点，Lr1(1)型
rotateRL(pp);// OK1
if(vL->rightChild->leftChild)
vL->rightChild->leftChild->isRed = false;
break;
}
else{// 如果v的左右孩子都是黑色节点，Lr0型
rotateRR(pp);// OK1
pp->isRed = false;// 更改原来的v节点为黑色节点
if(pp->leftChild->rightChild)
pp->leftChild->rightChild->isRed = true;
break;
}
}
}
else{// 否则是R型
// 找到被删除节点的兄弟
RedBlackTreeNode<pair<K, E> > *v = pp->leftChild;
// 如果c和v都为空的话，那么树本身就是平衡的
if((!c && !v))
break;
// 如果兄弟节点是黑色节点 Rb型
if(!v->isRed){
// 如果v的左右孩子都是红色节点，Rb2型；或者v的右孩子是红色节点，Rb1(2)型
if(v->rightChild && v->rightChild->isRed){
rotateLR(pp);// OK1
pp->isRed = pp->rightChild->isRed;
pp->rightChild->isRed = false;
break;
}
else if(v->leftChild && v->leftChild->isRed){// 如果v的左孩子是红色节点，Rb1(1)型
rotateLL(pp);// OK1
pp->isRed = pp->rightChild->isRed;// 这个节点的颜色不变
pp->rightChild->isRed = false;// 原来的祖先节点的颜色变为黑色节点
v->leftChild->isRed = false;// 将v的左孩子更改为黑色节点
break;// 不需要继续调整了
}
else{// 如果v的左右孩子都是黑色节点，Rb0型
// pp是红色节点，改变pp为黑色节点，改变v为红色节点
if(pp->isRed){
pp->isRed = false;// OK1
v->isRed = true;
break;// 终止循环，不需要再继续调整了
}
else{// pp是黑色节点，将v节点改变为红色节点，然后将pp节点作为新的y节点，也就是程序中的p节点
// 这个没有找到合适的节点去测试
v->isRed = true;//OK1
c = pp;
pp = c->parent;
}
}
}
else{// 如果兄弟节点v是红色节点 Rr型，则兄弟节点v一定有左右孩子
// 找到被删除节点的兄弟的右孩子
RedBlackTreeNode<pair<K, E> > *vR = v->rightChild;
// 如果vR的左右孩子都是红色节点，Rr2型 或者 vR的右孩子是红色节点，Rr1(2)型 两个合起来就是vR的右孩子存在且是红色节点
// 两种操作都是一样的
if(vR && vR->rightChild && vR->rightChild->isRed){
rotateRr1_2and2(pp);// OK1
pp->isRed = false;
break;
}
else if(vR && vR->leftChild && vR->leftChild->isRed){// 如果vR的左孩子是红色节点，Rr1(1)型
rotateLR(pp);// OK1
if(vR->leftChild->rightChild)
vR->leftChild->rightChild->isRed = false;
break;
}
else{// 如果v的左右孩子都是黑色节点，Rr0型，没找到合适的树来测试
// 如果c节点是nullptr的话，树本来就是平衡的，不需要调整了
// OK1
rotateLL(pp);
pp->isRed = false;// 更改原来的v节点为黑色节点
if(pp->rightChild->leftChild)
pp->rightChild->leftChild->isRed = true;
break;
}
}
}
}
}
if(root && root->isRed == true)
root->isRed = false;
delete p;
}
//判断是否为红黑树
template<class K, class E>
bool RedBlackTree<K, E>::ISRBTree()
{
if (root == nullptr) //空树是红黑树
{
return true;
}
if (root->isRed == true)
{
cout << "error: root is red" << endl;
return false;
}
//找最左路径作为黑色结点数目的参考值
RedBlackTreeNode<pair<K, E> > *cur = root;
int BlackCount = 0;
while (cur)
{
if (cur->isRed == false)
BlackCount++;
cur = cur->leftChild;
}
int count = 0;
return _ISRBTree(root, count, BlackCount);
}
//判断是否为红黑树的子函数
template<class K, class E>
bool RedBlackTree<K, E>::_ISRBTree(RedBlackTreeNode<pair<K, E> > * cur, int count, int BlackCount)
{
if (cur == nullptr) //该路径已经走完了
{
if (count != BlackCount)
{
cout << "error: black nodes nums not equal" << endl;
return false;
}
return true;
}
if (cur->isRed == true && cur->parent->isRed == true)
{
cout << "error: red and red nodes together" << endl;
return false;
}
if (cur->isRed == false)
{
count++;
}
return _ISRBTree(cur->leftChild, count, BlackCount) && _ISRBTree(cur->rightChild, count, BlackCount);
}
// overload << for pair
template<class K, class E>
ostream &operator<<(ostream &out, const pair<K, E> &x) {
out << x.first << ":" << x.second;
return out;
}
template<class K, class E>
ostream &operator<<(ostream &out, const RedBlackTreeNode<pair<K, E>> &x) {
out << x.element.first << ":" << x.element.second << " isRed = " << x.isRed;
return out;
}
#endif //_35RED_BLACK_TREE_REDBLACKTREE_H
RedBlackTree.cpp
/*
Project name : _35Red_black_tree
Last modified Date: 2024年1月9日21点10分
Last Version: V1.0
Descriptions: 红黑树测试函数
*/
#include "RedBlackTree.h"
#include<vector>
void RedBlackTreeTest() {
cout << "*************************RedBlackTreeTest() begin*******************************" << endl;
RedBlackTree<int, char> y;
pair<int, char> data;
for(int i = 1; i < 1000001; i++){
data = pair<int, char>(i, 'e');
y.insert(data);
}
// 第二种删除策略
for(int i = 250000; i > 0; i--){
cout << " Delete " << i << endl;
y.erase(i);
cout << "y.ISRBTree() = " << y.ISRBTree() << endl;
}
for(int i = 500000; i < 750001; i++){
cout << " Delete " << i << endl;
y.erase(i);
cout << "y.ISRBTree() = " << y.ISRBTree() << endl;
}
for(int i = 250001; i < 500000; i++){
cout << " Delete " << i << endl;
y.erase(i);
cout << "y.ISRBTree() = " << y.ISRBTree() << endl;
}
for(int i = 1000000; i > 750000; i--){
cout << " Delete " << i << endl;
y.erase(i);
cout << "y.ISRBTree() = " << y.ISRBTree() << endl;
}
cout << "***************************RedBlackTreeTest() end*******************************" << endl;
}
RedBlackTreeNode.h
/*
Project name : _35Red_black_tree
Last modified Date: 2024年1月5日21点00分
Last Version: V1.0
Descriptions: 红黑树树节点模板类
*/
#ifndef _35RED_BLACK_TREE_REDBLACKTREENODE_H
#define _35RED_BLACK_TREE_REDBLACKTREENODE_H
template<class T>
struct RedBlackTreeNode {
T element;// 存储键值对
RedBlackTreeNode<T> *leftChild, // 左子树
*rightChild, // 右子树
*parent; // 父亲节点
bool isRed; // true表示为红色，false表示为黑色
RedBlackTreeNode() {
leftChild = rightChild = parent = nullptr;
isRed = true;
}
explicit RedBlackTreeNode(T &theElement) : element(theElement) {
leftChild = rightChild = parent = nullptr;
isRed = true;
}
explicit RedBlackTreeNode(T &theElement,
RedBlackTreeNode *theLeftChild,
RedBlackTreeNode *theRightChild,
RedBlackTreeNode *theParent)
: element(theElement), leftChild(theLeftChild),
rightChild(theRightChild), parent(theParent) {
isRed = true;
}
explicit RedBlackTreeNode(T &theElement,
RedBlackTreeNode *theLeftChild,
RedBlackTreeNode *theRightChild,
RedBlackTreeNode *theParent, bool theIsRed)
: element(theElement), leftChild(theLeftChild), rightChild(theRightChild), parent(theParent) {
isRed = theIsRed;
}
};
#endif //_35RED_BLACK_TREE_REDBLACKTREENODE_H
dictionary.h
/*
Project name : _35Red_black_tree
Last modified Date: 2024年1月6日18点17分
Last Version: V1.0
Descriptions: 红黑树模板类
*/
#ifndef _35RED_BLACK_TREE_REDBLACKTREE_H
#define _35RED_BLACK_TREE_REDBLACKTREE_H
#include "RedBlackTreeNode.h"
#include "dictionary.h"
#include <stack>
void RedBlackTreeTest();
using namespace std;
template<class K, class E>
class RedBlackTree : public dictionary<K, E> {
public:
RedBlackTree() {
root = nullptr;
treeSize = 0;
}
[[nodiscard]] bool empty() const { return treeSize == 0; }
[[nodiscard]] int size() const { return treeSize; }
pair<K, E> *find(K theKey) const;
void insert(pair<K, E> &thePair);
void erase(K theKey);
/*中序遍历二叉树，使用函数指针的目的是是的本函数可以实现多种目的*/
void inOrder(void(*theVisit)(RedBlackTreeNode<pair<K, E>> *)) {
visit = theVisit;
/*是因为递归，所以才要这样的*/
inOrder(root);/*这里调用的是静态成员函数inOrder()*/
}
/*中序遍历---输出endl*/
void inOrderOutput() {
inOrder(output);
cout << endl;
}
/*前序遍历二叉树，使用函数指针的目的是是的本函数可以实现多种目的*/
void preOrder(void(*theVisit)(RedBlackTreeNode<pair<K, E>> *)) {
visit = theVisit;
int num = 0;
/*是因为递归，所以才要这样的*/
preOrder(root, num);/*这里调用的是静态成员函数preOrder()*/
cout << "num = " << num << endl;
}
/*中序遍历---输出endl*/
void preOrderOutput() {
preOrder(output);
cout << endl;
}
bool ISRBTree();
private:
RedBlackTreeNode<pair<K, E>> *root;// 指向根的指针
int treeSize;// 树的结点个数
static void (*visit)(RedBlackTreeNode<pair<K, E>> *);//是一个函数指针,返回值为void 函数参数为binaryTreeNode<pair<K, E>>*
static void output(RedBlackTreeNode<pair<K, E>> *t) { cout << *t << endl; }
static void inOrder(RedBlackTreeNode<pair<K, E>> *t);
static void preOrder(RedBlackTreeNode<pair<K, E>> *t, int& num);
void rotateLL(RedBlackTreeNode<pair<K, E>> *&x);
void rotateLR(RedBlackTreeNode<pair<K, E>> *&x);
void rotateRR(RedBlackTreeNode<pair<K, E>> *&x);
void rotateRL(RedBlackTreeNode<pair<K, E>> *&x);
void rotateRr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp);
void rotateLr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp);
bool _ISRBTree(RedBlackTreeNode<pair<K, E> > * root, int count, int BlackCount);
};
/*私有静态成员初始化*/
/*这里是静态函数指针成员的初始化，不初始化会引发LINK错误*/
template<class K, class E>
void (*RedBlackTree<K, E>::visit)(RedBlackTreeNode<pair<K, E>> *) = 0; // visit function
/*中序遍历 递归*/
template<class K, class E>
void RedBlackTree<K, E>::inOrder(RedBlackTreeNode<pair<K, E>> *t) {
if (t != nullptr) {
inOrder(t->leftChild);/*中序遍历左子树*/
visit(t);/*访问树根*/
inOrder(t->rightChild);/*中序遍历右子树*/
}
}
/*前序遍历 递归*/
template<class K, class E>
void RedBlackTree<K, E>::preOrder(RedBlackTreeNode<pair<K, E>> *t, int& num) {
if (t != nullptr) {
visit(t);/*访问树根*/
num++;
preOrder(t->leftChild, num);/*中序遍历左子树*/
preOrder(t->rightChild, num);/*中序遍历右子树*/
}
}
/* 查找元素
* 输入：theKey表示需要查找元素的键值
* 输出：键值为theKey的节点的pair地址
* 时间复杂度：O(logn)，n表示节点个数
*/
template<class K, class E>
pair<K, E> *RedBlackTree<K, E>::find(K theKey) const {
// 返回值是匹配数对的指针
// 如果没有匹配的数对，返回值为nullptr
// p从根节点开始搜索，寻找关键字等于theKey的一个元素
RedBlackTreeNode<pair<K, E> > *p = root;
while (p != nullptr)
// 检查元素 p->element
if (theKey < p->element.first)
p = p->leftChild;
else if (theKey > p->element.first)
p = p->rightChild;
else // 找到匹配的元素
return &p->element;
// 没找到匹配的元素
return nullptr;
}
/*
* LL旋转
* 输入：x是第一个L的父亲节点，插入元素和删除元素都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateLL(RedBlackTreeNode<pair<K, E>> *&x) {
// 记录祖父节点的父亲节点
RedBlackTreeNode<pair<K, E>> *Parent = x->parent;
RedBlackTreeNode<pair<K, E>> *b = x->leftChild;
x->leftChild = b->rightChild;
if(b->rightChild)
b->rightChild->parent = x;
b->rightChild = x;
// x的父亲节点变为b
x->parent = b;
// b的父亲节点变为原来x的父亲节点
b->parent = Parent;
// 这里就是原来祖父节点的父亲现在需要作为b的父亲，前提是祖父节点的父亲存在
if (Parent != nullptr) {
if (x == Parent->leftChild)
Parent->leftChild = b;
else
Parent->rightChild = b;
} else
root = b;// 祖父节点如果没有父亲的话就是根节点
x = b;// b节点将替换x节点
}
/*
* RR旋转
* 输入：x表示第一个R的父亲节点，在插入和删除时都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateRR(RedBlackTreeNode<pair<K, E>> *&x) {
// 记录祖父节点的父亲节点
RedBlackTreeNode<pair<K, E>> *Parent = x->parent;
RedBlackTreeNode<pair<K, E>> *b = x->rightChild;
x->rightChild = b->leftChild;
if(b->leftChild)
b->leftChild->parent = x;
b->leftChild = x;
x->parent = b;// x的父亲节点为b
// b的父亲节点为祖父节点的父亲节点
b->parent = Parent;
// 这里就是原来祖父节点的父亲现在需要作为b的父亲，前提是祖父节点的父亲存在
if (Parent != nullptr) {
if (x == Parent->leftChild)
Parent->leftChild = b;
else
Parent->rightChild = b;
} else
root = b;// 祖父节点如果没有父亲的话就是根节点
x = b;
}
/*
* LR旋转
* 输入：x表示L的父亲节点，插入元素和删除元素时都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateLR(RedBlackTreeNode<pair<K, E>> *&x) {
rotateRR(x->leftChild);
rotateLL(x);
}
/*
* RL旋转
* 输入：x表示R的父亲节点，插入元素和删除元素都会用到
* 输出：void
* 时间复杂度：O(1)
* 注意事项：执行本函数前后x指向的元素会改变为新的该子树的根节点
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateRL(RedBlackTreeNode<pair<K, E>> *&x) {
rotateLL(x->rightChild);
rotateRR(x);
}
/*
* 删除节点时：对于Rr1(2)型和Rr2型的旋转使用
* 输入：替换被删除节点的y节点的父亲节点
* 输出：void
* 时间复杂度：O(1)
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateRr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp) {
RedBlackTreeNode<pair<K, E>> *Parent = pp->parent;
RedBlackTreeNode<pair<K, E>> *w = pp->leftChild->rightChild;
RedBlackTreeNode<pair<K, E>> *x = w->rightChild;
if(x != nullptr){
w->rightChild = x->leftChild;
if(x->leftChild)
x->leftChild->parent = w;// 父亲节点要及时更改
}
else{
cout << "rotateRr1_2and2 error!" << endl;
}
x->leftChild = pp->leftChild;
pp->leftChild->parent = x;
pp->leftChild = x->rightChild;
if(x->rightChild)
x->rightChild->parent = pp;
x->rightChild = pp;
pp->parent = x;
if(Parent->leftChild == pp)
Parent->leftChild = x;
else
Parent->rightChild = x;
x->parent = Parent;
pp = x;
}
/*
* 删除节点时，对于Lr1(2)型和Lr2型的旋转使用
* 输入：替换被删除节点的y节点的父亲节点
* 输出：void
* 时间复杂度：O(1)
*/
template<class K, class E>
void RedBlackTree<K, E>::rotateLr1_2and2(RedBlackTreeNode<pair<K, E>> *&pp) {
RedBlackTreeNode<pair<K, E>> *Parent = pp->parent;
RedBlackTreeNode<pair<K, E>> *w = pp->rightChild->leftChild;
RedBlackTreeNode<pair<K, E>> *x = w->leftChild;
if(x != nullptr){
w->leftChild = x->rightChild;
if(x->rightChild)
x->rightChild->parent = w;// 父亲节点要及时更改
}
else{
cout << "rotateLr1_2and2 error!" << endl;
}
x->rightChild = pp->rightChild;
pp->rightChild->parent = x;
pp->rightChild = x->leftChild;
if(x->leftChild)
x->leftChild->parent = pp;
x->leftChild = pp;
pp->parent = x;
if(Parent->leftChild == pp)
Parent->leftChild = x;
else
Parent->rightChild = x;
x->parent = Parent;
pp = x;
}
/*
* 插入元素
* 输入：const pair<K, E> thePair表示需要插入的键值对
* 输出：void
* 时间复杂度：O(logn)，表示节点个数
*/
template<class K, class E>
void RedBlackTree<K, E>::insert(pair<K, E> &thePair) {
// 当红黑树为空时，插入节点直接作为根节点，且其颜色为黑色
if (root == nullptr) {
root = new RedBlackTreeNode<pair<K, E> >(thePair, nullptr, nullptr, nullptr, false);
treeSize++;
return;
}
// 如果树非空. 如果该键值存在则覆盖元素
// 寻找插入位置
RedBlackTreeNode<pair<K, E> > *p = root,
*pp = nullptr;
while (p != nullptr) {// 检查元素 p->element
pp = p;
// 如果当前键值小于p的键值，则移到p的左孩子
if (thePair.first < p->element.first)
p = p->leftChild;
else// 如果当前键值大于p的键值，则移到p的右孩子
if (thePair.first > p->element.first)
p = p->rightChild;
else {// 如果键值相等，覆盖旧的值
p->element.second = thePair.second;
return;
}
}
// 为thePair建立一个节点，然后与pp链接，此时pp是叶子节，默认插入为红色节点
auto *newNode = new RedBlackTreeNode<pair<K, E> >(thePair);
// 如果thePair的键值小于pp的键值，则将thePair作为pp的左孩子，反之将其作为右孩子
if (thePair.first < pp->element.first) {
pp->leftChild = newNode;
newNode->parent = pp;
} else {
pp->rightChild = newNode;
newNode->parent = pp;
}
treeSize++;
p = newNode;
// 如果父亲节点存在且父亲节点是红色的，则需要对红黑树进行调整
while (pp && pp->isRed == true) {
// parent是红色，则其父节点一定存在
RedBlackTreeNode<pair<K, E> > *grandfather = pp->parent;
if (pp == grandfather->leftChild) {// parent是grandfather的左孩子
// LYr(Y可以是L或R)的情况
RedBlackTreeNode<pair<K, E> > *uncle = grandfather->rightChild;// 找到grandfather的右孩子，可以称为叔叔
if (uncle && uncle->isRed == true) {// 如果叔叔存在且为红色
// 将父亲节点和其叔叔节点的颜色更改为黑色
pp->isRed = uncle->isRed = false;
// 只有在祖父节点不为根节点时，将祖父节点的颜色更改为红色
if (grandfather != root)
grandfather->isRed = true;
else // 如果祖父节点已经是根节点了，那么就直接终止循环，因为不可能再向上处理了
break;
// 继续往上处理
p = grandfather;
pp = p->parent;
} else {// uncle不存在或者uncle存在且为黑色
// 如果当前节点是其父亲节点的左孩子
// LLb的情况：左孩子的左孩子
if (p == pp->leftChild) {
rotateLL(grandfather);// LL单旋
// 调整颜色
// 现在的grandfather指向的是原来的父亲节点，grandfather的右孩子指向的是原祖父节点
grandfather->isRed = false;
grandfather->rightChild->isRed = true;
} else {// LRb的情况
rotateLR(grandfather);
// 调整颜色
// 现在的grandfather指向的是原来的新节点u，u的左孩子是原来的父亲节点pu，u的右孩子是原来的祖父节点gu
grandfather->isRed = false;
grandfather->rightChild->isRed = true;
}
break;// 无需继续向上进行处理
}
} else {// parent是grandfather的右孩子
// RYr(Y可以是L或R)的情况
RedBlackTreeNode<pair<K, E> > *uncle = grandfather->leftChild;// 找到grandfather的左孩子，可以称为叔叔
if (uncle && uncle->isRed == true) {// 如果叔叔存在且为红色
// 将父亲节点和其叔叔节点的颜色更改为黑色
pp->isRed = uncle->isRed = false;
// 只有在祖父节点不为根节点时，将祖父节点的颜色更改为红色
if (grandfather != root)
grandfather->isRed = true;
else // 如果祖父节点已经是根节点了，那么就直接终止循环，因为不可能再向上处理了
break;
// 继续往上处理
p = grandfather;
pp = p->parent;
} else {// uncle不存在或者uncle存在且为黑色
// 如果当前节点是其父亲节点的右孩子
// RRb的情况：右孩子的右孩子
if (p == pp->rightChild) {
rotateRR(grandfather);// RR单旋
// 调整颜色
// 现在的grandfather指向的是原来的父亲节点，grandfather的左孩子指向的是原祖父节点
grandfather->isRed = false;
grandfather->leftChild->isRed = true;
} else {// LRb的情况
rotateRL(grandfather);
// 调整颜色
// 现在的grandfather指向的是原来的新节点u，u的右孩子是原来的父亲节点pu，u的左孩子是原来的祖父节点gu
grandfather->isRed = false;
grandfather->leftChild->isRed = true;
}
break;// 无需继续向上进行处理
}
}
}
}
/*
* 删除元素
* 输入：const K theKey表示需要删除元素的键值
* 输出：void
* 时间复杂度：O(logn)，n表示节点个数
*/
template<class K, class E>
void RedBlackTree<K, E>::erase(K theKey) {
// 删除关键字等于theKey的数对
// 查找关键字为theKey的节点
RedBlackTreeNode<pair<K, E> > *p = root,
*pp = nullptr;
while (p != nullptr && p->element.first != theKey)
{
pp = p;
if (theKey < p->element.first)
p = p->leftChild;
else
p = p->rightChild;
}
if (p == nullptr){
cout << theKey << " not exist!" << endl;
return; // 不存在与关键字theKey匹配的数对
}
// 重新组织树结构
// 当p有两个孩子时的处理
if (p->leftChild != nullptr && p->rightChild != nullptr)
{
// 两个孩子
// 在P的左子树中寻找最大元素
RedBlackTreeNode<pair<K, E> > *s = p->leftChild,
*ps = p; // s的父节点
while (s->rightChild != nullptr)
{// 移动到更大的pair
ps = s;
s = s->rightChild;// 右孩子比较大
}
// 将最大元素s移到p
// p->element = s->element 的键值是 const
// 当最大值就是p的左孩子时，new的元素不能直接指向p的左孩子，而要指向p的左孩子的左孩子(此时p的左孩子没有右孩子)，因为到时候s会被delete掉,这个问题在后面的p至多有一个孩子那里解决的
RedBlackTreeNode<pair<K, E> >* q = nullptr;
// 值用s的值替换，颜色和其他指针的指向都是p的
q = new RedBlackTreeNode<pair<K, E> >(s->element, p->leftChild, p->rightChild, p->parent, p->isRed);
if(p->leftChild)
p->leftChild->parent = q;
if(p->rightChild)
p->rightChild->parent = q;
// pp是p的父节点
// 如果p没有父节点
if (pp == nullptr)
root = q;
else if (p == pp->leftChild)// 如果p是pp的左孩子
pp->leftChild = q;
else// 如果p是pp的右孩子
pp->rightChild = q;
// 如果s的父节点就是p，说明p节点的左子树只有左子树没有右子树
// 那么删除p后pp就是其父节点
if (ps == p) pp = q;
else pp = ps;// 反之ps是其父节点
delete p;
p = s;
}
// p至多只有一个孩子
// 把孩子的指针存放到c
RedBlackTreeNode<pair<K, E> > *c;
if (p->leftChild != nullptr)
c = p->leftChild;
else
c = p->rightChild;
// 删除p
bool isLeft = false;// 记录p节点是左孩子还是右孩子
if (p == root)
root = c;
else
{// p是pp的左孩子还是右孩子
if (p == pp->leftChild){
pp->leftChild = c;
// 更新一下c节点的父亲节点
if(c != nullptr)
c->parent = pp;
isLeft = true;
}
else{
pp->rightChild = c;
// 更新一下c节点的父亲节点
if(c != nullptr)
c->parent = pp;
}
}
treeSize--;
// 之前就找到了y节点的父亲节点pp
// 如果被删除节点是红色的，则红黑树还是平衡的；如果被删除节点是黑色的，则红黑树需要调整
if(p->isRed == false){
// 父亲节点不为空，说明还需要继续调整
while(pp){
// 如果c节点不为空，则需要判断c节点是左孩子还是右孩子
// 这个主要是用于第二轮调整平衡，也就是c节点此时不再是p的孩子节点
if(c){
if(c == pp->leftChild)
isLeft = true;
else
isLeft = false;
}
if(isLeft){
// 找到被删除节点的兄弟
RedBlackTreeNode<pair<K, E> > *v = pp->rightChild;
// 如果兄弟节点是黑色节点 Lb型
// 如果c和v都为空的话，那么不用调整平衡
if(!c && !v)
break;
if(!v->isRed){
// 如果v的左右孩子都是红色节点，Lb2型;或者v的左孩子是红色节点，Lb1(2)型
if(v->leftChild && v->leftChild->isRed){
rotateRL(pp);// OK1
pp->isRed = pp->leftChild->isRed;
pp->leftChild->isRed = false;
break;
}
else if(v->rightChild && v->rightChild->isRed){// 如果v的左孩子是红色节点，Lb1(1)型
rotateRR(pp);// OK1
pp->isRed = pp->leftChild->isRed;// 这个节点的颜色不变
pp->leftChild->isRed = false;// 原来的祖先节点的颜色变为黑色节点
v->rightChild->isRed = false;// 将v的左孩子更改为黑色节点
break;// 不需要继续调整了
}
else{// 如果v的左右孩子都是黑色节点，Lb0型
// pp是红色节点，改变pp为黑色节点，改变v为红色节点
if(pp->isRed){
pp->isRed = false;// OK1
v->isRed = true;
break;// 终止循环，不需要再继续调整了
}
else{// pp是黑色节点，将v节点改变为红色节点，然后将pp节点作为新的y节点，也就是程序中的p节点
v->isRed = true;//OK1
// 继续调整平衡
c = pp;
pp = c->parent;
}
}
}
else{// 如果兄弟节点是红色节点 Lr型，则兄弟节点一定有左右孩子
// 找到被删除节点的兄弟的左孩子
RedBlackTreeNode<pair<K, E> > *vL = v->leftChild;
// 如果vL的左右孩子都是红色节点，Lr2型 或者 如果v的左孩子是红色节点，Lr1(2)型
if(vL && vL->leftChild && vL->leftChild->isRed){
rotateLr1_2and2(pp);// OK1
pp->isRed = false;
break;
}
else if(vL && vL->rightChild && vL->rightChild->isRed){// 如果v的右孩子是红色节点，Lr1(1)型
rotateRL(pp);// OK1
if(vL->rightChild->leftChild)
vL->rightChild->leftChild->isRed = false;
break;
}
else{// 如果v的左右孩子都是黑色节点，Lr0型
rotateRR(pp);// OK1
pp->isRed = false;// 更改原来的v节点为黑色节点
if(pp->leftChild->rightChild)
pp->leftChild->rightChild->isRed = true;
break;
}
}
}
else{// 否则是R型
// 找到被删除节点的兄弟
RedBlackTreeNode<pair<K, E> > *v = pp->leftChild;
// 如果c和v都为空的话，那么树本身就是平衡的
if((!c && !v))
break;
// 如果兄弟节点是黑色节点 Rb型
if(!v->isRed){
// 如果v的左右孩子都是红色节点，Rb2型；或者v的右孩子是红色节点，Rb1(2)型
if(v->rightChild && v->rightChild->isRed){
rotateLR(pp);// OK1
pp->isRed = pp->rightChild->isRed;
pp->rightChild->isRed = false;
break;
}
else if(v->leftChild && v->leftChild->isRed){// 如果v的左孩子是红色节点，Rb1(1)型
rotateLL(pp);// OK1
pp->isRed = pp->rightChild->isRed;// 这个节点的颜色不变
pp->rightChild->isRed = false;// 原来的祖先节点的颜色变为黑色节点
v->leftChild->isRed = false;// 将v的左孩子更改为黑色节点
break;// 不需要继续调整了
}
else{// 如果v的左右孩子都是黑色节点，Rb0型
// pp是红色节点，改变pp为黑色节点，改变v为红色节点
if(pp->isRed){
pp->isRed = false;// OK1
v->isRed = true;
break;// 终止循环，不需要再继续调整了
}
else{// pp是黑色节点，将v节点改变为红色节点，然后将pp节点作为新的y节点，也就是程序中的p节点
// 这个没有找到合适的节点去测试
v->isRed = true;//OK1
c = pp;
pp = c->parent;
}
}
}
else{// 如果兄弟节点v是红色节点 Rr型，则兄弟节点v一定有左右孩子
// 找到被删除节点的兄弟的右孩子
RedBlackTreeNode<pair<K, E> > *vR = v->rightChild;
// 如果vR的左右孩子都是红色节点，Rr2型 或者 vR的右孩子是红色节点，Rr1(2)型 两个合起来就是vR的右孩子存在且是红色节点
// 两种操作都是一样的
if(vR && vR->rightChild && vR->rightChild->isRed){
rotateRr1_2and2(pp);// OK1
pp->isRed = false;
break;
}
else if(vR && vR->leftChild && vR->leftChild->isRed){// 如果vR的左孩子是红色节点，Rr1(1)型
rotateLR(pp);// OK1
if(vR->leftChild->rightChild)
vR->leftChild->rightChild->isRed = false;
break;
}
else{// 如果v的左右孩子都是黑色节点，Rr0型，没找到合适的树来测试
// 如果c节点是nullptr的话，树本来就是平衡的，不需要调整了
// OK1
rotateLL(pp);
pp->isRed = false;// 更改原来的v节点为黑色节点
if(pp->rightChild->leftChild)
pp->rightChild->leftChild->isRed = true;
break;
}
}
}
}
}
if(root && root->isRed == true)
root->isRed = false;
delete p;
}
//判断是否为红黑树
template<class K, class E>
bool RedBlackTree<K, E>::ISRBTree()
{
if (root == nullptr) //空树是红黑树
{
return true;
}
if (root->isRed == true)
{
cout << "error: root is red" << endl;
return false;
}
//找最左路径作为黑色结点数目的参考值
RedBlackTreeNode<pair<K, E> > *cur = root;
int BlackCount = 0;
while (cur)
{
if (cur->isRed == false)
BlackCount++;
cur = cur->leftChild;
}
int count = 0;
return _ISRBTree(root, count, BlackCount);
}
//判断是否为红黑树的子函数
template<class K, class E>
bool RedBlackTree<K, E>::_ISRBTree(RedBlackTreeNode<pair<K, E> > * cur, int count, int BlackCount)
{
if (cur == nullptr) //该路径已经走完了
{
if (count != BlackCount)
{
cout << "error: black nodes nums not equal" << endl;
return false;
}
return true;
}
if (cur->isRed == true && cur->parent->isRed == true)
{
cout << "error: red and red nodes together" << endl;
return false;
}
if (cur->isRed == false)
{
count++;
}
return _ISRBTree(cur->leftChild, count, BlackCount) && _ISRBTree(cur->rightChild, count, BlackCount);
}
// overload << for pair
template<class K, class E>
ostream &operator<<(ostream &out, const pair<K, E> &x) {
out << x.first << ":" << x.second;
return out;
}
template<class K, class E>
ostream &operator<<(ostream &out, const RedBlackTreeNode<pair<K, E>> &x) {
out << x.element.first << ":" << x.element.second << " isRed = " << x.isRed;
return out;
}
#endif //_35RED_BLACK_TREE_REDBLACKTREE_H
完整可编译运行代码见仓库：GitHub - Jasmine-up/Data-Structures-Algorithms-and-Applications/_3matrix。
如有问题请在评论区指出。另外，Github仓库会根据我的学习情况持续更新，欢迎大家点star，谢谢。
文章来源:https://blog.csdn.net/weixin_44410704/article/details/135490013
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！