【数据结构】模拟实现红黑树（RBTree）的插入算法

2024-01-17 07:32
文章标签 算法 实现 数据结构 模拟 红黑树 插入 rbtree

本文主要是介绍【数据结构】模拟实现红黑树（RBTree）的插入算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、红黑树基本概念

含义：

首先红黑树是一棵二叉搜索树，它在每一个节点上增加了一个存储位来表示节点的颜色（red 或 black）。红黑树通过对任何一条从根节点到叶子节点简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似平衡，而且在实际应用中发现红黑树性能确实比AVL树性能高。

【数据结构】二叉搜索树的插入，删除，查找等基本操作的实现

【数据结构】AVL树的平衡化旋转及实现AVL树的插入操作

性质：
  1. 每个节点不是黑色就是红色
  2. 树的根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子节点是黑色的（没有两个连续的红色节点）
  4. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（每条路径上黑色节点的数量相等）
  5. 每个叶子节点都是黑色的（此处的叶子节点指的是空节点）

【例】：

这里写图片描述

2、插入算法解析

在给已经平衡的RBTree树插入新节点时，有可能会导致树不满足红黑树的性质，这时候就需要重新调整树（节点颜色，树的旋转化等操作）。

又因为红黑树的性质里对于黑色节点的规定较多且根节点也为黑色节点，所以为了简单起见，我们默认新节点为红色节点，不满足性质再调整。

插入新节点大致可以分为五种情况，接下来我们来详细分析这五种情况：

情况一：

若树为空，插入后违反性质二，需要将新增节点颜色改为黑色。

这里写图片描述

情况二：

插入节点父节点为黑色，不违反任何性质，直接插入。

这里写图片描述

情况三

约定：pCur 为当前节点，pParent 为当前节点的父母节点，grand 为当前节点的祖父节点（当前节点父母节点的父母节点），uncle当前节点的父母节点的兄弟节点

【场景】：pCur为红色节点，pParent为红色节点，grand为黑色节点，uncle存在且为红色节点。

这里写图片描述

【解决方式】：

将pParent 和 uncle改成黑色节点；

若grand为根节点，则不用再处理；

若grand不为根节点，则令grand为红色节点，然后把grand 当成pCur,继续朝上更新；

情况四

约定：pCur 为当前节点，pParent 为当前节点的父母节点，grand 为当前节点的祖父节点（当前节点父母节点的父母节点），uncle当前节点的父母节点的兄弟节点

【场景】：pCur节点颜色为红色，pParent节点颜色为红，grand节点颜色为黑，uncle不存在 或是 uncle为黑色。

【解决方式】：

若pParent为grand的左孩子，pCur为pParent的左孩子，则进行右单旋转；

若pParent为grand的右孩子，pCur为pParent的右孩子，则进行左单旋转；

最后令pParent颜色变为黑色，grand颜色变为红色；

这里写图片描述

【注意】：
当uncle不存在时，此时的树每个支路的黑色节点个数是相等的，说明pCur是新插入的节点。

当uncle存在时，因为此时树的各支路黑色节点个数不等，所以此时的pCur不是新节点，而是调整后被改为红色，例如情况三中的图例所示。

情况五：

约定：pCur 为当前节点，pParent 为当前节点的父母节点，grand 为当前节点的祖父节点（当前节点父母节点的父母节点），uncle当前节点的父母节点的兄弟节点

【场景】：pCur节点颜色为红，pParent节点颜色为红，grand节点颜色为黑，uncle节点不存在 或是 uncle节点颜色为黑。

【解决方式】：

若pParent为grand的左孩子，pCur为pParent的右孩子，则针对pParent进行左单旋转；

若pParent为grand的右孩子，pCur为pParent的左孩子，则针对pParent进行右单旋转；

之后树的情况会变成情况四。

这里写图片描述

3、插入算法实现

基本步骤：
  • 若为空树，则创建一个新节点，令根指向这个新节点，并更新节点颜色为黑（性质2）；
  • 查找当前节点的插入位置 —-按照二叉搜索树的查找方式
  • 插入新节点
  • 更新节点颜色（之前的插入分析—-五种基本情况）
源码：

RBTree.h:

#pragma once
#include<stdio.h>
#include<iostream>using namespace std;
enum Color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode{
public:RBTreeNode(const K& key,const V& value,Color color = RED):_pLeft(NULL), _pRight(NULL), _pParent(NULL), _value(key,value), _color(color){}public:RBTreeNode<K,V>* _pLeft;RBTreeNode<K, V>* _pRight;RBTreeNode<K, V>* _pParent;Color _color;pair<K,V> _value;
};template<class K,class V>
class RBTree{typedef RBTreeNode<K, V> Node;typedef Node* pNode;
public:RBTree():_pRoot(NULL){}//插入bool InsertUnique(const pair<K,V>& value){return _InsertUnique(_pRoot,value);}//中序遍历void InOder(){cout << "中序遍历：" << endl;_InOder(_pRoot);}//判断是否是RBTreebool IsRBTree(){if (NULL == _pRoot)return true;size_t blackCount = 0;size_t count = 0;pNode pCur = _pRoot;//统计单支路黑色节点个数while (pCur){if (BLACK == pCur->_color)blackCount++;pCur = pCur->_pLeft;}return _IsRBTree(_pRoot, count, blackCount);}protected://判断是否是RBTreebool _IsRBTree(pNode pRoot, size_t count, const size_t blackCount){if (NULL == pRoot)return true;if (BLACK == pRoot->_color)count++;pNode pParent = pRoot->_pParent;if (pParent && pParent->_color == RED && pRoot->_color == RED){cout << "违反了性质3：不能有两个连续的红色节点" << endl;return false;}if (NULL == pRoot->_pLeft && NULL == pRoot->_pRight){if (count != blackCount){cout << "违反了性质4：每条路径上黑色节点的数量相等" << endl;return false;}}return _IsRBTree(pRoot->_pLeft, count, blackCount) && _IsRBTree(pRoot->_pRight, count, blackCount);}//中序遍历void _InOder(pNode pRoot){if (NULL == pRoot){return;}_InOder(pRoot->_pLeft);cout << "<" << pRoot->_value.first << "," << pRoot->_value.second << ">" << endl;_InOder(pRoot->_pRight);}//插入操作bool _InsertUnique(pNode& pRoot, const pair<K,V>& value){if (NULL == pRoot){//为空树,情况一pRoot = new Node(value.first,value.second);pRoot->_color = BLACK;return true;}//查找当前节点的插入位置pNode pCur = pRoot;pNode pParent = NULL; //标记while (pCur){if (value.second < pCur->_value.second){pParent = pCur;pCur = pCur->_pLeft;}else if (value.second > pCur->_value.second){pParent = pCur;pCur = pCur->_pRight;}else{//该树数据是不可重复的return false;}}//pCur指向NULL//插入新节点pCur = new Node(value.first,value.second);if (pCur->_value.second > pParent->_value.second){pParent->_pRight = pCur;pCur->_pParent = pParent;}else{pParent->_pLeft = pCur;pCur->_pParent = pParent;}//更新节点颜色及调整树的结构//情况二if (BLACK == pParent->_color)return true;//注意循环条件（因为三种情况下的变色都不会改变cur的颜色，而parent永远都是cur的parent）//所以只要parent的颜色为黑即可结束while (pParent && RED == pParent->_color){//pParent节点的颜色为红，则pParent的父母节点一定存在pNode grand = pParent->_pParent;if (pParent == grand->_pLeft){pNode uncle = grand->_pRight;if (uncle && RED == uncle->_color){//情况三pParent->_color = BLACK;uncle->_color = BLACK;grand->_color = RED;if (grand->_pParent && RED == grand->_pParent->_color){//继续朝上更新pCur = grand;pParent = pCur->_pParent;}else{break;}}if (NULL == uncle || (uncle && BLACK == uncle->_color)){//树需要旋转if (pCur == pParent->_pRight){//情况五RotateL(pParent);swap(pCur, pParent);//继续进行情况四}//情况四RotateR(grand);pParent->_color = BLACK;grand->_color = RED;return true;}}else{//pParent为grand的右孩子pNode uncle = grand->_pLeft;if (uncle && RED == uncle->_color){//情况三的镜像pParent->_color = BLACK;uncle->_color = BLACK;grand->_color = RED;if (grand->_pParent && RED == grand->_pParent->_color){//继续朝上更新pCur = grand;pParent = pCur->_pParent;}else{break;}}if (NULL == uncle || (uncle && BLACK == uncle->_color)){//需要旋转if (pCur == pParent->_pLeft){//情况五，镜像RotateR(pParent);swap(pCur, pParent);}//情况四RotateL(grand);pParent->_color = BLACK;grand->_color = RED;}}}//统一更新根节点颜色pRoot->_color = BLACK;}//左单旋void RotateL(pNode pParent){if (NULL == pParent)return;pNode ptr = pParent;pNode pSubR = ptr->_pRight;pNode pSubRL = pSubR->_pLeft;//标记ptr的父母节点pNode pPParent = ptr->_pParent;//令ptr成为pSubR的左子树pSubR->_pLeft = ptr;ptr->_pParent = pSubR;//pSubRL的值是小于pSubR的值，大于ptr的值，所以可以令pSubRL作为ptr的右子树ptr->_pRight = pSubRL;if (pSubRL)pSubRL->_pParent = ptr;pSubR->_pParent = pPParent;//判断ptr上一节点的三种情况if (NULL == pPParent){//ptr为根节点_pRoot = pSubR;}else{if (ptr == pPParent->_pLeft)pPParent->_pLeft = pSubR;elsepPParent->_pRight = pSubR;}}//右单旋void RotateR(pNode pParent){if (NULL == pParent)return;pNode ptr = pParent;pNode pSubL = ptr->_pLeft;pNode pSubLR = pSubL->_pRight;//标记ptr的父母节点pNode pPParent = ptr->_pParent;//令ptr成为pSubL的左子树pSubL->_pRight = ptr;ptr->_pParent = pSubL;//pSubLR的值是大于pSubL的值，小于ptr的值，所以可以令pSubLR作为ptr的左子树ptr->_pLeft = pSubLR;if (pSubLR)pSubLR->_pParent = ptr;pSubL->_pParent = pPParent;//判断ptr上一节点的三种情况if (NULL == pPParent){//ptr为根节点_pRoot = pSubL;}else{if (ptr == pPParent->_pLeft)pPParent->_pLeft = pSubL;elsepPParent->_pRight = pSubL;}}private:pNode _pRoot;
};

test.cpp:

#include<Windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include"RBTree.h"using namespace std;//RBTree
void test4(){int a[] = { 10, 7, 8, 15, 5, 6, 11, 13, 12 };RBTree<int, int> rbtree;for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i){rbtree.InsertUnique(make_pair(i, a[i]));}//测试该红黑树是否满足二叉搜索树的性质rbtree.InOder();//测试树是否满足红黑树的基本性质if (rbtree.IsRBTree())cout << "该树满足红黑树的基本性质" << endl;elsecout << "该树不满足红黑树的基本性质" << endl;}int main(){test4();system("pause");return 0;
}

程序运行结果：

这里写图片描述

4、红黑树的应用思考

模拟实现一个加入迭代器的红黑树
模拟实现一个map（使用红黑树实现）
模拟实现一个set（使用红黑树实现）

这篇关于【数据结构】模拟实现红黑树（RBTree）的插入算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/615294。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2