锐客网

  1. 首页 > 生活百科 > it技术 > >

c++|红黑树，插入和删除，基于C++的实现

数据结构链表c++b树

接上篇红黑树，插入和删除，更好的理解 ，在这篇文章中，我不会过多介绍理解部分，因为上篇文章已经说的差不多了。接下来我将基于C++来实现红黑树，同样的，欢迎大家在评论区提出疑问和指出错误！
首先，我们需要构建红黑树的结点类，这个类里面，要有key值，value值，结点的颜色，还要有指向左右子结点的结点类指针，最后加上指向父结点的结点类指针。我这里，将key值设为int类型，value值设为string类型，结点的颜色用bool类型表示，也就是true表示红色，false表示黑色。

class Node_RB { public: int m_key; string m_value; bool m_color; Node_RB* m_left; Node_RB* m_right; Node_RB* m_parent; Node_RB(int k, string v,bool c,Node_RB* l,Node_RB* r,Node_RB* p) { m_key = k; m_value = https://www.it610.com/article/v; m_color = c; m_left = l; m_right = r; m_parent = p; } };

接下来，就开始写我们的红黑树类了，这个类的成员变量和二叉树差不多，也有root根结点和表示结点数量的m_n。同时，我们知道，在插入和删除中，我们都会频繁用到左旋和右旋，所以，也提前写好这两个函数。注释部分我也参考了阿里P7大佬手撕红黑树全套教程，已经写的很详细了，也就不再过多赘述。
class RB_tree { public: Node_RB* root; int m_n; RB_tree() { m_n = 0; root = NULL; } /*左旋,以p为支点，注意，要记得考虑p的父节点，要加上p的父节点怎么连 ppr /\/\ pl pr=>prr /\/\ rl rrpl rl */ void left_rotate(Node_RB* p) { // temp = pr; p的右结点 = rl；rl的父节点设成p； pr的父节点 = p的父节点；p的父节点连pr； p的父节点 = pr； pr的左结点 = p； Node_RB* temp = p->m_right; //就是pr p->m_right = temp->m_left; if (p->m_right != NULL) { //假如rl不是空，那就要设置rl的父节点为p p->m_right->m_parent = p; } temp->m_parent = p->m_parent; //p是它父节点的左结点还是右节点，或者它就是root if (p->m_parent == NULL) { //p是根节点 root = temp; } else if (p->m_parent->m_left == p) { //p是左结点 p->m_parent->m_left = temp; } else if (p->m_parent->m_right == p) { //p是右节点 p->m_parent->m_right = temp; } p->m_parent = temp; temp->m_left = p; } /*右旋 以p为支点 ppl /\/\ plpr=>rlp /\/\ rlrrrr pr */ void right_rotate(Node_RB* p) { Node_RB* temp = p->m_left; //pl p->m_left = temp->m_right; if (p->m_left != NULL) { p->m_left->m_parent = p; }temp->m_parent = p->m_parent; if (p->m_parent == NULL) { root = temp; } else if (p->m_parent->m_left == p) { p->m_parent->m_left = temp; } else if (p->m_parent->m_right == p) { p->m_parent->m_right = temp; }temp->m_right = p; p->m_parent = temp; } }

开始我们最重要的两部分之一了：插入
回顾一下上一篇我总结的：
1.空树：作为根节点，变为黑色false
2.存在已有的key，换值即可
3.父节点为黑色结点：直接添加即可，无需改变
前三种情况已经处理好了，adjust函数处理后面的情况
4.父节点为红色：（那爷爷结点一定是黑色了，同时叔叔结点要么没有，要么就是红色，如果叔叔结点为黑色，那就不平衡了，叔叔那边深度就会大）
1.叔叔结点不存在
插入结点和父节点在同一侧
都在左侧，以爷爷节点为支点右旋，然后父节点改为黑色，爷爷结点改为红色
都在右侧，以爷爷节点为支点左旋，变色同上
插入结点和父节点不在同一侧
父节点在左侧，以父节点为支点左旋，转换为上面同一侧的情况,这里改颜色的是自己和爷爷，要注意的是，旋转后，谁是父节点，谁是爷爷结点
父节点在右侧，以父节点为支点右旋，转换为上面同一侧的情况
2.叔叔结点为红色，这种情况有可能就要从下往上迭代了，因为这让爷爷结点变红了，就可能出现爷爷的父节点也是红色
只需要变色，爷爷结点变红，父节点和叔叔结点变黑
void put(int k, string v) { Node_RB* n = root; Node_RB* np = root; if (n == NULL) { //空树插入第一个结点 root = new Node_RB(k, v, false, NULL, NULL, NULL); m_n = 1; return; } //先找一下这个结点在哪 while (n != NULL) { np = n; //记录父节点 if (n->m_key == k) { //存在已有的key，直接换值即可 n->m_value = https://www.it610.com/article/v; return; } else if (k < n->m_key) { n = n->m_left; } else { n = n->m_right; } } //先让这个插入结点的父节点指对，指向np Node_RB* n_new = new Node_RB(k, v, true, NULL, NULL, np); //判断这个结点是在np的左边还是右边 if (k < np->m_key) { np->m_left = n_new; } else { np->m_right = n_new; } //判断父节点是不是黑的 if (np->m_color == false) { m_n++; return; } else { adjust(n_new); m_n++; return; } }void adjust(Node_RB* n) { //循环，n的父节点不是黑结点，这个主要是为了叔叔结点是红色这一种情况,而且循环到n自己就是根结点就可以退出循环了 while (n != root && n->m_parent->m_color != false) { if (n->m_parent->m_parent->m_left == n->m_parent) { //父节点是爷爷结点的左结点，那就考虑叔叔结点有无，没有的话，考虑插入节点和父节点在不在同一侧 if (n->m_parent->m_parent->m_right == NULL) { //没有叔叔结点 if (n->m_parent->m_left == n) { //插入结点和父节点都是左节点,最好先变色，再旋转，不然旋转完，就不太好分清谁是父节点谁是插入结点了 n->m_parent->m_color = false; n->m_parent->m_parent->m_color = true; right_rotate(n->m_parent->m_parent); //这里n->parent颜色是黑色的了，就会退出循环 } else { //插入结点和父节点不在同一侧 n->m_color = false; n->m_parent->m_parent->m_color = true; left_rotate(n->m_parent); //这里原来的父结点已经变成插入结点的左子结点了，所以接下来要右旋，是要以原来的爷爷结点为支点 //也就是现在这个n的父节点 right_rotate(n->m_parent); n = n->m_left; //这一步是为了退出循环，这样n的父节点（其实就是原来的n）就是黑色的了 } } else { //叔叔结点为红色 n->m_parent->m_parent->m_color = true; n->m_parent->m_parent->m_right->m_color = false; n->m_parent->m_color = false; //以爷爷为插入结点进行新一轮循环，或递归，假如爷爷的父节点是红的，就会继续循环，否则就会退出循环 n = n->m_parent->m_parent; } } else { //父节点是右节点 if (n->m_parent->m_parent->m_left == NULL) { //没有叔叔结点 if (n->m_parent->m_right == n) { //和父节点一样在右侧 n->m_parent->m_color = false; n->m_parent->m_parent->m_color = true; left_rotate(n->m_parent->m_parent); } else { //不在同一侧 n->m_color = false; n->m_parent->m_parent->m_color = true; right_rotate(n->m_parent); left_rotate(n->m_parent); n = n->m_right; } } else { //叔叔结点为红色 n->m_parent->m_parent->m_color = true; n->m_parent->m_parent->m_left->m_color = false; n->m_parent->m_color = false; n = n->m_parent->m_parent; } } } //循环完了要记得把root设成黑色 root->m_color = false; }

最后是比较麻烦的删除
同样的，回顾一下上一篇总结的思路
【c++|红黑树，插入和删除，基于C++的实现】删除结点，总共三种情况
1.删除结点有两个子结点
这种情况都会转换，通过找它的后继（或者前驱）结点，然后把后继结点的key和value替换掉删除结点，最后将问题转换为删除后继结点即可
并且，后继结点要么就是叶节点，要么就是只有一个子结点
2.删除结点只有一个子结点
这种情况也很简单，只会出现一种情况，就是结点为黑，有一个红色的子结点，如果是后继结点，那只可能是右子结点
因为其他情况，在平衡时不存在，红红不行，黑黑，红黑都会导致左右不平衡
让子结点代替要删掉的结点，并把颜色换成黑色即可
3.删除结点是叶节点
这种情况分两种，红色还是黑色
1.红色，直接删除
2.黑色，很麻烦，再写一个函数来专门处理这种情况
//这个函数用来找到这个key的结点 Node_RB* find(int k) { Node_RB* n = root; if (n == NULL) { cout << "no key" << endl; return n; }while (n != NULL) { if (k < n->m_key) { n = n->m_left; } else if (k > n->m_key) { n = n->m_right; } else { return n; } } cout << " no key!"<m_right != NULL) { //先看看有没有右子树，当前情况是一定有的 n = n->m_right; //然后循环找最左边的点 while (n->m_left != NULL) { n = n->m_left; } return n; //找到了这个最左边的点，返回 } else { //没有右边子树,要是根结点，就不用找了，否则就要往上找了 //就是当n是父节点的左结点时，就说明这个父节点就是所需要的后继结点 while (n != NULL && n == n->m_parent->m_right) { n = n->m_parent; } return n->m_parent; } }//删除结点，并返回此结点的value string delete_node(int k) { Node_RB* n = find(k); if (n != NULL) { //找到了要删除的结点 if (n->m_left != NULL && n->m_right != NULL) { //这个结点有两个子结点,所以先找到它的后继结点,让后继结点的key和value覆盖掉原来n的 //将问题转换为删除后继结点，只有一个子结点或者没有子结点 Node_RB* n_back = back_node(n); n->m_key = n_back->m_key; string temp = n->m_value; n->m_value = https://www.it610.com/article/n_back->m_value; n_back->m_value = https://www.it610.com/article/temp; n = n_back; }//判断这个结点是不是只有一个子结点，并且上面一个if已经把有两个子结点的情况去除掉了 if (n->m_left != NULL || n->m_right != NULL) { Node_RB* ns = NULL; if (n->m_left != NULL) { //有左红子结点,让子结点代替删除结点n ns = n->m_left; } else { //有右红子结点 ns = n->m_right; }ns->m_parent = n->m_parent; if (n->m_parent == NULL) { //n就是root root = ns; } else if (n == n->m_parent->m_left) { //n是左结点 n->m_parent->m_left = ns; } else { //n是右结点 n->m_parent->m_right = ns; }ns->m_color = false; string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } else if (n->m_parent == NULL) { //n就是root，并且没有子结点 string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } else { //n是叶节点 if (n->m_color == true) { //假如是红结点，那直接删除即可 if (n->m_parent->m_left == n) { n->m_parent->m_left = NULL; } else { n->m_parent->m_right = NULL; } string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } else { //最麻烦的情况，黑色的叶节点，再写一个函数来平衡 //这种情况就是先调整平衡,再删除 balance_bnode(n); //调整完后，再同样地删除 if (n->m_parent->m_left == n) { n->m_parent->m_left = NULL; } else { n->m_parent->m_right = NULL; } string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } }} else { return "no key!"; } }

下面要单独处理删除结点事黑色叶节点情况的函数
我会基于这个思路：
总的来说，因为删了黑色的，所以肯定就会不平衡了,这里通过找兄弟结点借来平衡,并且因为是黑色叶结点，所以肯定会有兄弟结点的。
意思就是，假设，这个结点是要被删掉的左黑叶结点，那就需要通过左旋，让父节点下来代替它（不管父节点原来什么颜色，都变成它的颜色——黑），同时，兄弟结点（黑）上来代替父亲（变成父亲原来的颜色），并且，兄弟结点的右子红结点变黑维持平衡。
其他情况都会转换成这种情况
但要是兄弟结点也是黑色叶子结点，那就是兄弟结点没有红色子结点，也就是没得借了
要注意的是，这里的兄弟，指的是2-3-4树里的兄弟，所以红黑树里的红色的兄弟结点，是不对的，要通过旋转，让这个红色兄弟的黑子结点变成删除结点的兄弟结点，具体见上一篇
0.兄弟结点是红色，通过旋转，变色，让兄弟结点是黑色
1.兄弟结点可以借，就是有红色的子结点
1.兄黑，子两红
2.兄黑，子左红
3.兄黑，子右红
2.兄弟结点没得借，就是兄弟结点是黑色叶节点
1.父结点是红色，那直接父节点换成黑色，兄结点换成红色即可
2.父节点是黑色，这个就麻烦了，不可避免的子树黑色深度要减1，就需要循环或递归，一层层往上直到根结点不断变色
void balance_bnode(Node_RB* n) { //这里应该不用担心形参改变会影响实参，这是值传递,虽然这个while循环里有改变n while (n != root) { //先分是左节点还是右节点 if (n->m_parent->m_left == n) { //n是左结点 //先找到兄弟结点 Node_RB* nb = n->m_parent->m_right; //判断它是不是红的，是红的就要经过操作让它的子黑结点，变成新的兄弟结点 if (nb->m_color == true) { nb->m_color = false; nb->m_parent->m_color = true; left_rotate(nb->m_parent); //设置新的兄弟结点 nb = n->m_parent->m_right; } //找到兄弟结点之后，就该判断它有没有子结点了，也就是能不能借了 if (nb->m_left == NULL && nb->m_right == NULL) { //兄弟结点也是黑色叶子结点，不能借 //不管哪种情况，兄弟结点都是变成红色 nb->m_color = true; if (n->m_parent->m_color == true) { //1.父节点是红色 n->m_parent->m_color = false; n = root; //这是为了退出循环 } else { //2.父节点是黑色 //那就需要以父结点变成n再循环一次了,当然，假如父节点就是根节点，那就不用循环了 n = n->m_parent; } } else { //兄弟结点有子结点，可以借，那就将情况全部变为有右子红的情况（子两红属于有右子红） if (nb->m_right == NULL) { //兄弟结点没有右子结点，只有左子结点,那就需要通过右旋，让它有右子结点 nb->m_color = true; nb->m_left->m_color = false; right_rotate(nb); //现在nb变成那个右红子结点了，让它的父节点变成新的兄弟结点 nb = nb->m_parent; } //现在情况已经是有右子红了，需要将，即将代替父节点的兄弟结点换成父节点的颜色， //即将代替删除结点n的父节点换成n的颜色,黑 //兄弟结点的右子红会上去，就要变成黑色来保持平衡 nb->m_color = nb->m_parent->m_color; nb->m_parent->m_color = false; nb->m_right->m_color = false; //然后以父节点左旋 left_rotate(n->m_parent); n = root; //为了退出循环 } } else { //n是右结点 //先找到兄弟结点 Node_RB* nb = n->m_parent->m_left; //判断它是不是红的，是红的就要经过操作让它的子黑结点，变成新的兄弟结点 if (nb->m_color == true) { nb->m_color = false; nb->m_parent->m_color = true; right_rotate(nb->m_parent); //设置新的兄弟结点 nb = n->m_parent->m_left; } //找到兄弟结点之后，就该判断它有没有子结点了，也就是能不能借了 if (nb->m_left == NULL && nb->m_right == NULL) { //兄弟结点也是黑色叶子结点，不能借 //不管哪种情况，兄弟结点都是变成红色 nb->m_color = true; if (n->m_parent->m_color == true) { //1.父节点是红色 n->m_parent->m_color = false; n = root; //这是为了退出循环 } else { //2.父节点是黑色 //那就需要以父结点变成n再循环一次了,当然，假如父节点就是根节点，那就不用循环了 n = n->m_parent; } } else { //兄弟结点有子结点，可以借，那就将情况全部变为有左子红的情况（子两红属于有左子红） if (nb->m_left == NULL) { //兄弟结点没有左子结点，只有右子结点,那就需要通过左旋，让它有左子结点 nb->m_color = true; nb->m_right->m_color = false; left_rotate(nb); //现在nb变成那个左红子结点了，让它的父节点变成新的兄弟结点 nb = nb->m_parent; } //现在情况已经是有左子红了，需要将，即将代替父节点的兄弟结点换成父节点的颜色， //即将代替删除结点n的父节点换成n的颜色,黑 //兄弟结点的左子红会上去，就要变成黑色来保持平衡 nb->m_color = nb->m_parent->m_color; nb->m_parent->m_color = false; nb->m_left->m_color = false; //然后以父节点you旋 right_rotate(n->m_parent); n = root; //为了退出循环} } } }

现在红黑树的插入和删除代码已经写完了，我们来测试一下。
我用前序遍历输出一下这棵树，同时包括每个结点的颜色
void pre_print() { queue q1; queue q2; pre_print(root,q1,q2); int cnt = q1.size(); for (int i = 0; i < cnt; i++) { cout << q1.front()<<"+"< &q1, queue &q2) { if (n == NULL) { return; } q1.push(n->m_key); q2.push(n->m_color); if (n->m_left!= NULL) { pre_print(n->m_left,q1,q2); } if (n->m_right != NULL) { pre_print(n->m_right, q1,q2); } return; }

测试一下，我依次输入5，1，8，18，6，13，5，9，2，输出一次，接着删掉6再输出一次
void test01() { RB_tree rb; rb.put(5, "5"); rb.put(1, "1"); rb.put(8, "8"); rb.put(18, "18"); rb.put(6, "6"); rb.put(13, "13"); rb.put(5, "100"); rb.put(9, "9"); rb.put(2, "2"); cout << rb.get_size()<

输出结果（前序遍历）：
c++|红黑树，插入和删除，基于C++的实现
文章图片

在红黑树生成网站生成的结果：红黑树
插入：
c++|红黑树，插入和删除，基于C++的实现
文章图片

删除key为6的结点：
c++|红黑树，插入和删除，基于C++的实现
文章图片


结果符合预期。
最后的最后，如果大家有什么疑问或者发现了错误，欢迎评论区互动，希望这篇文章对大家有所帮助！
完整代码如下：
#include #include using namespace std; #includeclass Node_RB { public: int m_key; string m_value; bool m_color; Node_RB* m_left; Node_RB* m_right; Node_RB* m_parent; Node_RB(int k, string v,bool c,Node_RB* l,Node_RB* r,Node_RB* p) { m_key = k; m_value = https://www.it610.com/article/v; m_color = c; m_left = l; m_right = r; m_parent = p; } }; class RB_tree { public: Node_RB* root; int m_n; RB_tree() { m_n = 0; root = NULL; } void left_rotate(Node_RB* p) { // temp = pr; p的右结点 = rl；rl的父节点设成p； pr的父节点 = p的父节点；p的父节点连pr； p的父节点 = pr； pr的左结点 = p； Node_RB* temp = p->m_right; //就是pr p->m_right = temp->m_left; if (p->m_right != NULL) { //假如rl不是空，那就要设置rl的父节点为p p->m_right->m_parent = p; } temp->m_parent = p->m_parent; //p是它父节点的左结点还是右节点，或者它就是root if (p->m_parent == NULL) { //p是根节点 root = temp; } else if (p->m_parent->m_left == p) { //p是左结点 p->m_parent->m_left = temp; } else if (p->m_parent->m_right == p) { //p是右节点 p->m_parent->m_right = temp; } p->m_parent = temp; temp->m_left = p; } void right_rotate(Node_RB* p) { Node_RB* temp = p->m_left; //pl p->m_left = temp->m_right; if (p->m_left != NULL) { p->m_left->m_parent = p; }temp->m_parent = p->m_parent; if (p->m_parent == NULL) { root = temp; } else if (p->m_parent->m_left == p) { p->m_parent->m_left = temp; } else if (p->m_parent->m_right == p) { p->m_parent->m_right = temp; }temp->m_right = p; p->m_parent = temp; } bool get_color(Node_RB* n) { return n == NULL ? false : n->m_color; } int get_size() { return m_n; } void put(int k, string v) { Node_RB* n = root; Node_RB* np = root; if (n == NULL) { //空树插入第一个结点 root = new Node_RB(k, v, false, NULL, NULL, NULL); m_n = 1; return; } //先找一下这个结点在哪 while (n != NULL) { np = n; //记录父节点 if (n->m_key == k) { //存在已有的key，直接换值即可 n->m_value = https://www.it610.com/article/v; return; } else if (k < n->m_key) { n = n->m_left; } else { n = n->m_right; } } //先让这个插入结点的父节点指对，指向np Node_RB* n_new = new Node_RB(k, v, true, NULL, NULL, np); //判断这个结点是在np的左边还是右边 if (k < np->m_key) { np->m_left = n_new; } else { np->m_right = n_new; } //判断父节点是不是黑的 if (np->m_color == false) { m_n++; return; } else { adjust(n_new); m_n++; return; } } void adjust(Node_RB* n) { //循环，n的父节点不是黑结点，这个主要是为了叔叔结点是红色这一种情况,而且循环到n自己就是根结点就可以退出循环了 while (n != root && n->m_parent->m_color != false) { if (n->m_parent->m_parent->m_left == n->m_parent) { //父节点是爷爷结点的左结点，那就考虑叔叔结点有无，没有的话，考虑插入节点和父节点在不在同一侧 if (n->m_parent->m_parent->m_right == NULL) { //没有叔叔结点 if (n->m_parent->m_left == n) { //插入结点和父节点都是左节点,最好先变色，再旋转，不然旋转完，就不太好分清谁是父节点谁是插入结点了 n->m_parent->m_color = false; n->m_parent->m_parent->m_color = true; right_rotate(n->m_parent->m_parent); //这里n->parent颜色是黑色的了，就会退出循环 } else { //插入结点和父节点不在同一侧 n->m_color = false; n->m_parent->m_parent->m_color = true; left_rotate(n->m_parent); //这里原来的父结点已经变成插入结点的左子结点了，所以接下来要右旋，是要以原来的爷爷结点为支点 //也就是现在这个n的父节点 right_rotate(n->m_parent); n = n->m_left; //这一步是为了退出循环，这样n的父节点（其实就是原来的n）就是黑色的了 } } else { //叔叔结点为红色 n->m_parent->m_parent->m_color = true; n->m_parent->m_parent->m_right->m_color = false; n->m_parent->m_color = false; //以爷爷为插入结点进行新一轮循环，或递归，假如爷爷的父节点是红的，就会继续循环，否则就会退出循环 n = n->m_parent->m_parent; } } else { //父节点是右节点 if (n->m_parent->m_parent->m_left == NULL) { //没有叔叔结点 if (n->m_parent->m_right == n) { //和父节点一样在右侧 n->m_parent->m_color = false; n->m_parent->m_parent->m_color = true; left_rotate(n->m_parent->m_parent); } else { //不在同一侧 n->m_color = false; n->m_parent->m_parent->m_color = true; right_rotate(n->m_parent); left_rotate(n->m_parent); n = n->m_right; } } else { //叔叔结点为红色 n->m_parent->m_parent->m_color = true; n->m_parent->m_parent->m_left->m_color = false; n->m_parent->m_color = false; n = n->m_parent->m_parent; } } } //循环完了要记得把root设成黑色 root->m_color = false; } void pre_print() { queue q1; queue q2; pre_print(root,q1,q2); int cnt = q1.size(); for (int i = 0; i < cnt; i++) { cout << q1.front()<<"+"< &q1, queue &q2) { if (n == NULL) { return; } q1.push(n->m_key); q2.push(n->m_color); if (n->m_left!= NULL) { pre_print(n->m_left,q1,q2); } if (n->m_right != NULL) { pre_print(n->m_right, q1,q2); } return; } /*void find(int k) { find(root,k); }*/ Node_RB* find(int k) { Node_RB* n = root; if (n == NULL) { cout << "no key" << endl; return n; }while (n != NULL) { if (k < n->m_key) { n = n->m_left; } else if (k > n->m_key) { n = n->m_right; } else { return n; } } cout << " no key!"<m_left != NULL && n->m_right != NULL) { //这个结点有两个子结点,所以先找到它的后继结点,让后继结点的key和value覆盖掉原来n的 //将问题转换为删除后继结点，只有一个子结点或者没有子结点 Node_RB* n_back = back_node(n); n->m_key = n_back->m_key; string temp = n->m_value; n->m_value = https://www.it610.com/article/n_back->m_value; n_back->m_value = https://www.it610.com/article/temp; n = n_back; }//判断这个结点是不是只有一个子结点，并且上面一个if已经把有两个子结点的情况去除掉了 if (n->m_left != NULL || n->m_right != NULL) { Node_RB* ns = NULL; if (n->m_left != NULL) { //有左红子结点,让子结点代替删除结点n ns = n->m_left; } else { //有右红子结点 ns = n->m_right; }ns->m_parent = n->m_parent; if (n->m_parent == NULL) { //n就是root root = ns; } else if (n == n->m_parent->m_left) { //n是左结点 n->m_parent->m_left = ns; } else { //n是右结点 n->m_parent->m_right = ns; }ns->m_color = false; string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } else if (n->m_parent == NULL) { //n就是root，并且没有子结点 string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } else { //n是叶节点 if (n->m_color == true) { //假如是红结点，那直接删除即可 if (n->m_parent->m_left == n) { n->m_parent->m_left = NULL; } else { n->m_parent->m_right = NULL; } string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } else { //最麻烦的情况，黑色的叶节点，再写一个函数来平衡 //这种情况就是先调整平衡,再删除 balance_bnode(n); //调整完后，再同样地删除 if (n->m_parent->m_left == n) { n->m_parent->m_left = NULL; } else { n->m_parent->m_right = NULL; } string old_value = https://www.it610.com/article/n->m_value; delete n; m_n--; return old_value; } }} else { return "no key!"; } } void balance_bnode(Node_RB* n) { //这里应该不用担心形参改变会影响实参，这是值传递,虽然这个while循环里有改变n while (n != root) { //先分是左节点还是右节点 if (n->m_parent->m_left == n) { //n是左结点 //先找到兄弟结点 Node_RB* nb = n->m_parent->m_right; //判断它是不是红的，是红的就要经过操作让它的子黑结点，变成新的兄弟结点 if (nb->m_color == true) { nb->m_color = false; nb->m_parent->m_color = true; left_rotate(nb->m_parent); //设置新的兄弟结点 nb = n->m_parent->m_right; } //找到兄弟结点之后，就该判断它有没有子结点了，也就是能不能借了 if (nb->m_left == NULL && nb->m_right == NULL) { //兄弟结点也是黑色叶子结点，不能借 //不管哪种情况，兄弟结点都是变成红色 nb->m_color = true; if (n->m_parent->m_color == true) { //1.父节点是红色 n->m_parent->m_color = false; n = root; //这是为了退出循环 } else { //2.父节点是黑色 //那就需要以父结点变成n再循环一次了,当然，假如父节点就是根节点，那就不用循环了 n = n->m_parent; } } else { //兄弟结点有子结点，可以借，那就将情况全部变为有右子红的情况（子两红属于有右子红） if (nb->m_right == NULL) { //兄弟结点没有右子结点，只有左子结点,那就需要通过右旋，让它有右子结点 nb->m_color = true; nb->m_left->m_color = false; right_rotate(nb); //现在nb变成那个右红子结点了，让它的父节点变成新的兄弟结点 nb = nb->m_parent; } //现在情况已经是有右子红了，需要将，即将代替父节点的兄弟结点换成父节点的颜色， //即将代替删除结点n的父节点换成n的颜色,黑 //兄弟结点的右子红会上去，就要变成黑色来保持平衡 nb->m_color = nb->m_parent->m_color; nb->m_parent->m_color = false; nb->m_right->m_color = false; //然后以父节点左旋 left_rotate(n->m_parent); n = root; //为了退出循环 } } else { //n是右结点 //先找到兄弟结点 Node_RB* nb = n->m_parent->m_left; //判断它是不是红的，是红的就要经过操作让它的子黑结点，变成新的兄弟结点 if (nb->m_color == true) { nb->m_color = false; nb->m_parent->m_color = true; right_rotate(nb->m_parent); //设置新的兄弟结点 nb = n->m_parent->m_left; } //找到兄弟结点之后，就该判断它有没有子结点了，也就是能不能借了 if (nb->m_left == NULL && nb->m_right == NULL) { //兄弟结点也是黑色叶子结点，不能借 //不管哪种情况，兄弟结点都是变成红色 nb->m_color = true; if (n->m_parent->m_color == true) { //1.父节点是红色 n->m_parent->m_color = false; n = root; //这是为了退出循环 } else { //2.父节点是黑色 //那就需要以父结点变成n再循环一次了,当然，假如父节点就是根节点，那就不用循环了 n = n->m_parent; } } else { //兄弟结点有子结点，可以借，那就将情况全部变为有左子红的情况（子两红属于有左子红） if (nb->m_left == NULL) { //兄弟结点没有左子结点，只有右子结点,那就需要通过左旋，让它有左子结点 nb->m_color = true; nb->m_right->m_color = false; left_rotate(nb); //现在nb变成那个左红子结点了，让它的父节点变成新的兄弟结点 nb = nb->m_parent; } //现在情况已经是有左子红了，需要将，即将代替父节点的兄弟结点换成父节点的颜色， //即将代替删除结点n的父节点换成n的颜色,黑 //兄弟结点的左子红会上去，就要变成黑色来保持平衡 nb->m_color = nb->m_parent->m_color; nb->m_parent->m_color = false; nb->m_left->m_color = false; //然后以父节点you旋 right_rotate(n->m_parent); n = root; //为了退出循环} } } } Node_RB* back_node(Node_RB* n) { if (n == NULL) { return NULL; } else if (n->m_right != NULL) { //先看看有没有右子树，当前情况是一定有的 n = n->m_right; //然后循环找最左边的点 while (n->m_left != NULL) { n = n->m_left; } return n; //找到了这个最左边的点，返回 } else { //没有右边子树,要是根结点，就不用找了，否则就要往上找了 //就是当n是父节点的左结点时，就说明这个父节点就是所需要的后继结点 while (n != NULL && n == n->m_parent->m_right) { n = n->m_parent; } return n->m_parent; } }}; void test01() { RB_tree rb; rb.put(5, "5"); rb.put(1, "1"); rb.put(8, "8"); rb.put(18, "18"); rb.put(6, "6"); rb.put(13, "13"); rb.put(5, "100"); rb.put(9, "9"); rb.put(2, "2"); cout << rb.get_size()<


    推荐阅读


    上一篇：kubernetes|Kubernetes K8S之Helm部署EFK日志分析系统

    下一篇：vim|linux的基本开发工具（vim，gcc，gdb，make/Makefile）