红黑树的模拟实现

一、介绍

1. 概念

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

2. 性质

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

3. 结点定义

enum Colour//两种颜色
{RED,BLACK
};//定义红黑树的结点
template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

二、插入的3种情况

（一）情况1

  • 因为cur为当前插入新结点（红色），而不能有连在一起的红色节点，所以parent结点需要变成黑色。
  • 控制每条路径上黑节点的数量相同，那么就要把uncle变黑
  • grandparent如果不是根节点，需要继续向上调整，所以grandparent需要变成红色

//情况1：uncle存在且为红色
if (uncle != nullptr && uncle->_col == RED)
{//调整颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上调整cur = grandfather;parent = cur->_parent;
}

 

（二）情况2

//情况2
if (cur == parent->_left)
{//             grandfather//        parent//    curRotateR(grandfather);//右旋转//调整颜色parent->_col = BLACK;grandfather->_col = RED;}

 

（三）情况3

 

 

else//cur在parent的右边
{//             grandfather//        parent//              curRotateL(parent);//先左旋转RotateR(grandfather);//再右旋转//调整颜色cur->_col = BLACK;grandfather->_col = RED;
}

（四）插入代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr)//如果开始结点为空{_root = new Node(kv);_root->_col = BLACK;//根节点为黑色return true;}Node* parent = nullptr;Node* cur = _root;//寻找应该插入的位置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//已经存在一样的值，直接返回false{return false;}}//链接cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//调整while (parent && parent->_col == RED)//如果父亲结点是黑色直接结束{Node* grandfather = parent->_parent;if (parent == grandfather->_left){//         grandfather//      parent     uncle//   cur//Node* uncle = grandfather->_right;//情况1：uncle存在且为红色if (uncle != nullptr && uncle->_col == RED){//调整颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上调整cur = grandfather;parent = cur->_parent;}else//uncle不存在或者uncle为黑色{   //情况2if (cur == parent->_left){//             grandfather//        parent//    curRotateR(grandfather);//右旋转//调整颜色parent->_col = BLACK;grandfather->_col = RED;}else//cur在parent的右边{//             grandfather//        parent//              curRotateL(parent);//先左旋转RotateR(grandfather);//再右旋转//调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}else//parent == grandfather->_right{Node* uncle = grandfather->_left;//         g//      u    p//             c////情况1：uncle存在且为红色if (uncle != nullptr && uncle->_col == RED){//调整颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上调整cur = grandfather;parent = cur->_parent;}else//uncle不存在或者uncle为黑色{if (cur == parent->_right){//           g//              p//                 cRotateL(grandfather);//调整颜色parent->_col = BLACK;grandfather->_col = RED;}else{//         g//             p//           cRotateR(parent);//先右旋RotateL(grandfather);//再左旋//调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

三、判断是否近似平衡

//	// 根节点->当前节点这条路径的黑色节点的数量
bool Check(Node* root, int blacknum, const int refVal)
{if (root == nullptr)//走到了一条路径的尽头{if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);
}bool IsBalance()//判断是否平衡
{if (_root == nullptr)return true;if (_root->_col == RED)//根结点如果是红色return false;int refVal = 0;Node* cur = _root;while (cur)//计算其中一条路径上的黑色节点数量作为参考值{if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);
}

四、完整代码

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
enum Colour//两种颜色
{RED,BLACK
};//定义红黑树的结点
template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr)//如果开始结点为空{_root = new Node(kv);_root->_col = BLACK;//根节点为黑色return true;}Node* parent = nullptr;Node* cur = _root;//寻找应该插入的位置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//已经存在一样的值，直接返回false{return false;}}//链接cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//调整while (parent && parent->_col == RED)//如果父亲结点是黑色直接结束{Node* grandfather = parent->_parent;if (parent == grandfather->_left){//         grandfather//      parent     uncle//   cur//Node* uncle = grandfather->_right;//情况1：uncle存在且为红色if (uncle != nullptr && uncle->_col == RED){//调整颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上调整cur = grandfather;parent = cur->_parent;}else//uncle不存在或者uncle为黑色{   //情况2if (cur == parent->_left){//             grandfather//        parent//    curRotateR(grandfather);//右旋转//调整颜色parent->_col = BLACK;grandfather->_col = RED;}else//cur在parent的右边{//             grandfather//        parent//              curRotateL(parent);//先左旋转RotateR(grandfather);//再右旋转//调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}else//parent == grandfather->_right{Node* uncle = grandfather->_left;//         g//      u    p//             c////情况1：uncle存在且为红色if (uncle != nullptr && uncle->_col == RED){//调整颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上调整cur = grandfather;parent = cur->_parent;}else//uncle不存在或者uncle为黑色{if (cur == parent->_right){//           g//              p//                 cRotateL(grandfather);//调整颜色parent->_col = BLACK;grandfather->_col = RED;}else{//         g//             p//           cRotateR(parent);//先右旋RotateL(grandfather);//再左旋//调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}// 根节点->当前节点这条路径的黑色节点的数量bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr)//走到了一条路径的尽头{if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}bool IsBalance()//判断是否平衡{if (_root == nullptr)return true;if (_root->_col == RED)//根结点如果是红色return false;int refVal = 0;Node* cur = _root;while (cur)//计算其中一条路径上的黑色节点数量作为参考值{if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}void RotateL(Node* parent)//左单旋{Node* parentParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;//更新调整结点的父指针指向parent->_parent = subR;//subRL->_parent = parent;错误，没有判断subRL是不是为空if (subRL != nullptr){subRL->_parent = parent;}if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}//更新平衡因子//parent->_bf = subR->_bf = 0;}void RotateR(Node* parent)//右单旋{Node* parentParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//更新调整结点的父指针指向if (subLR != nullptr){subLR->_parent = parent;}subL->_right = parent;//更新调整结点的父指针指向parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{//需要先判断subR应该链接在parentParent的哪一侧if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}//更新平衡因子//parent->_bf = subL->_bf = 0;}void InOrder()//中序遍历{_InOrder(_root);cout << endl;}void _InOrder(Node* root)//中序遍历{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}int Height(){return _Height(_root);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}
private:Node* _root = nullptr;
};

1. 测试用例1

#include"RBTree.h"
int main()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };int a[] = { 790,760,969,270,31,424,377,24,702 };RBTree<int, int> t;for (auto e : a){if (e == 702){int i = 0;}cout << "Insert:" << e << "->";t.Insert(make_pair(e, e));cout << t.IsBalance() << endl;}t.InOrder();cout << t.IsBalance() << endl;return 0;
}

2. 测试用例2

#include"RBTree.h"int main()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);//cout << v.back() << endl;}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){if (e == 29365){int i = 0;}//cout << "Insert:" << e << "->";t.Insert(make_pair(e, e));//cout << t.IsBalance() << endl;}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalance() << endl;cout << t.Height() << endl;cout << t.Size() << endl;size_t begin1 = clock();for (auto e : v){t.Find(e);}for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;return 0;
}

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

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

相关文章

【Redis】list常用命令内部编码使用场景

【Redis】list常用命令内部编码使用场景

文章目录 前置知识列表类型的特点 命令LPUSHLPUSHXRPUSHRPUSHXLRANGELPOPRPOPLINDEXLREMLINSERTLTRIMLSETLLEN 阻塞版本命令BLPOPBRPOP 命令总结内部编码测试内部编码 使用场景消息队列分频道的消息队列 模拟栈和队列 前置知识 列表类型是⽤来存储多个有序的字符串&#xff0c…
阅读更多...
吴恩达《机器学习》7-1-＞7-4:过拟合问题、代价函数、线性回归的正则化、正则化的逻辑回归模型

吴恩达《机器学习》7-1-＞7-4:过拟合问题、代价函数、线性回归的正则化、正则化的逻辑回归模型

一、过拟合的本质 过拟合是指模型在训练集上表现良好&#xff0c;但在新数据上的泛化能力较差。考虑到多项式回归的例子&#xff0c;我们可以通过几个模型的比较来理解过拟合的本质。 线性模型&#xff08;欠拟合&#xff09;&#xff1a; 第一个模型是一个线性模型&#xff0…
阅读更多...
量子计算和量子通信技术：引领潜力无限的未来

量子计算和量子通信技术：引领潜力无限的未来

近年来&#xff0c;随着量子计算和量子通信技术的迅速发展&#xff0c;它们在各个领域的广泛应用前景引起了人们的极大兴趣。本文将深入探讨量子计算和量子通信技术的普遍应用&#xff0c;以及它们预示的未来&#xff0c;同时提出业内人士需要注意的事项。 介绍&#xff1a;量子…
阅读更多...
OushuDB 专家认证第四期报名开始啦！

OushuDB 专家认证第四期报名开始啦！

OushuDB 专家认证培训第四期今日正式启动&#xff01;本次培训为偶数科技面向生态合作伙伴与客户公开举办的线上培训&#xff0c;旨在共同发展 OushuDB 生态。 报名时间&#xff1a;2023年11月9日9:00—11月30日12:00 报名方式&#xff1a;偶数科技官网&#xff08;点击下方阅…
阅读更多...
C/C++数据结构之链表题目答案与解析

C/C++数据结构之链表题目答案与解析

个人主页&#xff1a;点我进入主页 专栏分类&#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 欢迎大家点赞&#xff0c;评论&#xff0c;收藏。 一起努力&#xff0c;一起奔赴大厂。 目录 1.前言 2.题目…
阅读更多...
灵活运用Vue指令：探究v-if和v-for的使用技巧和注意事项

灵活运用Vue指令：探究v-if和v-for的使用技巧和注意事项

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 ⭐ 专栏简介 &#x1f4d8; 文章引言 一、作…
阅读更多...
2023年Q3乳品行业数据分析（乳品市场未来发展趋势）

2023年Q3乳品行业数据分析（乳品市场未来发展趋势）

随着人们生活水平的不断提高以及对健康生活的追求不断增强&#xff0c;牛奶作为优质蛋白和钙的补充品&#xff0c;市场需求逐年增加。 今年Q3&#xff0c;牛奶乳品市场仍呈增长趋势。根据鲸参谋电商数据分析平台的相关数据显示&#xff0c;2023年7月-9月&#xff0c;牛奶乳品市…
阅读更多...
计算机毕设 大数据工作岗位数据分析与可视化 - python flask

计算机毕设 大数据工作岗位数据分析与可视化 - python flask

文章目录 0 前言1 课题背景2 实现效果3 项目实现3.1 概括 3.2 Flask实现3.3 HTML页面交互及Jinja2 4 **完整代码**5 最后 0 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕设题目缺少创新和亮点&#xff0c;往往达不到毕业答辩的要…
阅读更多...
【Excel】补全单元格值变成固定长度

【Excel】补全单元格值变成固定长度

我们知道股票代码都为6位数字&#xff0c;但深圳中小板代码前面以0开头&#xff0c;数字格式时前面的0会自动省略&#xff0c;现在需要在Excel表格补全它。如下图&#xff1a; 这时我们需要用到特殊的函数&#xff1a;TEXT或者RIGHT TEXT函数是Excel中一个非常有用的函数。TEX…
阅读更多...
c: struct sort descending and ascending in windows and Ubuntu

c: struct sort descending and ascending in windows and Ubuntu

/*** file StudentStructSort.h* author geovindu,Geovin Du,涂聚文 (geovindu163.com)* ide: vscode c11,c17 Ubuntu 22.4* brief 结构体排序示例* date 2023-11-05* version 0.1* copyright geovindu 站在巨人的肩膀上 Standing on the Shoulders of Giants**/#ifnd…
阅读更多...
海康工业相机如何提高相机帧率

海康工业相机如何提高相机帧率

影响帧率的因素 相机参数 帧率限制使能 像素格式 曝光时间 数据包大小&#xff08;网口&#xff09; 相机默认参数 ADC位深 系统环境设置
阅读更多...
opencv创建图片,绘制图片,画框,划线,改变像素点颜色

opencv创建图片,绘制图片,画框,划线,改变像素点颜色

文章目录 创建空白图片创建一张渐变色彩色绘制多边形绘制多线改变像素点颜色 创建空白图片 bool tool_class::creatEmpty(int width, int height, std::string image_p) {// 创建一个空白图像cv::Mat blankImage(height, width, CV_8UC3, cv::Scalar(255, 255, 255));// 保存图…
阅读更多...
CSS3 分页、框大小、弹性盒子

CSS3 分页、框大小、弹性盒子

一、CSS3分页&#xff1a; 网站有很多个页面&#xff0c;需要使用分页来为每个页面做导航。示例&#xff1a; <style> ul.pagination { display: inline-block; padding: 0; margin: 0; } ul.pagination li {display: inline;} ul.pagination li a { color: black; f…
阅读更多...
给CAD中添加自定义菜单CUIX

给CAD中添加自定义菜单CUIX

本文以AutoCAD2020为例&#xff0c;介绍如何添加自定义菜单。 打开AutoCAD2020&#xff0c;在命令行执行CUI并回车&#xff0c;出现菜单 进入菜单编辑界面 点击传输&#xff0c;然后新建 在菜单上右键&#xff0c;添加自定义菜单 点击保存&#xff0c;即可存为cuix文件。之后…
阅读更多...
arduino 简易智能花盆

arduino 简易智能花盆

编辑器&#xff1a;arduino IDE 主板&#xff1a;arduino uno 传感器&#xff1a; 0.96寸的OLED屏&#xff08;四脚&#xff09; 声音模块 土壤温湿度模块 DS18B20温度模块&#xff08;这里用到防水的&#xff09; 光敏电阻模块&#xff08;买成三脚的了只能显示高低&#x…
阅读更多...
【uniapp】文件授权验真系统(含代码)

【uniapp】文件授权验真系统(含代码)

文章目录 前言一、框架选用二、数据库设计三、设计上传列表四、上传操作1.前端2.后端 五、修改操作六、访问操作七、二维码生成八、二维码访问九、删除操作总结 前言 吐槽&#xff1a;终于开通了【资源绑定】的功能了&#xff0c;之前还要一个一个的去贴链接 之前的同学联系…
阅读更多...
家居美学：将水离子壁炉融入你的现代装饰

家居美学：将水离子壁炉融入你的现代装饰

当谈及家居装饰和壁炉选择时&#xff0c;水离子雾化壁炉是一个备受瞩目的话题。水离子雾化壁炉的美学价值&#xff0c;还为室内装饰带来全新的维度。它甚至能够激发室内装饰的灵感。 水离子雾化壁炉是现代美学的标志&#xff0c;融合了简洁、线条清晰的设计。这种壁炉常常采用不…
阅读更多...
地区 IP 库

地区 IP 库

地区 & IP 库 yudao-spring-boot-starter-biz-ip (opens new window)业务组件&#xff0c;提供地区 & IP 库的封装。 #1. 地区 AreaUtils (opens new window)是地区工具类&#xff0c;可以查询中国的省、市、区县&#xff0c;也可以查询国外的国家。 它的数据来自 …
阅读更多...
React动态生成二维码和毫米（mm）单位转像素（px）单位

React动态生成二维码和毫米（mm）单位转像素（px）单位

一、使用qrcode.react生成二维码&#xff0c;qrcode.react - npm 很简单&#xff0c;安装依赖包&#xff0c;然后引用就行了 npm install qrcode.react或者 yarn add qrcode.react直接上写好的代码 import React, {useEffect, useState} from react; import QRCode from qr…
阅读更多...
6.存储器概述，主存储器

6.存储器概述，主存储器

目录 一. 存储系统基本概念 &#xff08;1&#xff09;存储系统的层次结构 &#xff08;2&#xff09;分类 &#xff08;3&#xff09;存储器的性能指标 二. 主存储器的基本组成 三. SRAM和DRAM 四. 只读存储器ROM 五. 提升主存速度的方法 &#xff08;1&#xff09;双…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023