devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

c++代码手撕红黑树_c++ curfit

作者：小蓝xlanll | 2024-03-16 01:23:54

赞

踩

c++ curfit

企业里永远是技术驱动理论发展

比起理解红黑树的原理，更重要的是理解红黑树的应用场景，因为某些应用场景的需要，红黑树才会应运而生。

红黑树的特点：

插入，删除，查找都是O(logn)的复杂度。

红黑树的应用：

  • epoll的实现，内核会在内存开辟一个空间存放epoll的红黑树，并将每个epollfd加入到红黑树中，一般epoll会设置LT水平触发，当网卡有数据到来，可读缓冲区不为空，会触发回调EPOLLIN事件，而之前注册了对EPOLLIN事件感兴趣的socketfd会有专门的队列存储，内核会遍历队列搜寻对应的socketfd，因为在红黑树里找有近似O(logn)的时间复杂度，所以10亿个socket也只需要20次查找。

  • 进程调度，内核CFS队列，以红黑树的形式存储进程信息。

  • 有的hashtable（记得是java），当冲突时不以链表来组织重复元素，而是以红黑树的形式来组织。

  • 内存管理，比如空闲链表freelist可以通过红黑树来组织，这样malloc的时候要找到符合大小的内存块，如果不是firstfit的原则，而是全局最优大小原则，想找到适合的内存块就可以通过红黑树来找。

  • Nginx的Timer事件管理。

红黑树定义

写代码之前先写一下红黑树的规则吧

  1. 每个颜色不是红就是黑。

  2. 根节点必黑

  3. 叶子节点必黑

  4. 红色节点的左右孩子都为黑

  5. 每个节点到其叶子节点（nil）的所有路径上的黑色节点数量都一样

我的理解：从任一节点到叶子结点的路径上，路径的元素必然有黑色节点，而路径的长度则取决于路径上红色节点的数量，最短的路径上，所有节点都是黑色，这种情况下，查找效率为真实的O(logn)，和严格平衡的AVL树一致。而如果在刚刚的最短路径上，也就是所有黑色节点的中间插入红色节点，这样是不会打破红黑树的平衡的(规则5)，此时便是最长路径，查找效率为2logn，但依然和logn在同一数量级，因此，红黑树的查找效率可以看做是(Ologn)，同时比AVL树拥有更高的插入和删除效率。

红黑树代码框架

  1. //-既然标题是c++，那么就写成满满的c++风格吧
  2. using Color = bool;//-颜色因为只有红或者黑，选择bool类型
  3. using KEY_TYPE = int;//-为了更好理解红黑树，就不写成模板类了，所以首选万年int（笑~）
  4. using VALUE_TYPE = int;//-同理
  5.  
  6. //-全局静态红黑变量
  7. static const Color red = false;
  8. static const Color black  = true;
  9.  
  10. //-红黑树的节点特点，有color，有parent
  11. class RBtree_node{
  12. public:
  13.     Color color;
  14.     RBtree_node * parent;
  15.     RBtree_node * left;
  16.     RBtree_node * right;
  17.  
  18.     KEY_TYPE key;//-后期如果想解耦合，可以将key和value抽离出去
  19.     VALUE_TYPE value;
  20.     RBtree_node(Color color_):color(color_),parent(nullptr),left(nullptr),right(nullptr),key(-99999){}
  21.     RBtree_node(Color color_, KEY_TYPE key_,RBtree_node * nil):
  22.                       color(color_),parent(nil),left(nil),right(nil),key(key_){}
  23. };
  24.  
  25.  
  26. class RBtree{
  27. private:
  28. //-红黑树数据成员：其中nil的意义在于，因为红黑树的所有叶子节点都是黑色的，所以可以将所有临近末尾的节点，
  29. //-都连接到这一个叶子结点nil上，同理，root的parent也可以连接到nil上，形成一个dummy空节点
  30.     RBtree_node * root;
  31.     RBtree_node * nil;
  32. public :
  33. //-以下实现了红黑树常用接口：
  34.     //-构造函数
  35.     RBtree(){
  36.         nil = new RBtree_node(black);//-为所有叶子节点nil初始化，颜色为黑色
  37.         root = nil;//-红黑树为空的时候，让nil作为root
  38.     }
  39.     //-左旋
  40.     void leftRotate(RBtree_node *left_node);
  41.  
  42.     //- 右旋
  43.     void rightRotate(RBtree_node * right_node);
  44.  
  45.     //-插入key
  46.     void insertNode(KEY_TYPE key);
  47.  
  48.     //-修复插入
  49.     void fixInsert(RBtree_node * node);
  50.  
  51.     //-查找某个key的节点
  52.     RBtree_node* searchNode(KEY_TYPE key);
  53.  
  54.     //-查找某个节点的中序后继
  55.     RBtree_node* successor(RBtree_node * node);
  56.  
  57.     //-删除key
  58.     void deleteNode(KEY_TYPE key);
  59.  
  60.     //-修复删除
  61.     void fixDelete(RBtree_node * node);
  62.  
  63.     //-层序遍历打印红黑树
  64.     void print();
  65.  
  66.     //-打印中序遍历
  67.     void printMiddle(RBtree_node * node);
  68.     
  69. };

相关视频推荐

5种红黑树的用途，从应用到内核场景的优缺点

源码阅读：STL 红黑树、散列表的实现

c/c++后端开发需要学些什么？迭代13次的c/c++后端开发学习路线分享

免费学习地址：c/c++ linux服务器开发/后台架构师

需要C/C++ Linux服务器架构师学习资料加qun812855908获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享

接下来将接口一一实现：

红黑树节点左旋右旋：

实现参照该图，至于学习方法也没啥捷径，只能把这个结构图和变换方式深深印刻在脑海里。

手撕代码的时候想象一下还是容易写的，如果觉得这样很累就纸上画个草图。

由于左旋和右旋是对称的，所以规则只需要记一半。

​图1 左旋右旋

  1. //-左旋
  2. void RBtree::leftRotate(RBtree_node *left_node){
  3.     RBtree_node * right_node = left_node->right;
  4.     //-右节点的左枝条接在左节点的右枝条上
  5.     left_node->right = right_node->left;
  6.     if(right_node->left!=nil){
  7.         left_node->right->parent = left_node;
  8.     }
  9.     //-右节点接在左节点的父亲上
  10.     right_node->parent = left_node->parent;
  11.     if(left_node == root){
  12.         //-nil不会指向任何节点，但是root->parent是nil
  13.         root = right_node;
  14.     }
  15.     else if(left_node == left_node->parent->left){
  16.         left_node->parent->left = right_node;
  17.     }else{
  18.         left_node->parent->right = right_node;
  19.     }
  20.     //-左节点接在右节点的左枝上
  21.     left_node->parent = right_node;
  22.     right_node->left = left_node;
  23. }
  24.  
  25. //- 右旋：写完左旋后，把所有left和right对调即可
  26. void RBtree::rightRotate(RBtree_node * right_node){
  27.     RBtree_node * left_node = right_node->left;
  28.     right_node->left = left_node->right;
  29.     if(left_node->right!=nil){
  30.         right_node->left->parent = right_node;
  31.     }
  32.     left_node->parent = right_node->parent;
  33.     if(right_node == root){
  34.         root = left_node;
  35.     }
  36.     else if(right_node == right_node->parent->right){
  37.         right_node->parent->right = left_node;
  38.     }else{
  39.         right_node->parent->left = left_node;
  40.     }
  41.     right_node->parent = left_node;
  42.     left_node->right = right_node;
  43. }

红黑树的插入，插入修复

插入的步骤原理：

  • 找到插入位置，注意红黑树新节点的插入位置都是叶子结点。

  • 如果红黑树中没有节点，插入节点需要改变root指向，同时将root的parent指向nil。

  • 改变插入节点父亲的左右指针，同时插入节点本身的左右指针指向nil。

  • 如果插入节点的父亲是红色，说明平衡被打破了，需要执行修复插入，让红黑树恢复平衡

要点:

  • 如果在查找的时候发现元素已经存在，我这里就直接抛弃了新元素的插入，如果要实现红黑树multimap的insert_equal功能可以自己实现一下。

  • 为什么要插入修复？

首先我们会强制默认所有的新节点都是红色节点。

因为红色节点不论插在哪个位置，都不会破坏规则5（路径上黑色节点数量相同），唯一可能破坏的是规则4（红色节点的孩子必黑），由于破坏规则5比破坏规则4要容易得多，所以将新节点设置为红色可以尽量地避免破坏规则。

当新的红色节点插入到一个红色节点之后，破坏了规则4，才需要修复，如图2，插入元素16

修复的意义和规则在于，如何将新红节点的父亲（34）变成黑色后，依然能保持红黑树的左右平衡，这个时候才涉及到对伯父节点（184）的讨论

插入修复的步骤原理：

  • 我们的目的是为了让左边cur为红的情况下，使父亲变黑且不会破坏平衡。

  • 所以只要cur的parent是红色，就一直循环。

  • 判断伯父节点（184），如果伯父节点是红色，如图2，那么同时将父亲和伯父改成黑色就不会改变平衡，将祖父（101）变红，让cur变成祖父（101）进入下一轮迭代。

​图2 伯父（184）为红

  • 如果伯父节点是黑色，如图3，插入节点16

​图3 伯父（184）为黑

  • 那么将父亲（34）变黑就会让左边多一个黑色，不过可以通过让祖父（101）变红，旋转祖父，让祖父下沉，父亲上浮，这样相当于让老爹变黑同时左右都加了一个黑色，不会破坏平衡。

  • 但是旋转祖父需要有个前提条件，插入节点不能是父亲的靠内节点，如图4，插入节点（36）为右孩子，父亲（34）是祖父（101）左枝。

​图4，插入节点（36）是靠内节点

  • 一旦右旋祖父（101），就会破坏cur（36）和父亲（34）的连接关系，所以必须要把cur从靠内节点变成靠外节，一个方便的方式是让父亲成为新cur（34），并右旋cur（34），如图5，之后再进行上个步骤，将新父亲（36）变黑，祖父（101）变红，右旋祖父。

​图5 原cur（36）经过旋转变为父亲，将34作为新cur

要点：

  • 终止条件，当当前节点（红）的父亲为黑的时候打破循环（注意回溯到nil的时候的，nil也是黑色）

  • 终止循环后，注意如果回溯到root，会改变root的颜色为红，需要在循环结束后fix成黑色。

  • 因为父亲是祖父左枝也好右枝也好，变换总是左右对称的，所以规则只需要记一半。

  1. //-插入key
  2. void RBtree::insertNode(KEY_TYPE key){
  3.     RBtree_node * prev = nil;
  4.     RBtree_node * cur = root;
  5.     while(cur!=nil){
  6.         prev = cur;
  7.         if(key>cur->key){
  8.             cur = cur->right;
  9.         }else if(key<cur->key){
  10.             cur = cur->left;
  11.         }else{//-该key已经存在
  12.             return;
  13.         }
  14.     }
  15.     //-创建新节点
  16.     RBtree_node * new_node = new RBtree_node(red,key,nil);
  17.     //-如果节点没有元素
  18.     new_node->parent = prev;
  19.     if(prev == nil){
  20.         root = new_node;
  21.     }
  22.     else if(key<prev -> key){
  23.         prev ->left = new_node;
  24.     }else{
  25.         prev ->right = new_node;
  26.     }
  27.     fixInsert(new_node);
  28.     print();
  29. }
  30.  
  31. //-修复插入
  32. void RBtree::fixInsert(RBtree_node * new_node){
  33.     while(new_node -> parent->color == red){//-终止条件要注意
  34.         //-如果父亲是左枝
  35.         if(new_node->parent == new_node -> parent->parent->left){
  36.             //-获得其伯父节点
  37.             RBtree_node * uncle = new_node->parent->parent->right;
  38.             if(uncle->color == red){//-如果伯父是红色，那么将父亲和伯父同时变黑，不会破坏左右平衡
  39.                 uncle->color = black;
  40.                 new_node->parent->color = black;
  41.                 new_node->parent ->parent->color = red;//-将祖父变红，才能实现下一轮回溯修复
  42.                 new_node = new_node->parent->parent;
  43.             }else{//-如果伯父是黑色
  44.                 //-判断new_node是不是右孩子，如果是右孩子转换成左孩子
  45.                 if(new_node == new_node -> parent->right){
  46.                     new_node = new_node->parent;
  47.                     leftRotate(new_node);
  48.                 }
  49.                 //-此时红色节点是左孩子
  50.                 //-如果结构本是平衡状态，右边本该比左边多一个黑，但是我们将父亲（左)变黑会破坏平衡，
  51.                 //-所以需要右旋祖父，把父亲上浮，相当于在左枝多一个黑的时候给右枝也多了黑，这样左右就能平衡
  52.                 new_node->parent->color = black;
  53.                 new_node->parent ->parent->color = red;
  54.                 rightRotate(new_node->parent->parent);
  55.             }
  56.         }
  57.         //-如果父亲是右枝（将上边代码的left和right全部对调即可，不用记规则）
  58.         else {
  59.             RBtree_node * uncle = new_node->parent->parent->left;
  60.             if(uncle->color == red){//-如果伯父是红色
  61.                 uncle->color = black;
  62.                 new_node->parent->color = black;
  63.                 new_node->parent ->parent->color = red;
  64.                 new_node = new_node->parent->parent;
  65.             }else{//-如果伯父是黑色
  66.                 if(new_node == new_node -> parent->left){
  67.                     new_node = new_node->parent;
  68.                     rightRotate(new_node);
  69.                 }
  70.                 new_node->parent->color = black;
  71.                 new_node->parent ->parent->color = red;
  72.                 leftRotate(new_node->parent->parent);
  73.             }
  74.         }
  75.     }
  76.     //-如果new_node回溯到root，此时root->parent==nil（black）打破了循环，而此时root被改变成了黑色，违反了规则1，
  77.     //-所以最后需要强行把root fix成黑色
  78.     root->color = black;
  79. }

红黑树查找某个key，以及找到某个节点的中序后继

主要讲下怎么根据当前节点找中序后继，根据BST的特性

  • 如果当前节点有右孩子：其后继肯定在右枝条上，且是右枝条最左边的元素。

  • 如果当前节点没有右孩子：根据中序遍历的递归顺序，假设cur是其父亲的左孩子，cur遍历完后，下一个节点（后继）就是父亲，反之，如果cur是右孩子，说明其父亲也递归完了，需要回溯父亲的父亲，所以只需要一直往上找直到cur为其parent的左孩子为止，然后返回parent，而回溯到root的时候，root的父亲虽然是nil，但是nil是没有左右孩子的，所以退出循环。

  1. //-查找某个key的节点
  2. RBtree_node* RBtree::searchNode(KEY_TYPE key){
  3.     RBtree_node * cur = root;
  4.     while(cur!=nil){
  5.         if(key>cur -> key){
  6.             cur = cur->right;
  7.         }else if(key < cur -> key){
  8.             cur = cur->left;
  9.         }else{
  10.             return cur;
  11.         }
  12.     }
  13.     return cur;
  14. }
  15.  
  16. //-查找某个节点的中序后继
  17. RBtree_node* RBtree::successor(RBtree_node * node){
  18.     //-如果节点有右孩子
  19.     if(node->right!=nil){
  20.         RBtree_node * res = node -> right;
  21.         while(res->left!=nil){
  22.             res = res->left;
  23.         }
  24.         return res;
  25.     }else{
  26.         while(node!=root&&node!=node->parent->left){
  27.             node = node->parent;
  28.         }
  29.         return node->parent;
  30.     }
  31. }

红黑树删除，修复删除

删除的步骤原理：

  • 类似二叉堆，当我们从栈顶pop元素后，需要用二叉树末尾节点代替原来的root，而后从二叉堆顶部开始向下修复，同理，我们要删除树上的一个节点，自然需要一个节点来顶替删除节点(key_node)的位置，因次，我们并不一定要在数据结构上真正删除key_node，可以找到那个顶替节点(delete_node)，将顶替节点的数据覆盖key_node，而在数据结构上真正删除的是那个顶替节点（delete_node）。

  • 在数据结构上真正删除哪个节点（delete_node怎么取），取决于(key_node)是否有左右枝条，

  • 如果key_node左右孩子都没有，说明是叶子节点，直接删除key_node即可，delete_node就是key_node本身。

  • 如果key_node左右孩子只有其一，那么删除key_node只需要将孩子接在祖父上，删除自己即可，所以delete_node依旧是key_node本身。

  • 如果key_node左右孩子都有，那么可以根据上面的successor函数，找到key_node的直接后继，也就是删除节点右边最小的元素，将其本身数据用来顶替key_node，不会破坏BST的性质。之后将其作为delete_node在数据结构上删除即可，如图6。

图6

  • 找到delete_node后，还要找到delete_node的孩子（delete_son），将delete_son接在delete_node的父亲上。

  • 判断delete_node是否是黑色，如果是黑色，则删除了该元素必会破坏红黑树的平衡（规则5），需要修复fix_delete，而修复从delete_son开始。

要点：

  • 记得额外判断如果delete_node是root的情况，需要更新其孩子delete_son为新的root。

修复删除的步骤原理：

  • 删除节点delete_node如果是黑色的，说明树中有一个枝条（假设是左枝）的黑色节点必会比兄弟枝条（右枝）少一个。我们怎么才能使左右重新平衡，要么让左枝条黑色节点+1，要么让右枝条黑色节点-1。后续步骤全都以delete_son为其父左枝条为例，因为对称，依旧只需要记一半的规则。

  • 让delete_son的兄弟bro变成黑色，如果bro是红色，则bro->黑色，parent->红色，左旋parent，此时bro的左枝会变成新的bro，因为bro是红色，所以根据规则4，左枝必为黑，即新bro变为黑色。

  • 判断bro的孩子，

  • 如果左黑右黑，将bro->红色，不会改变bro后续孩子的平衡，同时，bro所在的右枝条的黑色节点-1，红黑树重新平衡，将父亲作为新的delete_son继续循环，直到delete_son为红色。

  • 如果左红右黑，通过右旋bro，变成左黑右红。

  • 如果左黑右红。bro继承父亲的颜色，将bro的父亲变黑，右孩子变黑（右枝黑+1），左旋父亲（左枝黑+1，右枝黑-1），总的来说delete_son所在的左枝条的黑色节点+1，红黑树重新平衡，并且直接让delete_son=root退出循环。

要点：

  • 终止条件：当delete_son==root或者delete_son为红的时候终止循环。

  1. //-删除key
  2. void RBtree::deleteNode(KEY_TYPE key){
  3.     //-查找key所在节点
  4.     RBtree_node * key_node = searchNode(key);
  5.     //-实际删除的节点
  6.     RBtree_node* delete_node;
  7.     //-delete_node的孩子
  8.     RBtree_node* delete_son;
  9.     //-如果同时有左枝或者右枝条
  10.     if(key_node->left != nil&&key_node->right != nil){
  11.         delete_node = successor(key_node);
  12.         delete_son = delete_node->right;
  13.     }//-如果仅有左枝或者右枝条或者左右都没有
  14.     else{
  15.         delete_node = key_node;
  16.         if(key_node->left != nil){
  17.             delete_son = key_node->left;
  18.         }else{
  19.             delete_son = key_node->right;
  20.         }
  21.     }
  22.  
  23.     //-删除deletenode
  24.     delete_son->parent = delete_node->parent;
  25.     //-先判断deletenode是不是根节点
  26.     if(delete_node == root){
  27.         root = delete_son;
  28.     }
  29.     else if(delete_node == delete_node->parent->left){
  30.         delete_node->parent->left = delete_son;
  31.     }else{
  32.         delete_node -> parent -> right = delete_son;
  33.     }
  34.     //-覆盖key_node原有数据
  35.     key_node->key = delete_node -> key;
  36.     key_node ->value = delete_node -> value;
  37.  
  38.     //-如果删除节点是黑色的，需要修复delete_son,注意是孩子
  39.     if(delete_node->color == black){
  40.         fixDelete(delete_son);
  41.     }
  42.     //-释放空间
  43.     delete delete_node;
  44.     //-打印
  45.     print();
  46. }
  47.  
  48. //-修复删除
  49. void RBtree::fixDelete(RBtree_node * delete_son){
  50.     //-修复的原因是因为delete_son所在的枝条的黑节点比另一个枝条少一个，所以不平衡，所以需要填上左边缺失的黑，或者减掉右边多余的黑
  51.     //-当delete_son是黑色的一直循环
  52.     while(delete_son!=root&&delete_son->color == black){
  53.         //-判断delete_son所在枝条,如果是左枝
  54.         if(delete_son == delete_son->parent->left){
  55.             //-如果兄弟是红色的
  56.             RBtree_node * bro = delete_son->parent->right;
  57.             if(bro->color == red){
  58.                 bro->color = black;//-兄弟变黑
  59.                 delete_son->parent->color = red;//-父亲变红
  60.                 leftRotate(delete_son->parent);//-左旋父亲，兄弟上浮，相当于左右都加了一个黑，不改变平衡状态
  61.                 bro = delete_son->parent->right;//-新的bro是原来bro的左枝，因为原bro是红的，其左右枝都是黑色的，这样保证新的兄弟是黑色的
  62.             }
  63.             //-此时兄弟是黑色的,判断兄弟的孩子
  64.             //-左黑右黑（兄弟的孩子平衡了）
  65.             if(bro->left->color == black&&bro->right -> color == black){
  66.                 bro->color = red;//-相当于右边减去多的一个黑，达到平衡
  67.                 delete_son = delete_son->parent;
  68.             }else{
  69.                 //-如果是左红右黑,变成左黑右红
  70.                 if (bro->right->color == black){
  71.                     bro -> color = red;
  72.                     bro->left->color = black;
  73.                     rightRotate(bro);//-左节点上浮，相当于左右都加了一个黑，不改变平衡
  74.                 }
  75.                 bro->color = bro->parent -> color;
  76.                 bro->parent -> color = black;
  77.                 bro->right->color = black;//-给右边加了一个黑
  78.                 leftRotate(delete_son->parent);//-父亲下沉，兄弟上浮，左边加一个黑，右边减一个黑，总体上左边填上了缺少的黑也达到了平衡
  79.                 delete_son = root;
  80.             }
  81.         }
  82.         //-如果是右枝（不用记规则，把上面的代码left和right对调即可）
  83.         else {
  84.             RBtree_node * bro = delete_son->parent->left;
  85.             if(bro->color == red){
  86.                 bro->color = black;
  87.                 delete_son->parent->color = red;
  88.                 rightRotate(delete_son->parent);
  89.                 bro = delete_son->parent->left;
  90.             }
  91.             if(bro->right->color == black&&bro->left -> color == black){
  92.                 bro->color = red;
  93.                 delete_son = delete_son->parent;
  94.             }else{
  95.                 if (bro->left->color == black){
  96.                     bro -> color = red;
  97.                     bro->right->color = black;
  98.                     leftRotate(bro);
  99.                 }
  100.                 bro->color = bro->parent -> color;
  101.                 bro->parent -> color = black;
  102.                 bro->left->color = black;
  103.                 rightRotate(delete_son->parent);
  104.                 delete_son = root;
  105.             }
  106.         }
  107.     }
  108.     delete_son->color = black;
  109. }

二叉树层序遍历和中序遍历

每次插入删除的时候，使用层序遍历打印一遍二叉树，可以验证一下是否正确。

每个节点都有前缀，b代表黑节点，r代表红节点。

  1. //-层序遍历打印红黑树
  2. void RBtree::print(){
  3.     std::deque<RBtree_node*> dqueue;//-使用deque实现队列
  4.     dqueue.push_back(root);
  5.     while(!dqueue.empty()){
  6.         int size = (int)dqueue.size();
  7.         for (int i = 0; i < size; ++i) {
  8.             RBtree_node* temp = dqueue.front();
  9.             dqueue.pop_front();
  10.             if(temp->left!=nullptr){
  11.                 dqueue.push_back(temp -> left);
  12.             }
  13.             if(temp -> right != nullptr){
  14.                 dqueue.push_back(temp -> right);
  15.             }
  16.             std::string color = temp->color?"b: ":"r: ";
  17.             std::string keystr = temp==nil?"nil":std::to_string(temp->key);
  18.             std::cout<<color<<keystr<<"  ";
  19.         }
  20.         std::cout<<std::endl;
  21.     }
  22. }
  23.  
  24. //-打印中序遍历
  25. void RBtree::printMiddle(RBtree_node * node){
  26.     if(node == nil){
  27.         return;
  28.     }
  29.     printMiddle(node->left);
  30.     std::string color = node->color?"b:":"r:";
  31.     std::cout<<color<<std::to_string(node->key)<<"  ";
  32.     printMiddle(node->right);
  33. }

红黑树测试代码

写个循环来插入元素，输入i插入元素，输入d删除元素，输入q退出程序。

附上一个在线生成红黑树的连接，可以配合测试自己写的红黑树的正确性

红黑树动画在线演示

  1. int main(){
  2.     RBtree rb;
  3.     std::string select;
  4.     KEY_TYPE key;
  5.     while(true){
  6.         std::cout<<"\n输入操作：i：插入key，d：删除key q：退出"<<std::endl;
  7.         std::cin>>select;
  8.         if(select == "i"){
  9.             std::cout<<"输入key"<<std::endl;
  10.             std::cin>>key;
  11.             rb.insertNode(key);
  12.         }else if(select == "d"){
  13.             std::cout<<"输入key"<<std::endl;
  14.             std::cin>>key;
  15.             rb.deleteNode(key);
  16.         }else if(select == "q"){
  17.             break;
  18.         }else{
  19.             std::cout<<"输入不合法，重新输入"<<std::endl;
  20.         }
  21.     }
  22.     return 0;
  23. }

完整代码

  1. #include <iostream>
  2. #include <deque>
  3. #include <string>
  4. #include <vector>
  5.  
  6. //-既然标题是c++，那么就写成满满的c++风格吧
  7. using Color = bool;//-颜色因为只有红或者黑，选择bool类型
  8. using KEY_TYPE = int;//-为了更好理解红黑树，就不写成模板类了，所以首选万年int（笑~）
  9. using VALUE_TYPE = int;//-同理
  10.  
  11. //-全局静态红黑变量
  12. static const Color red = false;
  13. static const Color black  = true;
  14.  
  15. //-红黑树的节点特点，有color，有parent
  16.  
  17. class RBtree_node{
  18. public:
  19.     Color color;
  20.     RBtree_node * parent;
  21.     RBtree_node * left;
  22.     RBtree_node * right;
  23.  
  24.     KEY_TYPE key;//-后期如果想解耦合，可以将key和value抽离出去
  25.     VALUE_TYPE value;
  26.     RBtree_node(Color color_):color(color_),parent(nullptr),left(nullptr),right(nullptr),key(-99999){}
  27.     RBtree_node(Color color_, KEY_TYPE key_,RBtree_node * nil):
  28.     color(color_),parent(nil),left(nil),right(nil),key(key_){}
  29. };
  30.  
  31.  
  32. class RBtree{
  33. private:
  34.     //-红黑树数据成员：其中nil的意义在于，因为红黑树的所有叶子节点都是黑色的，所以可以将所有临近末尾的节点，
  35.     //-都连接到这一个叶子结点nil上，同理，root的parent也可以连接到nil上，形成一个dummy空节点
  36.     RBtree_node * root;
  37.     RBtree_node * nil;
  38. public :
  39.     //-以下实现了红黑树常用接口：
  40.     //-构造函数
  41.     RBtree(){
  42.     nil = new RBtree_node(black);//-为所有叶子节点nil初始化，颜色为黑色
  43.     root = nil;//-红黑树为空的时候，让nil作为root
  44. }
  45. //-左旋
  46. void leftRotate(RBtree_node *left_node);
  47.  
  48. //- 右旋
  49. void rightRotate(RBtree_node * right_node);
  50.  
  51. //-插入key
  52. void insertNode(KEY_TYPE key);
  53.  
  54. //-修复插入
  55. void fixInsert(RBtree_node * node);
  56.  
  57. //-查找某个key的节点
  58. RBtree_node* searchNode(KEY_TYPE key);
  59.  
  60. //-查找某个节点的中序后继
  61. RBtree_node* successor(RBtree_node * node);
  62.  
  63. //-删除key
  64. void deleteNode(KEY_TYPE key);
  65.  
  66. //-修复删除
  67. void fixDelete(RBtree_node * node);
  68.  
  69. //-层序遍历打印红黑树
  70. void print();
  71.  
  72. //-打印中序遍历
  73. void printMiddle(RBtree_node * node);
  74.  
  75. };
  76.  
  77. //-左旋
  78. void RBtree::leftRotate(RBtree_node *left_node){
  79.     RBtree_node * right_node = left_node->right;
  80.     //-右节点的左枝条接在左节点的右枝条上
  81.     left_node->right = right_node->left;
  82.     if(right_node->left!=nil){
  83.         left_node->right->parent = left_node;
  84.     }
  85.     //-右节点接在左节点的父亲上
  86.     right_node->parent = left_node->parent;
  87.     if(left_node == root){
  88.         //-nil不会指向任何节点，但是root->parent是nil
  89.         root = right_node;
  90.     }
  91.     else if(left_node == left_node->parent->left){
  92.         left_node->parent->left = right_node;
  93.     }else{
  94.         left_node->parent->right = right_node;
  95.     }
  96.     //-左节点接在右节点的左枝上
  97.     left_node->parent = right_node;
  98.     right_node->left = left_node;
  99. }
  100.  
  101. //- 右旋：写完左旋后，把所有left和right对调即可
  102. void RBtree::rightRotate(RBtree_node * right_node){
  103.     RBtree_node * left_node = right_node->left;
  104.     right_node->left = left_node->right;
  105.     if(left_node->right!=nil){
  106.         right_node->left->parent = right_node;
  107.     }
  108.     left_node->parent = right_node->parent;
  109.     if(right_node == root){
  110.         root = left_node;
  111.     }
  112.     else if(right_node == right_node->parent->right){
  113.         right_node->parent->right = left_node;
  114.     }else{
  115.         right_node->parent->left = left_node;
  116.     }
  117.     right_node->parent = left_node;
  118.     left_node->right = right_node;
  119. }
  120.  
  121. //-插入key
  122. void RBtree::insertNode(KEY_TYPE key){
  123.     RBtree_node * prev = nil;
  124.     RBtree_node * cur = root;
  125.     while(cur!=nil){
  126.         prev = cur;
  127.         if(key>cur->key){
  128.             cur = cur->right;
  129.         }else if(key<cur->key){
  130.             cur = cur->left;
  131.         }else{//-该key已经存在
  132.             return;
  133.         }
  134.     }
  135.     //-创建新节点
  136.     RBtree_node * new_node = new RBtree_node(red,key,nil);
  137.     //-如果节点没有元素
  138.     new_node->parent = prev;
  139.     if(prev == nil){
  140.         root = new_node;
  141.     }
  142.     else if(key<prev -> key){
  143.         prev ->left = new_node;
  144.     }else{
  145.         prev ->right = new_node;
  146.     }
  147.     fixInsert(new_node);
  148.     print();
  149. }
  150.  
  151. //-修复插入
  152. void RBtree::fixInsert(RBtree_node * new_node){
  153.     while(new_node -> parent->color == red){//-终止条件要注意
  154.         //-如果父亲是左枝
  155.         if(new_node->parent == new_node -> parent->parent->left){
  156.             //-获得其伯父节点
  157.             RBtree_node * uncle = new_node->parent->parent->right;
  158.             if(uncle->color == red){//-如果伯父是红色，那么将父亲和伯父同时变黑，不会破坏左右平衡
  159.                 uncle->color = black;
  160.                 new_node->parent->color = black;
  161.                 new_node->parent ->parent->color = red;//-将祖父变红，才能实现下一轮回溯修复
  162.                 new_node = new_node->parent->parent;
  163.             }else{//-如果伯父是黑色
  164.                 //-判断new_node是不是右孩子，如果是右孩子转换成左孩子
  165.                 if(new_node == new_node -> parent->right){
  166.                     new_node = new_node->parent;
  167.                     leftRotate(new_node);
  168.                 }
  169.                 //-此时红色节点是左孩子
  170.                 //-如果结构本是平衡状态，右边本该比左边多一个黑，但是我们将父亲（左)变黑会破坏平衡，
  171.                 //-所以需要右旋祖父，把父亲上浮，相当于在左枝多一个黑的时候给右枝也多了黑，这样左右就能平衡
  172.                 new_node->parent->color = black;
  173.                 new_node->parent ->parent->color = red;
  174.                 rightRotate(new_node->parent->parent);
  175.             }
  176.         }
  177.         //-如果父亲是右枝（将上边代码的left和right全部对调即可，不用记规则）
  178.         else {
  179.             RBtree_node * uncle = new_node->parent->parent->left;
  180.             if(uncle->color == red){//-如果伯父是红色
  181.                 uncle->color = black;
  182.                 new_node->parent->color = black;
  183.                 new_node->parent ->parent->color = red;
  184.                 new_node = new_node->parent->parent;
  185.             }else{//-如果伯父是黑色
  186.                 if(new_node == new_node -> parent->left){
  187.                     new_node = new_node->parent;
  188.                     rightRotate(new_node);
  189.                 }
  190.                 new_node->parent->color = black;
  191.                 new_node->parent ->parent->color = red;
  192.                 leftRotate(new_node->parent->parent);
  193.             }
  194.         }
  195.     }
  196.     //-如果new_node回溯到root，此时root->parent==nil（black）打破了循环，而此时root被改变成了黑色，违反了规则1，
  197.     //-所以最后需要强行把root fix成黑色
  198.     root->color = black;
  199. }
  200.  
  201. //-查找某个key的节点
  202. RBtree_node* RBtree::searchNode(KEY_TYPE key){
  203.     RBtree_node * cur = root;
  204.     while(cur!=nil){
  205.         if(key>cur -> key){
  206.             cur = cur->right;
  207.         }else if(key < cur -> key){
  208.             cur = cur->left;
  209.         }else{
  210.             return cur;
  211.         }
  212.     }
  213.     return cur;
  214. }
  215.  
  216. //-查找某个节点的中序后继
  217. RBtree_node* RBtree::successor(RBtree_node * node){
  218.     //-如果节点有右孩子
  219.     if(node->right!=nil){
  220.         RBtree_node * res = node -> right;
  221.         while(res->left!=nil){
  222.             res = res->left;
  223.         }
  224.         return res;
  225.     }else{
  226.         while(node!=root&&node!=node->parent->left){
  227.             node = node->parent;
  228.         }
  229.         return node->parent;
  230.     }
  231. }
  232.  
  233. //-删除key
  234. void RBtree::deleteNode(KEY_TYPE key){
  235.     //-查找key所在节点
  236.     RBtree_node * key_node = searchNode(key);
  237.     //-实际删除的节点
  238.     RBtree_node* delete_node;
  239.     //-delete_node的孩子
  240.     RBtree_node* delete_son;
  241.     //-如果同时有左枝或者右枝条
  242.     if(key_node->left != nil&&key_node->right != nil){
  243.         delete_node = successor(key_node);
  244.         delete_son = delete_node->right;
  245.     }//-如果仅有左枝或者右枝条或者左右都没有
  246.     else{
  247.         delete_node = key_node;
  248.         if(key_node->left != nil){
  249.             delete_son = key_node->left;
  250.         }else{
  251.             delete_son = key_node->right;
  252.         }
  253.     }
  254.  
  255.     //-删除deletenode
  256.     delete_son->parent = delete_node->parent;
  257.     //-先判断deletenode是不是根节点
  258.     if(delete_node == root){
  259.         root = delete_son;
  260.     }
  261.     else if(delete_node == delete_node->parent->left){
  262.         delete_node->parent->left = delete_son;
  263.     }else{
  264.         delete_node -> parent -> right = delete_son;
  265.     }
  266.     //-覆盖key_node原有数据
  267.     key_node->key = delete_node -> key;
  268.     key_node ->value = delete_node -> value;
  269.  
  270.     //-如果删除节点是黑色的，需要修复delete_son,注意是孩子
  271.     if(delete_node->color == black){
  272.         fixDelete(delete_son);
  273.     }
  274.     //-释放空间
  275.     delete delete_node;
  276.     //-打印
  277.     print();
  278. }
  279.  
  280. //-修复删除
  281. void RBtree::fixDelete(RBtree_node * delete_son){
  282.     //-修复的原因是因为delete_son所在的枝条的黑节点比另一个枝条少一个，所以不平衡，所以需要填上左边缺失的黑，或者减掉右边多余的黑
  283.     //-当delete_son是黑色的一直循环
  284.     while(delete_son!=root&&delete_son->color == black){
  285.         //-判断delete_son所在枝条,如果是左枝
  286.         if(delete_son == delete_son->parent->left){
  287.             //-如果兄弟是红色的
  288.             RBtree_node * bro = delete_son->parent->right;
  289.             if(bro->color == red){
  290.                 bro->color = black;//-兄弟变黑
  291.                 delete_son->parent->color = red;//-父亲变红
  292.                 leftRotate(delete_son->parent);//-左旋父亲，兄弟上浮，相当于左右都加了一个黑，不改变平衡状态
  293.                 bro = delete_son->parent->right;//-新的bro是原来bro的左枝，因为原bro是红的，其左右枝都是黑色的，这样保证新的兄弟是黑色的
  294.             }
  295.             //-此时兄弟是黑色的,判断兄弟的孩子
  296.             //-左黑右黑（兄弟的孩子平衡了）
  297.             if(bro->left->color == black&&bro->right -> color == black){
  298.                 bro->color = red;//-相当于右边减去多的一个黑，达到平衡
  299.                 delete_son = delete_son->parent;
  300.             }else{
  301.                 //-如果是左红右黑,变成左黑右红
  302.                 if (bro->right->color == black){
  303.                     bro -> color = red;
  304.                     bro->left->color = black;
  305.                     rightRotate(bro);//-左节点上浮，相当于左右都加了一个黑，不改变平衡
  306.                 }
  307.                 bro->color = bro->parent -> color;
  308.                 bro->parent -> color = black;
  309.                 bro->right->color = black;//-给右边加了一个黑
  310.                 leftRotate(delete_son->parent);//-父亲下沉，兄弟上浮，左边加一个黑，右边减一个黑，总体上左边填上了缺少的黑也达到了平衡
  311.                 delete_son = root;
  312.             }
  313.         }
  314.         //-如果是右枝（不用记规则，把上面的代码left和right对调即可）
  315.         else {
  316.             RBtree_node * bro = delete_son->parent->left;
  317.             if(bro->color == red){
  318.                 bro->color = black;
  319.                 delete_son->parent->color = red;
  320.                 rightRotate(delete_son->parent);
  321.                 bro = delete_son->parent->left;
  322.             }
  323.             if(bro->right->color == black&&bro->left -> color == black){
  324.                 bro->color = red;
  325.                 delete_son = delete_son->parent;
  326.             }else{
  327.                 if (bro->left->color == black){
  328.                     bro -> color = red;
  329.                     bro->right->color = black;
  330.                     leftRotate(bro);
  331.                 }
  332.                 bro->color = bro->parent -> color;
  333.                 bro->parent -> color = black;
  334.                 bro->left->color = black;
  335.                 rightRotate(delete_son->parent);
  336.                 delete_son = root;
  337.             }
  338.         }
  339.     }
  340.     delete_son->color = black;
  341. }
  342.  
  343. //-层序遍历打印红黑树
  344. void RBtree::print(){
  345.     std::deque<RBtree_node*> dqueue;//-使用deque实现队列
  346.     dqueue.push_back(root);
  347.     while(!dqueue.empty()){
  348.         int size = (int)dqueue.size();
  349.         for (int i = 0; i < size; ++i) {
  350.             RBtree_node* temp = dqueue.front();
  351.             dqueue.pop_front();
  352.             if(temp->left!=nullptr){
  353.                 dqueue.push_back(temp -> left);
  354.             }
  355.             if(temp -> right != nullptr){
  356.                 dqueue.push_back(temp -> right);
  357.             }
  358.             std::string color = temp->color?"b: ":"r: ";
  359.             std::string keystr = temp==nil?"nil":std::to_string(temp->key);
  360.             std::cout<<color<<keystr<<"  ";
  361.         }
  362.         std::cout<<std::endl;
  363.     }
  364. }
  365.  
  366. //-打印中序遍历
  367. void RBtree::printMiddle(RBtree_node * node){
  368.     if(node == nil){
  369.         return;
  370.     }
  371.     printMiddle(node->left);
  372.     std::string color = node->color?"b:":"r:";
  373.     std::cout<<color<<std::to_string(node->key)<<"  ";
  374.     printMiddle(node->right);
  375. }
  376.  
  377. int main(){
  378.     RBtree rb;
  379.     std::string select;
  380.     KEY_TYPE key;
  381.     while(true){
  382.         std::cout<<"\n输入操作：i：插入key，d：删除key q：退出"<<std::endl;
  383.         std::cin>>select;
  384.         if(select == "i"){
  385.             std::cout<<"输入key"<<std::endl;
  386.             std::cin>>key;
  387.             rb.insertNode(key);
  388.         }else if(select == "d"){
  389.             std::cout<<"输入key"<<std::endl;
  390.             std::cin>>key;
  391.             rb.deleteNode(key);
  392.         }else if(select == "q"){
  393.             break;
  394.         }else{
  395.             std::cout<<"输入不合法，重新输入"<<std::endl;
  396.         }
  397.     }
  398.     return 0;
  399. }

                

        
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/246040
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号