数据结构：红黑树的插入实现(C++)

在这里插入图片描述

个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》《C++》《Linux》

文章目录

  • 一、红黑树
  • 二、红黑树的插入
  • 三、代码实现
  • 总结

一、红黑树

红黑树的概念：
红黑树是一颗二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，该节点颜色不是红色就是黑色。通过对每一条从根节点到叶子结点路径上各个节点颜色的控制，确保没有一条路径会比其它路径长出两倍，因此红黑树是接近平衡。

在这里插入图片描述

那红黑树是通过哪些规则来对节点颜色进行控制？

  1. 每个节点不是红色就是黑色

  2. 根节点是黑色

  3. 如果一个节点是红色，则其两个子节点是黑色(不能有连续的红色节点)

  4. 对于每个节点，从该节点到其所以叶子结点的路径上，其黑色节点的数目相同

  5. 每个叶子结点都是黑色的(此处的叶子结点是空节点(NIL)，方便我们计算路径的个数)
    注意：上述中的路径是从某一节点到NIL节点。如上图8节点到叶子结点就有5条路径，每条路径都有一个黑色节点。

那为什么遵循这5条规则，红黑树就能保证其最长路径中节点的个数不会超过最短路径节点个数的两倍？
我们假设从根节点到叶子结点的黑色节点数为n，那么最短路径不就是连续的黑色节点，最短路径的节点数为n，那么最长路径不就是红黑相间，最长路径的节点数为2n。所以红黑树保证其最长路径中节点的个数不会超过最短路径节点个数的两倍。

下面是红黑树节点的定义。

enum
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode(T data = T()):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;int _col;
};

该定义中，我们默认将新节点颜色定义为红色，这样我们插入节点时需要维护规则的成本就少。如我们新插入一个红色节点，那么有可能会违背规则3(当其父节点是红色时，有连续红色节点)，这时我们可能需要一些变色和旋转，来维持规则，但如果我们插入节点是黑色，那么我们一定违背4(每条路径上黑色节点数相同)，这时我们可能需要对整个数进行操作。

二、红黑树的插入

红黑树也是一个二叉搜索树，插入新节点与二叉搜索树的操作一样，如果新插入节点比该节点大，新插入节点就去该节点的右子树，反之去该节点的左子树。

if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur != nullptr){parent = cur;if (cur->_data > data){cur = cur->_left;}else if(cur->_data < data){cur = cur->_right;}else // cur->_data == data{return false;}}cur = new Node(data);cur->_parent = parent;if (cur->_data > parent->_data){parent->_right = cur;}else{parent->_left = cur;}

这里我们主要分析新插入节点后，红黑树的情况和处理。对于旋转，这里并不会详细解析。对于旋转的详细解析在我的AVL树一文中。数据结构：AVLTree的插入和删除的实现

在分析情况前，我们先了解几个节点的含义，方便后续的理解。
在这里插入图片描述
接下来的所有情况都与这四个节点有关。

因为我们新插入的节点是红色，如果新插入节点的父节点是黑色，那么红黑树的规则未被破坏。如果新插入节点的父节点是红色，那么就有连续的红色节点。这是我们就要分情况讨论。

情况1. cur为红色，parent为红色，grandfather为黑色，uncle为红色
也就是如下图所示：
在这里插入图片描述
这种情况是最简单的情况，我们只需要将parent 与 uncle的颜色变成黑色(解决连续红色节点)，再将grandfather的颜色变成红色(防止经过grandfather路径的黑色节点数+1)
在这里插入图片描述
但就如上图所示，因为我们将grandfather的颜色变成红色，如果grandfather的父节点的颜色也是红色，这时我们依旧有连续的红色节点，我们仍需对grandfather进行处理。
在这里插入图片描述
我们重复变色过程
在这里插入图片描述
这时，grandfather没有父节点，就可以停止了，但此时grandfather作为根节点为红色，我们需要特殊处理一下即可。这样对于该插入新节点的情况一就完成了。
下面是总结的模型：
在这里插入图片描述
对于这种cur，parent，uncle为红色，grandfather为黑色的情况，我们只需让parent，uncle变成红色，grandfather变成黑色，接着需要检查grandfather的父节点是否是红色，如果是红色，重复上述操作。如果是黑色，就可以结束了。

情况2：cur为红色，parent为红色，grandfather为黑色，uncle不存在或uncle存在且为黑色
在这里插入图片描述
这时情况1 的处理就行不通了，因为uncle要么不存在，要么本身就为黑色，如果将grandfather变成红色，那么经过grandfather的路径的黑色节点数就-1。所以我们要采取旋转+变色。
在这里插入图片描述
因为cur在parent的右侧，parent在grandfather的右侧，成直线。所以我们对grandfather左单旋，接着将parent的颜色变成黑色，grandfather的颜色变成红色(防止经过grandfather的路径的黑色节点数+1)，又因为parent作为新的根节点为黑色，所以我们不需要去检查parent的父节点的颜色。(虽然我们也可以只将cur变为黑色，但这样我们就需要检查parent父节点的颜色)
那如果我们新增5节点要怎么处理？
在这里插入图片描述
此时我们也需要旋转+变色，但我们要双旋。
在这里插入图片描述
如上图，我们要先对parent左单旋，使grandfather，cur，parent在同一侧，接着使grandfather左单旋，cur变为黑色，grandfather变成红色。
如果parent在grandfather的左侧，情况与上述情况类似，只需要改变旋转方向即可。
下面是总结的模型：
单旋在这里插入图片描述
双旋
在这里插入图片描述

while (parent != nullptr && parent->_col != BLACK){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle != nullptr && uncle->_col == RED) // uncle存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == BLACK) // uncle不存在 或 umcle存在且为黑{if (cur == parent->_left) // 同方向{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // cur == parent->_right 不同方向{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;if (uncle != nullptr && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == BLACK){if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK; //特殊处理，保证根节点是黑色

则此，红黑树的插入就完成了。

三、代码实现

RBTree.h 文件是红黑树插入的实现
test.cpp 文件是测试用例

// RBTree.h 文件
#pragma onceenum
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode(T data = T()):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;int _col;
};template<class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:RBTree():_root(nullptr){}bool insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur != nullptr){parent = cur;if (cur->_data > data){cur = cur->_left;}else if(cur->_data < data){cur = cur->_right;}else // cur->_data == data{return false;}}cur = new Node(data);cur->_parent = parent;if (cur->_data > parent->_data){parent->_right = cur;}else{parent->_left = cur;}while (parent != nullptr && parent->_col != BLACK){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle != nullptr && uncle->_col == RED) // uncle存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == BLACK) // uncle不存在 或 umcle存在且为黑{if (cur == parent->_left) // 同方向{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // cur == parent->_right 不同方向{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;if (uncle != nullptr && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == BLACK){if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}// 读取红黑树最左侧节点Node* leftMost(){if (_root == nullptr){return nullptr;}Node* cur = _root;while (cur->_left != nullptr){cur = cur->_left;}return cur;}// 读取红黑树最右侧节点Node* rightMost(){if (_root == nullptr){return nullptr;}Node* cur = _root;while (cur->_right != nullptr){cur = cur->_right;}return cur;}bool isValidRBTree(){if (_root->_col == RED){return false;}// 找最左边的黑色节点数作为标准比较int pathBlack = 0;Node* cur = _root;while (cur != nullptr){if (cur->_col == BLACK){pathBlack++;}cur = cur->_left;}return _isValidRBTree(_root, 0, pathBlack);}bool _isValidRBTree(Node* root, int blackCount, int pathBlack){if (root == nullptr){if (blackCount == pathBlack)return true;elsereturn false;}if (root->_col == RED&& root->_parent != nullptr&& root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackCount++;}return _isValidRBTree(root->_left, blackCount, pathBlack)&& _isValidRBTree(root->_right, blackCount, pathBlack);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;parent->_left = subLR;subL->_right = parent;parent->_parent = subL;if (subLR != nullptr){subLR->_parent = parent;}if (pparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_right = subRL;subR->_left = parent;parent->_parent = subR;if (subRL != nullptr){subRL->_parent = parent;}if (pparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}}private:Node* _root;
};
//test.cpp 文件
#include <iostream>
#include <vector>using namespace std;
#include "RBTree.h"#define N 10000000void test1()
{vector<int> nums(N);srand((unsigned int)time(0));for (int i = 0; i < N; i++){nums[i] = rand() + i;//cout << nums[i] << endl;}RBTree<int> tree;for (auto val : nums){if (val == 11478){int i = 0;i++;}tree.insert(val);//cout << val << "->" << tree.isValidRBTree() << endl;}cout << tree.isValidRBTree() << endl;
}int main()
{test1();return 0;
}

总结

以上就是我对于红黑树插入实现的总结。感谢支持！！！
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

基于java web个人财务管理系统

基于java web个人财务管理系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…
阅读更多...
SDUT OJ《算法分析与设计》贪心算法

SDUT OJ《算法分析与设计》贪心算法

A - 汽车加油问题 Description 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法&#xff0c;指出应在哪些加油站停靠加油&#xff0c;使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置&#xff0c;计算最少加油次数。 I…
阅读更多...
【LeetCode刷题-树】--1367.二叉树中的链表

【LeetCode刷题-树】--1367.二叉树中的链表

1367.二叉树中的链表 方法&#xff1a;枚举 枚举二叉树中的每个节点为起点往下的路径是否与链表相匹配的路径&#xff0c;为了判断是否匹配设计了一个递归函数dfs(root,head),其中root表示当前匹配到的二叉树节点&#xff0c;head表示当前匹配到的链表节点&#xff0c;整个函数…
阅读更多...
opencv(2): 视频采集和录制

opencv(2): 视频采集和录制

视频采集 相关API VideoCapture()cap.read()&#xff1a; 返回两个值&#xff0c;第一个参数&#xff0c;如果读到frame&#xff0c;返回 True. 第二个参数为相应的图像帧。cap.release() VideoCapture cv2.VideoCapture(0) 0 表示自动检测&#xff0c;如果在笔记本上运行&…
阅读更多...
微服务和Spring Cloud Alibaba介绍

微服务和Spring Cloud Alibaba介绍

1、微服务介绍 1.1 系统架构演变 随着互联网的发展&#xff0c;网站应用的规模也在不断的扩大&#xff0c;进而导致系统架构也在不断的进行变化。从互联网早起到现在&#xff0c;系统架构大体经历了下面几个过程: 单体应用架构 —> 垂直应用架构 —> 分布 式架构—>…
阅读更多...
Selenium操作已经打开的Chrome浏览器窗口

Selenium操作已经打开的Chrome浏览器窗口

Selenium操作已经打开的Chrome浏览器窗口 0. 背景 在使用之前的代码通过selenium操作Chrome浏览器时&#xff0c;每次都要新打开一个窗口&#xff0c;觉得麻烦&#xff0c;所以尝试使用 Selenium 获取已经打开的浏览器窗口&#xff0c;在此记录下过程 本文使用 chrome浏览器来…
阅读更多...
springboot引入redisson分布式锁及原理

springboot引入redisson分布式锁及原理

1.引入依赖 <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.13.6</version> </dependency>2.配置类创建bean /*** author qujingye* Classname RedissonConfig* Description TOD…
阅读更多...
基于单片机的水位检测系统仿真设计

基于单片机的水位检测系统仿真设计

**单片机设计介绍&#xff0c; 基于单片机的水位检测系统仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的水位检测系统仿真系统是一种用于模拟水位检测系统的工作过程&#xff0c;以验证设计方案的可行性和优…
阅读更多...
CCRC认证是什么？

CCRC认证是什么？

什么是CCRC认证&#xff1f; 信息安全服务资质&#xff0c;是信息安全服务机构提供安全服务的一种资格&#xff0c;包括法律地位、资源状况、管理水平、技术能力等方面的要求。 信息安全服务资质&#xff08;CCRC&#xff09;是依据国家法律法规、国家标准、行业标准和技术规范…
阅读更多...
系列五、怎么查看默认的垃圾收集器是哪个？

系列五、怎么查看默认的垃圾收集器是哪个？

一、怎么查看默认的垃圾收集器是哪个 java -XX:PrintCommandLineFlags -version
阅读更多...
main.js 中的 render函数

main.js 中的 render函数

按照之前的单组件文件中的写法&#xff0c;我们的写法应该是这样的 import App from ./App.vuenew Vue({el: #app,templete: <App></App>,components: {App}, }) 1、定义el根节点。2、注册App组件。3、渲染 templete 模板 但是在脚手架工程中&#xff0c;他是这…
阅读更多...
excel中vlookup用法

excel中vlookup用法

excel中vlookup用法 用法示例 参数说明 参数1&#xff1a;E1用于匹配的字段 参数2&#xff1a;E1:F4&#xff0c;匹配表格范围 参数3&#xff1a;要取的字段属于匹配表格范围的第几列 数据4&#xff1a;精确匹配
阅读更多...
react实现步进器

react实现步进器

创建一个步进器组件&#xff0c;包含当前步骤&#xff08;currentStep&#xff09;的状态以及前进和后退的操作&#xff1a; import React, { useState } from react;function Stepper() {const [currentStep, setCurrentStep] useState(1);const handleNext () > {setCu…
阅读更多...
python-opencv 培训课程作业

python-opencv 培训课程作业

python-opencv 培训课程作业 作业一&#xff1a; 第一步&#xff1a;读取 res 下面的 flower.jpg&#xff0c;读取彩图&#xff0c;并用 opencv 展示 第二步&#xff1a;彩图 -> 灰度图 第三步&#xff1a;反转图像&#xff1a;最大图像灰度值减去原图像&#xff0c;即可得…
阅读更多...
2023.11.18 - hadoop之zookeeper分布式协调服务

2023.11.18 - hadoop之zookeeper分布式协调服务

1.zookeeper简介 ZooKeeper概念: Zookeeper是一个分布式协调服务的开源框架。本质上是一个分布式的小文件存储系统 ZooKeeper作用: 主要用来解决分布式集群中应用系统的一致性问题。 ZooKeeper结构: 采用树形层次结构&#xff0c;没有目录与文件之分,ZooKeeper树中的每个节点被…
阅读更多...
linux文件IO

linux文件IO

文件IO截断 截断对文件的偏移量没有影响。
阅读更多...
Sqlite安装配置及使用

Sqlite安装配置及使用

一、下载SQLite Sqlite官网 我下载的是3370000版本:sqlite-dll-win64-x64-3370000.zip 和 sqlite-tools-win32-x86-3370000.zip 二、解压下载的两个压缩包 三、配置环境 四、检查是否安装配置成功 winR&#xff1a;输入cmd调出命令窗口&#xff0c;输入sqlite3后回车查看s…
阅读更多...
2023-11-17 VsCode使用makefile进行多文件编译

2023-11-17 VsCode使用makefile进行多文件编译

点击 <C 语言编程核心突破> 快速C语言入门 VsCode使用makefile进行多文件编译 前言一、一个简单的多文件示例二、makefile基本语法三、VsCode使用makefile总结 前言 要解决问题: C或C可以多文件编译, 意味着需要进行代码组织, 为了方便多文件编译, gnu开发了make工具, …
阅读更多...
mac苹果笔记本应用程序在哪？有什么快捷方式吗？

mac苹果笔记本应用程序在哪？有什么快捷方式吗？

苹果笔记本电脑一直以来都被广泛使用&#xff0c;而苹果的操作系统 macOS 也非常受欢迎。一台好的笔记本电脑不仅仅依赖于硬件配置&#xff0c;还需要丰富多样的应用程序来满足用户的需求。苹果笔记本应用程序在哪&#xff0c;不少mac新手用户会有这个疑问。在这篇文章中&#…
阅读更多...
PMCW体制雷达系列文章(4) – PMCW雷达之抗干扰

PMCW体制雷达系列文章(4) – PMCW雷达之抗干扰

说明 本文作为PMCW体制雷达系列文章之一&#xff0c;主要聊聊FMCW&PMCW两种体制雷达的干扰问题。事实上不管是通信领域还是雷达领域&#xff0c;对于一切以电磁波作为媒介的信息传递活动&#xff0c;干扰是无处不在的。近年来&#xff0c;随着雷达装车率的提高&#xff0c;…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023