红黑树源代码（进阶与细节解释）

目录

对于结点的修改

红黑树模板参数的控制

红黑树结点当中存储的数据

 对于insert函数的细节修改

 迭代器的代码

迭代器类的添加

迭代器的++

迭代器的--

正向迭代器的代码

红黑树代码全部展示：

看完前两篇的文章，相信对于红黑树有了一定的了解，知道红黑树是怎么样子进行插入的，是怎么样进行查找的，知道了底层是怎么样子的，知道了其与AVL树，二叉搜索树有什么区别了。

但是对于set，map的底层又全是红黑树，set与map的区别就是其键值对一个是k，k型，一个是k，v型的，所以就有了封装，（对于封装后面会讲解什么是封装）二者底层全是同一份的红黑树，但是前面两篇文章的红黑树要不只能使用与k，k型，要不就是k，v型，所以就要对红黑树的源代码进行修改，进行细节上的修饰与进阶。

对于结点的修改

对于此其实不需要进行特别的修改，但是要注意这里的T，如果要是对应的set，那么他就是K，如果是map那么他就是pair<k,v>。

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

红黑树模板参数的控制

我们都知道，set是KK模型的容器，而map是KV模型的容器，那我们如何用一棵KV模型的红黑树同时实现map和set呢？

 这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。

template<class K, class T>
class RBTree

这里的T也就是对应的结点设置的T，上面也说了，set对应的是K，map是pair<k,v>。

那么下面就看看set容器与map容器中的传的模板参数吧。

set

template<class K>
class set
{
public://...
private:RBTree<K, K> _t;
};

map

template<class K, class V>
class map
{
public://...
private:RBTree<K, pair<K, V>> _t;
};

那能不能不要红黑树的第一个模板参数，只保留第二个模板参数呢？

乍眼一看好像是可以的，因为此时红黑树的第二个模板参数当中也是有键值Key的，但实际上红黑树的第一个模板参数是不能省略的。

对于set容器来说，省略红黑树的第一个参数当然没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase。

红黑树结点当中存储的数据

现在红黑树的模板参数变成了K和T，那么红黑树结点当中存储的应该是什么呢？

 前面说到，由于上层容器的不同，底层红黑树当中的K和T也是不同的：

  • set容器：K和T都代表键值Key。
  • map容器：K代表键值Key，T代表由Key和Value构成的键值对。

对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。

这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对。

所以说其实结点的设置其实没有太大的修改，还是与原本还差不多。

 对于insert函数的细节修改

在做完上面的修改后，原本的代码如果在运行下，是会有些问题的，（问题是在封装出现）这里问题是什么就不多说了，

修改起来也是很简单

只需要把其返回值修改为如此就可以。

然后第一个参数就是结点指针，第二个是bool值，插入成功返回true，失败false。 

 迭代器的代码

对于解决迭代器的问题，首先就是要添加一个迭代器类，然后再解决迭代器的++/--，对于红黑树的++，--。用语言来说是很简便的。

迭代器类的添加

template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
};
template<class K, class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator <T, T&, T*> iterator;typedef __TreeIterator <T, const T&, const T*> const_iterator;
//......
private:Node* _root = nullptr;
};

迭代器的++

核心：中序的下一个

  1. it指向的节点，右子树不为空，下一个就是右子树的最左节点。
  2. it指向的节点，右子树为空，it所在的子树全已访问完了，那么需要往上找孩子是父亲做节点的那个祖先。

迭代器的--

  1. it的左子树不为空，下一个就为左子树的最有节点。
  2. it的左子树为空，沿着根找孩子是父亲右节点的那个祖先。

代码展示：

	Self& operator--(){//走的是中序  左 根 右if (_node->_left){//左不为空，下一个就是左子树的最右Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{//左为空，没根找孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator++(){//走的是中序  左 根 右if (_node->_right){//右子树不为空，下一个就是右子树的最左结点Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

正向迭代器的代码

template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator--(){//走的是中序  左 根 右if (_node->_left){//左不为空，下一个就是左子树的最右Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{//左为空，没根找孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator++(){//走的是中序  左 根 右if (_node->_right){//右子树不为空，下一个就是右子树的最左结点Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

对于迭代器的最后一步就是添加上begin（），end（）函数。

红黑树代码全部展示：

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
enum Colour
{RED,BLACK,
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator--(){//走的是中序  左 根 右if (_node->_left){//左不为空，下一个就是左子树的最右Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}else{//左为空，没根找孩子是父亲右的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator++(){//走的是中序  左 根 右if (_node->_right){//右子树不为空，下一个就是右子树的最左结点Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};template<class K,class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator <T, T&, T*> iterator;typedef __TreeIterator <T,const T&,const T*> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}	iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}pair<Node*, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);;}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(cur, false);;}}cur = new Node(data);Node* newnode = cur;//默认结点颜色为红色if (kot(parent->_data) < kot(data)){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//大前提//parent在左if (parent == grandfather->_left){Node* uncle = grandfather->_right;//Node* uncle = parent->_right;//错误二if (uncle && uncle->_col == RED){//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红//     g//   p   u// c// //解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑//     g//   p   u// c// // 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接breakRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑//       g//   p      u//     c// 解决：对p左单旋，后变为情景二。RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//情景大概反着来{//1  uncleNode* uncle = grandfather->_left;//错误一//Node* uncle = parent->_right;//错误一if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right)//2{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//3{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//最后_root->_col = BLACK;return make_pair(newnode, true);;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)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;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}iterator Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return iterator(cur);}}return end();}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << kof(root->_data) << " ";_InOrder(root->_right);}bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){if (refVal != blacknum){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED){if (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(){//1:是否存在 红-红 //每条路径黑色结点是否相同个数//最长的不超过最短的二倍//根，叶子为黑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);}
private:Node* _root = nullptr;
};

下一篇文章就开始进行封装的解释。

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

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

相关文章

飘香水果购物网站：基于SpringBoot的架构设计

飘香水果购物网站：基于SpringBoot的架构设计

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常适…
阅读更多...
【C++】模拟实现hash_table(哈希表)

【C++】模拟实现hash_table(哈希表)

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:实战项目集 ⚙️操作环境:Visual Studio 2022 目录 一.了解项目功能 二.逐步实现项目功能模块及其逻辑详解 &#x1f4cc;实现HashNode类模板 &#x1f38f;构造HashNode类成员变量 &#x1f38f;实现HashNode类构造函数…
阅读更多...
家里养有宠物应该用哪款宠物空气净化器比较好？哪款最能吸毛？

家里养有宠物应该用哪款宠物空气净化器比较好？哪款最能吸毛？

这不是国庆节刚过吗&#xff0c;我的小猫终于是平安的度过了在农村生活的时光&#xff0c;之前还担心会不会被爸妈嫌弃&#xff0c;这下好了&#xff0c;嫌弃也过了国庆节。 但是一把猫咪带回出租房&#xff0c;由于几天不在房子里待&#xff0c;猫咪对熟悉的环境又特别激动&a…
阅读更多...
视频怎么做成扫码展示？视频二维码在线做的方法

视频怎么做成扫码展示？视频二维码在线做的方法

视频想要快速的分享给其他人&#xff0c;选择生成二维码是一种很方便的形式&#xff0c;其他人只需要扫描二维码就可以在线查看视频&#xff0c;与其他分享方式相比更加的简单、方便。现在日常生活中有很多场景都会有视频二维码的应用&#xff0c;简化了获取视频的流程&#xf…
阅读更多...
JavaEE: 深入解析HTTP协议的奥秘(3)

JavaEE: 深入解析HTTP协议的奥秘(3)

文章目录 HTTP认识 "报头"(Header)认识 "状态码"(status code) HTTP JavaEE: 深入解析HTTP协议的奥秘(2) 书接上文~ 认识 “报头”(Header) Header 的整体的格式是"键值对"结构. 每个键值对占一行,键和值之间使用分号分隔. Host 表示服务器主…
阅读更多...
【基础篇】一个键值数据库包含什么？

【基础篇】一个键值数据库包含什么？

背景 今天&#xff0c;在构造这个简单的键值数据库时&#xff0c;我们只需要关注整体架构和核心模块。这就相当于医学上在正式解剖人体之前&#xff0c;会先解剖一只小白鼠。我们通过剖析这个最简单的键值数据库&#xff0c;来迅速抓住学习和调优 Redis 的关键。 我们把这个简…
阅读更多...
STM32外设应用知识详解

STM32外设应用知识详解

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…
阅读更多...
RKMEDIA画面质量调节-QP调节

RKMEDIA画面质量调节-QP调节

QP是在视频采集编码过程中的量化参数&#xff0c;其值与画面质量成反比&#xff0c;即QP值越大画面质量越小&#xff0c;其具体调整方法如下&#xff1a; typedef struct rkVENC_RC_PARAM_S {RK_U32 u32ThrdI[RC_TEXTURE_THR_SIZE]; // [0, 255]RK_U32 u32ThrdP[RC_TEXTURE_TH…
阅读更多...
如何基于 RLHF 来优化 ChatGPT 类型的大语言模型

如何基于 RLHF 来优化 ChatGPT 类型的大语言模型

&#x1f6b4;前言 对于ChatGPT来说&#xff0c;RLHF是其训练的核心。所谓RLHF&#xff0c;即Reinforcement Learning with Human Feedback&#xff0c;基于人类反馈的强化学习。这项技术通过结合模型自身的生成能力和人类专家的反馈&#xff0c;为改进文本生成质量提供了新的…
阅读更多...
解决Android Studio中使用lombok插件错误: 找不到符号的问题

解决Android Studio中使用lombok插件错误: 找不到符号的问题

问题 主要是想节省实体类的set、get等方法&#xff0c;使用lombok报错如下&#xff1a; 解决方案 由于Android的限制&#xff0c;在Android中使用lombok兼容极其麻烦&#xff0c;如果你只是想减少set、get等代码可以直接使用kotlin的data class 示例 data class KotlinTes…
阅读更多...
等级保护等保资料原件合集（word源资料）

等级保护等保资料原件合集（word源资料）

第二章 系统定级与安全域 2.1 系统定级 2.1.1 不同等级的安全保护能力 2.1.2 重要信息系统 2.1.3 定级参考 2.2 安全域定义 2.2.1 安全域定义方法 2.2.2 安全域等级描述 第三章 实施方案设计 3.1 三级等保要求 3.2 基本要求的详细技术要求 3.2.1 物理安全 3.2.2 网…
阅读更多...
Unity 从零开始的框架搭建1-1 unity中对象调用的三种方式的优缺点分析【干货】

Unity 从零开始的框架搭建1-1 unity中对象调用的三种方式的优缺点分析【干货】

该文章专栏是向QFrameWork作者凉鞋老师学习总结得来&#xff0c;吃水不忘打井人&#xff0c;不胜感激 Unity 框架搭建学习笔记1-1&#xff0c;前一个1代表凉鞋的第一季教程&#xff0c;后一个1代表该季第一篇我的文章 unity中对象调用的三种方式 方法调用&#xff0c;例如&…
阅读更多...
Qt设计登录界面

Qt设计登录界面

优化登录框&#xff1a; 将两个按钮连接到槽函数 在构造函数中定义 connect(this->btn1,&QPushButton::clicked,this,&Logon::my_slot);connect(this->btn2,&QPushButton::clicked,this,&Logon::my_cancel); 定义登录按钮连接的槽函数 void Logon::my…
阅读更多...
基于Java语言的充电桩平台+云快充协议+充电桩管理后台+充电桩小程序

基于Java语言的充电桩平台+云快充协议+充电桩管理后台+充电桩小程序

软件架构 1、提供云快充底层桩直连协议&#xff0c;版本为云快充1.5&#xff0c;对于没有对接过充电桩系统的开发者尤为合适&#xff1b; 2、包含&#xff1a;启动充电、结束充电、充电中实时数据获取、报文解析、Netty通讯框架、包解析工具、调试器模拟器软件等&#xff1b;…
阅读更多...
CMake 属性之目标属性

CMake 属性之目标属性

【写在前面】 CMake 可以通过属性来存储信息。它就像是一个变量&#xff0c;但它被附加到一些其他的实体上&#xff0c;像是一个目录或者是一个目标。例如一个全局的属性可以是一个有用的非缓存的全局变量。 在 CMake 的众多属性中&#xff0c;目标属性 ( Target Properties ) …
阅读更多...
NodeJS智慧社区管理微信小程序-计算机毕业设计源码40623

NodeJS智慧社区管理微信小程序-计算机毕业设计源码40623

摘 要 随着中国经济的飞速增长&#xff0c;消费者的智能化水平不断提高&#xff0c;许多智能手机和相关的软件正在得到更多的关注和支持。其中&#xff0c;智慧社区管理微信小程序更是深得社区人员的喜爱&#xff0c;它的出现极大地改善了社区人员的生活质量&#xff0c;同时&…
阅读更多...
宠物咖啡馆在线体验：SpringBoot框架的创新应用

宠物咖啡馆在线体验：SpringBoot框架的创新应用

4系统概要设计 4.1概述 本系统采用B/S结构(Browser/Server,浏览器/服务器结构)和基于Web服务两种模式&#xff0c;是一个适用于Internet环境下的模型结构。只要用户能连上Internet,便可以在任何时间、任何地点使用。系统工作原理图如图4-1所示&#xff1a; 图4-1系统工作原理…
阅读更多...
云微客AI直播矩阵，让小白轻松上手的必备直播利器

云微客AI直播矩阵，让小白轻松上手的必备直播利器

现在直播带货都已经杀疯了&#xff0c;在新趋势下&#xff0c;AI智能直播应运而生。AI智能直播相较于传统直播&#xff0c;直播模式对于场地的要求和人员的要求都相对较低&#xff0c;大大降低了我们的试错成本&#xff0c;同时直播矩阵系统也为企业和个人带来了低成本、高效率…
阅读更多...
浅析基于双碳目标的光储充一体化电站状态评估技术

浅析基于双碳目标的光储充一体化电站状态评估技术

摘要&#xff1a;全国碳市场拉开了我国能源结构加速转型的大幕&#xff0c;催生了光伏、储能和新能源汽车等一批绿色产业的兴起&#xff0c;同时随着利好政策扶植和消费者的青睐&#xff0c;光伏、储能和新能源汽车市场均加快发展。但传统的充电桩和光伏电站都是分开建设&#…
阅读更多...
如何在电脑上创建虚拟网卡

如何在电脑上创建虚拟网卡

1.右键点击此电脑&#xff0c;选择——管理 2.选择设备管理器——网络适配器&#xff0c;在点击操作选择 添加过时硬件 3.点击 下一页 4.在这里选择网络适配器&#xff0c;点击下一页 5.选择微软的环回适配器 6.打开控制面板 7.点击网络和Internet 8.点击网络和共享中心 9…
阅读更多...
最新文章

Copyright @ 2022~2023