C++简单实现红黑树

目录

一、概念

二、红黑树的性质

三、红黑树的定义

四、红黑树的插入操作

情况一（叔叔节点存在且为红色）——变色+向上调整：

情况二（叔叔节点不存在或为黑色）——旋转+变色：

2.1叔叔节点不存在

2.2叔叔节点为黑色

插入的代码实现：

五、红黑树的验证

六、红黑树完整代码

一、概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

二、红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点）

三、红黑树的定义

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_kv(kv),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响{}pair<K, V> _kv;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _parent;Colour _col;
};

C++STL中的set和map底层就是使用红黑树实现的，而map是存放键值对的，所以我们给红黑树的节点中的值存放一个键值对，以及左右孩子的指针和指向父节点的指针，还有一个存放颜色的标记。

四、红黑树的插入操作

红黑树的插入首先和普通二叉搜索树的插入操作一样，新建一个节点，左节点的值小于根，右节点的值大于根，找到位置进行插入。插入后应如果破坏了红黑树的性质，就需要进行调整。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：

我们给出一个约定：cur为当前节点，p为父亲节点，g为祖父节点，u为叔叔节点

情况一（叔叔节点存在且为红色）——变色+向上调整：

将p和u改成黑色，将g改为红色

此时有三种情况：

1、g没有父亲节点，直接变成黑色就可以，插入结束；

2、g有父亲节点，且父亲为黑色，插入结束；

3、g有父亲节点，且父亲为红色（违反了红色节点不能连续的性质），需要向上调整。

情况二（叔叔节点不存在或为黑色）——旋转+变色：

2.1叔叔节点不存在

如果cur在parent的左边——右旋：

cur在parent的右边——先左旋再右旋：

2.2叔叔节点为黑色

如果cur在parent的左边——右旋：

cur在parent的右边——先左旋再右旋：

以上插入操作是p在g节点左边的情况，p在g节点右边的情况与以上插入过程类似，仅仅是镜像翻转一下。

插入的代码实现：

左旋代码：

void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;cur->_left = parent;if (curleft)curleft->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

右旋代码：

void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;cur->_right = parent;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

插入代码：

    bool insert(const pair<K, V>& kv){//如果root为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//插入Node* cur = _root;Node* parent = cur;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);//插入节点if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完毕，开始调整颜色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//叔叔在右if (grandfather->_left == parent){Node* uncle = grandfather->_right;//叔叔存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在或者为黑色——旋转+变色else{//右单旋即可if (parent->_left == cur){RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//先左单旋，后右单旋else{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}//叔叔在左else{Node* uncle = grandfather->_left;//uncle存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//uncle不存在或为黑色——旋转+变色else{//左单旋即可if (parent->_right == cur){RotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}//先右单旋，再左单旋else{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

五、红黑树的验证

    bool isBalance(){return _isBalance(_root);}bool checkcolour(Node* root, int benckmark, int blackcount){if (root == nullptr){if (blackcount != benckmark)return false;return true;}if (root->_col == RED && root->_parent && root->_parent->_col == RED)return false;if (root->_col == BLACK)++benckmark;return checkcolour(root->_left, benckmark, blackcount)&& checkcolour(root->_right, benckmark, blackcount);}bool _isBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;Node* cur = root;//求树中最左路径黑色节点的个数while (cur){if (cur->_col == BLACK)++blackcount;cur = cur->_left;}return checkcolour(_root, 0, blackcount);}

六、红黑树完整代码

#pragma once#include <iostream>
#include <vector>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_kv(kv),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响{}pair<K, V> _kv;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _parent;Colour _col;
};
/*
* 红黑树插入思路——关键在于uncle节点：
* 分为两大类：
* 一、如果uncle存在且为红色——仅仅变色即可
* 
*	       g(黑)                            g(红)     
*     p(红)     u(红)    ------->       p(黑)      u(黑) ------->继续向上更新
*  c(红)                            c(红)
* 
* 
* 二、如果uncle不存在或为黑色——旋转加变色
* 
* 情况一：       g(黑)                              p(红)
*            p(红)    NULL/黑  ------->       c(红)       g(黑)
*         c(红)
* 
*        仅仅右旋即可，g变成红色; p变成黑色;  break;
* 
* 情况二：       g(黑)                                  g(黑)                c(红)
*			 p(红)    NULL/黑  ------->   先左旋     c(红)    ------->   p(红)    g(黑) 
*               c(红)                             p(红)
* 
*        c变成黑色，g变成红色，break;
* 
* 情况三：情况一的对称图形
* 情况四：情况二的对称图形
* 
*/
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}void InOrder(){cout << "InOrder: ";_InOrder(_root);cout << endl;}bool insert(const pair<K, V>& kv){//如果root为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//插入Node* cur = _root;Node* parent = cur;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);//插入节点if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完毕，开始调整颜色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//叔叔在右if (grandfather->_left == parent){Node* uncle = grandfather->_right;//叔叔存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在或者为黑色——旋转+变色else{//右单旋即可if (parent->_left == cur){RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//先左单旋，后右单旋else{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}//叔叔在左else{Node* uncle = grandfather->_left;//uncle存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//uncle不存在或为黑色——旋转+变色else{//左单旋即可if (parent->_right == cur){RotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}//先右单旋，再左单旋else{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}bool isBalance(){return _isBalance(_root);}private:bool checkcolour(Node* root, int benckmark, int blackcount){if (root == nullptr){if (blackcount != benckmark)return false;return true;}if (root->_col == RED && root->_parent && root->_parent->_col == RED)return false;if (root->_col == BLACK)++benckmark;return checkcolour(root->_left, benckmark, blackcount)&& checkcolour(root->_right, benckmark, blackcount);}bool _isBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;Node* cur = root;while (cur){if (cur->_col == BLACK)++blackcount;cur = cur->_left;}return checkcolour(_root, 0, blackcount);}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;cur->_left = parent;if (curleft)curleft->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;cur->_right = parent;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}
private:Node* _root;int blackcount = 0;
};

测试：

运行结果：

之后更新红黑树的应用，用红黑树封装map和set。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/144125.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

智能网联驾驶测试与评价工业和信息化部重点实验室“车载智能计算基础平台参考架构2.0专家研讨会”圆满结束

智能网联驾驶测试与评价工业和信息化部重点实验室“车载智能计算基础平台参考架构2.0专家研讨会”圆满结束

近日&#xff0c;智能网联驾驶测试与评价工业和信息化部重点实验室在北京市召开“车载智能计算基础平台参考架构2.0专家研讨会”&#xff0c;本次会议由智能网联驾驶测试与评价工业和信息化部重点实验室、中国软件评测中心&#xff08;工业和信息化部软件与集成电路促进中心&am…
阅读更多...
ChatGPT 在机器学习中的应用

ChatGPT 在机器学习中的应用

办公室里一个机器人坐在人类旁边&#xff0c;Artstation 上的流行趋势&#xff0c;美丽的色彩&#xff0c;4k&#xff0c;充满活力&#xff0c;蓝色和黄色&#xff0c; DreamStudio出品 一、介绍 大家都知道ChatGPT。它在解释机器学习和深度学习概念方面也非常高效&#xff0c;…
阅读更多...
SpringCloud Alibaba - Sentinel

SpringCloud Alibaba - Sentinel

接上文SpringCloud Alibaba - Nacos 1.Sentinel 流量防卫兵 1.1 安装与部署 和Nacos一样&#xff0c;它是独立安装和部署的&#xff0c;下载地址https://github.com/alibaba/Sentinel/releases 下载后的jar放到目录 然后配置 启动并访问,用户名密码都是 sentinel 此时就…
阅读更多...
祝贺莱佛士学生在ASDA2023设计大赛中获得最高奖项

祝贺莱佛士学生在ASDA2023设计大赛中获得最高奖项

莱佛士一直主张学生们积极参与各种国际知名的设计大赛&#xff0c;也会竭尽所能为学生们的参赛提供途径与指导&#xff0c;本次的American Standard Design Award&#xff08;ASDA&#xff09;2023设计大赛也不例外。 ASDA2023设计大赛&#xff0c;推广以用户为中心的设计理念…
阅读更多...
为什么要选择Spring cloud Sentinel

为什么要选择Spring cloud Sentinel

为什么要选择Spring cloud Sentinel &#x1f34e;对比Hystrix&#x1f342;雪崩问题及解决方案&#x1f342;雪崩问题&#x1f342;.超时处理&#x1f342;仓壁模式&#x1f342;断路器&#x1f342;限流&#x1f342;总结 &#x1f34e;对比Hystrix 在SpringCloud当中支持多…
阅读更多...
CSS滚动条详解(::-webkit-scrollbar )

CSS滚动条详解(::-webkit-scrollbar )

滚动条出现的事件&#xff1a; 当设置定宽或者定高的元素添加overflow:scroll属性&#xff0c;会出现滚动条&#xff0c;但是原生样式的会比较丑影响美观。 <div class"content"><div class"contain"></div> </div>.content {wid…
阅读更多...
第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 试题 A: 子 2023

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 试题 A: 子 2023

[蓝桥杯 2023 国 B] 子 2023 试题 A: 子 2023 【问题描述】 小蓝在黑板上连续写下从 1 1 1 到 2023 2023 2023 之间所有的整数&#xff0c;得到了一个数字序列&#xff1a; S 12345678910111213 ⋯ 20222023 S 12345678910111213\cdots 20222023 S12345678910111213⋯2…
阅读更多...
IntelliJ IDEA学习总结（3）—— IntelliJ IDEA 常用快捷键（带动图演示）

IntelliJ IDEA学习总结（3）—— IntelliJ IDEA 常用快捷键（带动图演示）

一、构建/编译 Ctrl + F9：构建项目 该快捷键，等同于菜单【Build】—>【Build Project】 执行该命令后，IntelliJ IDEA 会编译项目中所有类，并将编译结果输出到out目录中。IntelliJ IDEA 支持增量构建，会在上次构建的基础上，仅编译修改的类。 Ctrl + Shift + F9：重新编…
阅读更多...
【论文阅读 09】融合门控自注意力机制的生成对抗网络视频异常检测

【论文阅读 09】融合门控自注意力机制的生成对抗网络视频异常检测

2021年 中国图象图形学报 摘 要 背景&#xff1a; 视频异常行为检测是智能监控技术的研究重点&#xff0c;广泛应用于社会安防领域。当前的挑战之一是如何提高异常检测的准确性&#xff0c;这需要有效地建模视频数据的空间维度和时间维度信息。生成对抗网络&#xff08;GANs&…
阅读更多...
【2251. 花期内花的数目】

【2251. 花期内花的数目】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个下标从 0 开始的二维整数数组 flowers &#xff0c;其中 flowers[i] [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi &#xff08;都 包含&#xff09;。同时给你一个下标从 0 开始…
阅读更多...
数据结构和算法（8）：搜索树（二叉搜索树和AVL树）

数据结构和算法（8）：搜索树（二叉搜索树和AVL树）

查找 所谓的查找或搜索&#xff0c;指从一组数据对象中找出符合特定条件者&#xff0c;这是构建算法的一种基本而重要的操作。其中的数据对象&#xff0c;统一地表示和实现为 词条&#xff08;entry&#xff09; 的形式&#xff1b;不同词条之间&#xff0c;依照各自的 关键码…
阅读更多...
Caddy Web服务器深度解析与对比：Caddy vs. Nginx vs. Apache

Caddy Web服务器深度解析与对比：Caddy vs. Nginx vs. Apache

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…
阅读更多...
canvas手写签名组件

canvas手写签名组件

效果图&#x1f447; 代码不多直接粘在这里 <template><div class"border"><canvasref"canvas"width"800"height"500"class"border-success"tabindex"0"mousedown"onMouseDown"/>&…
阅读更多...
二叉树题目：二叉树剪枝

二叉树题目：二叉树剪枝

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;二叉树剪枝 出处&#xff1a;814. 二叉树剪枝 难度 4 级 题目描述 要求 给定二叉树的根结点 root \texttt{root} root&#xff0c;返回移除了所有…
阅读更多...
如何用思维导图做学习计划？

如何用思维导图做学习计划？

在我们不断追求个人和职业发展的过程中&#xff0c;学习计划起着至关重要的作用。然而&#xff0c;很多人在制定学习计划时常常感到困惑&#xff0c;不知道如何才能制定一份周全且可行的计划。本文将介绍一种结构化思维的方法&#xff0c;以帮助你制定一份高效的学习计划。 首先…
阅读更多...
113. 路径总和ii

113. 路径总和ii

力扣题目链接(opens new window) 给定一个二叉树和一个目标和&#xff0c;找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树&#xff0c;以及目标和 sum 22&#xff0c; 在路径总和题目的基础上&…
阅读更多...
如何使用Etherscan Remix插件验证智能合约

如何使用Etherscan Remix插件验证智能合约

在Moonbeam上验证合约的方式有很多&#xff0c;使用Etherscan Remix插件是最快、最简单的方式。 此示例中&#xff0c;我们展示如何在Remix上激活Etherscan插件并验证简单的增量智能合约。开始之前&#xff0c;请准备以下内容&#xff1a; MetaMask钱包 存有DEV的账户 将验证…
阅读更多...
Linux 线程同步（重要） 互斥量

Linux 线程同步（重要） 互斥量

/*三个窗口卖一百张票 */#include<stdio.h> #include<unistd.h> #include<pthread.h> #include<string.h> int tickets 0; void * sellticket(void * arg) {//卖票usleep(7000);while(tickets < 100) {printf("%ld 正在卖第 %d 张票\n",…
阅读更多...
34.CSS魔线图标的悬停效果

34.CSS魔线图标的悬停效果

效果 源码 index.html <!DOCTYPE html> <html> <head> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Icon Fill Hover Effects</title> <link rel="stylesheet" h…
阅读更多...
基于AIOps实现智慧园区极简IT运维

基于AIOps实现智慧园区极简IT运维

随着物联网、云平台、大数据、人工智能等技术的发展&#xff0c;并逐步投入到智慧园区的建设&#xff0c;传统园区数字化转型加快。园区的形式包括产业园区、教育园区、制造业园区、科研园区、社区等等&#xff0c;园区形态不断演进和发展&#xff0c;园区网承载的对象和业务也…
阅读更多...
最新文章

Copyright @ 2022~2023