map、set底层封装模拟实现(红黑树)
文章目录
- 一、红黑树
- 1.1红黑树的规则:
- 1.2红黑树的插入操作
- 1.2.1不需要旋转(如果叔叔存在且为红,这里的C表示孩子,P表示父亲,U表示叔叔,G表示祖父),包含四种情况,无论孩子在哪里,都是只需要改变叔叔和父亲的颜色为黑,祖父为红,然后向上继续走,C = G
- 1.2.2需要旋转(左旋,右旋,左右双旋,右左双旋),叔叔不存在或者为黑
- 1.2红黑树的插入代码
- 1.3红黑树的整体框架
- 二、map、set的底层封装
- 2.1set的底层封装
- 2.2map的底层封装
- 2.3红黑树的底层封装
一、红黑树
相较于前面的AVL树,红黑树的优势是:旋转次数减少,效率提高了,同时还保留了AVL树的查找优势
1.1红黑树的规则:
1.每个节点不是红色就是黑色
2.红色节点的孩子一定是黑色节点
3.不能有连续的红色节点
4.每条路径(走到空为止)上的黑色节点数量相同
5.最短路径<=最长路径<=2最短路径(当某条路径只有黑色节点,而另一条路径红色节点数量和黑色节点相同,那么最长路径就是最短路路径的两倍)
1.2红黑树的插入操作
1.2.1不需要旋转(如果叔叔存在且为红,这里的C表示孩子,P表示父亲,U表示叔叔,G表示祖父),包含四种情况,无论孩子在哪里,都是只需要改变叔叔和父亲的颜色为黑,祖父为红,然后向上继续走,C = G
1.2.2需要旋转(左旋,右旋,左右双旋,右左双旋),叔叔不存在或者为黑
右旋的情况(这里省略了C,P,U所连的节点)
左右双旋的情况(这里省略了C,P,U所连的节点)
下面两种情况省略
1.2红黑树的插入代码
bool Insert(const pair<K, V>& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (data.first > cur->_data.first){parent = cur;cur = cur->_right;}else if (data.first < cur->_data.first){parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(data);if (parent->_data.first > cur->_data.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//判断父亲是否为红,为黑就不管while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在且为红{uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;//继续向上处理parent = cur->_parent;}else{if (cur == parent->_left){//叔叔为黑或者叔叔不存在RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;parent->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;//继续向上处理parent = cur->_parent;}else{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;}void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppnode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}
}void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppnode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}
}
1.3红黑树的整体框架
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;//颜色定义
enum color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{typedef RBTreeNode<K, V> Node;pair<K, V> _data;Node* _left;Node* _right;Node* _parent;color _col;//构造函数RBTreeNode(const pair<K, V>& data):_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _data(data){}
};template<class K,class V>
class RBTree
{
public:typedef RBTreeNode<K, V> Node;bool Insert(const pair<K, V>& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (data.first > cur->_data.first){parent = cur;cur = cur->_right;}else if (data.first < cur->_data.first){parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(data);if (parent->_data.first > cur->_data.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//判断父亲是否为红,为黑就不管while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在且为红{uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;//继续向上处理parent = cur->_parent;}else{if (cur == parent->_left){//叔叔为黑或者叔叔不存在RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;parent->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;//继续向上处理parent = cur->_parent;}else{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;}void Inorder(){_Inorder(_root);}private:void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_data.first << endl;_Inorder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppnode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppnode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}Node* _root = nullptr;
};
二、map、set的底层封装
这里我们需要加上迭代器和仿函数(为了套用同一个红黑树的模版)
map有两个模版参数、set只有一个模版参数,因此我们需要加一个仿函数来确定是map还是set
2.1set的底层封装
namespace SF
{//仿函数template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K,const K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K& key){return _t.Insert(key);}private:RBTree<K,const K, SetKeyOfT> _t;};
}
2.2map的底层封装
namespace SF
{template<class K,class V> class map{struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pair<K,V>& data){return _t.Insert(data);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}
2.3红黑树的底层封装
#pragma once
#include<vector>enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;T _data;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){if (_node->_right){// 右子树的中序第一个(最左节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){// return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator== (const Self & s){return _node == s._node;}
};// set->RBTree<K, K, SetKeyOfT>
// map->RBTree<K, pair<K, V>, MapKeyOfT>// KeyOfT仿函数 取出T对象中的key
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T> iterator;iterator begin(){Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}iterator end(){return iterator(nullptr);}bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;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 false;}}cur = new Node(data); // 红色的if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一:叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二:叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){// g// p u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 情况一:叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二:叔叔不存在或者存在且为黑// 旋转+变色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}private:Node* _root = nullptr;
};
相关文章:

map、set底层封装模拟实现(红黑树)
文章目录 一、红黑树1.1红黑树的规则:1.2红黑树的插入操作1.2.1不需要旋转(如果叔叔存在且为红,这里的C表示孩子,P表示父亲,U表示叔叔,G表示祖父),包含四种情况,无论孩子在哪里&…...
PHP8.2-xlswriter 扩展
https://pecl.php.net/package/xlswriter ### 进入/root/ cd ~ ### 下载扩展 wget https://pecl.php.net/get/xlswriter-1.5.5.tgz ### 解压扩展 tar -zxvf xlswriter-1.5.5.tgz ### 进入扩展目录 cd xlswriter-1.5.5 ### 查找对应php版本的phpize find / -name phpi…...
imx6ull开发板设置SD卡启动,SD卡中烧写uboot,kernel,设备树,根文件系统fs
IMX6ULL ARM Linux开发板SD卡启动,SD卡的分区与分区格式化创建_sd制作分区-CSDN博客...

2024年第七届可再生能源与环境工程国际会议(REEE 2024)即将召开!
2024年第七届可再生能源与环境工程国际会议(REEE 2024)将于2024 年8月28-30日在法国南特举行。共绘绿色未来,全球同频共振!REEE 2024将汇聚全球可再生能源与环境工程领域的专家学者和业界精英,共同探讨行业发展的前沿技…...

【华为】NAT的分类和实验配置
【华为】NAT的分类和实验配置 NAT产生的技术背景IP地址分类NAT技术原理NAT分类静态NAT动态NATNAPTEasy IP(PAT)NAT Server 配置拓扑静态NAT测试抓包 动态NAT测试抓包 NAPT测试抓包 PAT测试抓包 NAT Server检测抓包 PC1PC2服务器 NAT产生的技术背景 随着…...

拉普拉斯丨独家冠名2024年度ATPV技术分论坛,助力产业科技持续创新
为了进一步促进行业技术交流,推进光伏行业发展及标准建设的进程,针对高效电池,领跑组件,新产品认证及应用等技术专题及国内外光伏标准的最新进程,由中国绿色供应链联盟光伏专委会(ECOPV)指导的2…...
LangChain入门教程 - 使用代理Agent
对于大模型,比如某些场景,需要数学计算,或者需要从某些网站获取参考资料,就必须使用专门的代理来完成任务。这里我们使用langchain提供的数学工具来实现一个最简单的例子,下一篇我们会讲如何自己实现代理。 首先创建一…...
windows驱动开发-内核编程技术汇总(五)
使用安全字符串函数 和应用层不一样的是,windows内核完全使用Unicode字符串,许多支持AsciiC的windowsAPI,是在应用层完成项Unicode的切换的。许多系统安全问题是由缓冲区处理不善和生成的缓冲区溢出引起的。 糟糕的缓冲区处理通常与字符串操…...
Java中的optional类是啥和例子
Optional 是 Java 8 引入的一个容器对象,用于表示值存在或不存在。这是一个可以为 null 的容器对象,但使用 Optional 比直接使用 null 更安全,因为 Optional 类提供了许多有用的方法,以便更优雅地处理可能存在或不存在的值。 使用…...

AI大模型探索之路-训练篇16:大语言模型预训练-微调技术之LoRA
系列篇章💥 AI大模型探索之路-训练篇1:大语言模型微调基础认知 AI大模型探索之路-训练篇2:大语言模型预训练基础认知 AI大模型探索之路-训练篇3:大语言模型全景解读 AI大模型探索之路-训练篇4:大语言模型训练数据集概…...
mysql事务锁排查
-- mysql show full PROCESSLIST; -- 查看哪些表在锁。 show open tables where IN_use>0; -- 正在执行的事务: SELECT * FROM information_schema.INNODB_TRX;-- 8.0之前 查看正在锁的事务 select * from information_schema.innodb_locks;-- 查看等待锁的事务 …...

ChatGPT变懒原因:正在给自己放寒假!已被网友测出
ChatGPT近期偷懒严重,有了一种听起来很离谱的解释: 模仿人类,自己给自己放寒假了~ 有测试为证,网友Rob Lynch用GPT-4 turbo API设置了两个系统提示: 一个告诉它现在是5月,另一个告诉它现在是1…...

C#标签设计打印软件开发
1、新建自定义C#控件项目Custom using System; using System.Collections.Generic; using System.Text;namespace CustomControls {public class CommonSettings{/// <summary>/// 把像素换算成毫米/// </summary>/// <param name="Pixel">多少像素…...

Springboot+vue+小程序+基于微信小程序的在线学习平台
一、项目介绍 基于Spring BootVue小程序的在线学习平台从实际情况出发,结合当前年轻人的学习环境喜好来开发。基于Spring BootVue小程序的在线学习平台在语言上使用Java语言进行开发,在数据库存储方面使用的MySQL数据库,开发工具是IDEA。…...

正点原子[第二期]Linux之ARM(MX6U)裸机篇学习笔记-13-按键实验
前言: 本文是根据哔哩哔哩网站上“正点原子[第二期]Linux之ARM(MX6U)裸机篇”视频的学习笔记,在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。…...

ubuntu与redhat的不同之处
华子目录 什么是ubuntu概述 ubuntu版本简介桌面版服务器版 安装部署部署后的设置设置root密码关闭防火墙启用允许root进行ssh登录更改apt源安装所需软件 安装nginx安装apache网络配置Netplan概述配置详解配置文件DHCP静态IP设置设置 软件安装方法apt安装软件作用常用命令配置ap…...

三岁孩童被家养大型犬咬伤 额部撕脱伤达10公分
近期,一名被家养大型犬咬伤了面部的3岁小朋友,在被家人紧急送来西安国际医学中心医院,通过24小时急诊门诊简单救治后,转至整形外科,由主治医师李世龙为他实施了清创及缝合手术。 “患者额部撕脱伤面积约为10公分&…...
@click=“handleClick()“不会传递默认事件参数
当你使用click"handleClick()"这种形式绑定事件处理器时,Vue会将它视为一个函数调用,而不是一个事件监听器。在这种情况下,Vue不会自动传递原生事件对象作为默认参数。 如果你想让Vue自动传递原生事件对象作为默认参数,…...
KVM安装Ubuntu24.04简要坑点以及优点
本机环境是ubuntu22.04的环境,然后是8核16线程 ssd是500的 目前对于虚拟机的选择,感觉kvm确实会更加流畅,最重要的一点是简洁,然后实际安装效果也比较的好,如果对于速度方面希望快一点,并且流畅一点的话这…...

QT_day1
#include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {//修改窗口标题this->setWindowTitle("4.6.0");//修改窗口图标this->setWindowIcon(QIcon("C:\\Users\\zj\\Desktop\\yuanshen\\icon"));//修改窗口大小this…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...

Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...

sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...

【若依】框架项目部署笔记
参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作: 压缩包下载:http://download.redis.io/releases 1. 上传压缩包,并进入压缩包所在目录,解压到目标…...

dvwa11——XSS(Reflected)
LOW 分析源码:无过滤 和上一关一样,这一关在输入框内输入,成功回显 <script>alert(relee);</script> MEDIUM 分析源码,是把<script>替换成了空格,但没有禁用大写 改大写即可,注意函数…...