【C++】用红黑树模拟实现set、map

目录

  • 前言及准备:
  • 一、红黑树接口
    • 1.1 begin
    • 1.2 end
    • 1.3 查找
    • 1.4 插入
    • 1.5 左单旋和右单旋
  • 二、树形迭代器(正向)
    • 2.1 前置++
  • 三、模拟实现set
  • 四、模拟实现map

前言及准备:

set、map的底层结构是红黑树,它们的函数通过调用红黑树的接口来实现,红黑树一些接口需要通过树形迭代器来实现。set是k模型,map是kv模型,红黑树要不要写两份呢?答案是不需要,只用一份即可,通过仿函数来控制。

定义树的节点:

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){}
};

红黑树有3个指针域,数据域用T来表示,如果是set,那么传过来的是k模型;如果是map,是kv模型。新增的节点的颜色默认是红色(根节点除外)。

一、红黑树接口

1.1 begin

返回的是红黑树的第一个节点,注意,这里的第一个的顺序是按中序遍历来的,所以,第一个节点的位置是树的最左节点。

//返回的迭代器指向的数据可修改
iterator begin()
{Node* subLeft = _root;while (subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);
}
//返回的迭代器指向的数据不可修改
const_iterator begin() const
{Node* subLeft = _root;while (subLeft->_left){subLeft = subLeft->_left;}return const_iterator(subLeft);
}

1.2 end

返回的是最后一个节点(最右侧节点)的下一个位置。由于这里实现的红黑树没有头节点,所以只能给nullptr来勉强实现这个迭代器。但是这样其实是不行的,因为对end()位置的迭代器进行 - - 操作,必须要能找最后一个元素,给nullptr就找不到了。如果有头节点,那么end()的位置应该是在头节点的位置。
在这里插入图片描述

iterator end()
{return iterator(nullptr);
}
const_iterator end() const
{return const_iterator(nullptr);
}

1.3 查找

查找的过程与之前写的二叉搜索树没有多大区别,要注意的是返回类型,找到了,返回的是该节点的迭代器,找不到就返回end()。

iterator Find(const K& key)
{KeyOfT kot;Node* cur = _root;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();
}

咋知道是set还是map的数据进行比较,看传过来的类模板参数中的仿函数是set的还是map的。当然,这里只需写好就行,不用关心传过来的是什么,set和map的仿函数内部已经确定好了。

说明一下:

template<class K, class T, class KeyOfT>

这是该红黑树的类模板,K是Find()函数中要对比的数据类型,T是节点的数据域,可能是k模型,也有可能是kv模型。怎么确定呢?通过第三个类模板参数——仿函数来确定。仿函数传的是set的,就是k模型;仿函数传的是map的,就是kv模型。仿函数内部具体实现下面再说。

1.4 插入

为了接近STL库中的insert函数,返回类型是pair,即插入成功,返回该节点的迭代器和true;插入失败,说明该节点已经存在,返回该节点的迭代器和false。

pair<iterator, bool> Insert(const T& data)
{//为空if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根节点都是黑色的,特殊处理return make_pair(iterator(_root), true);}//非空KeyOfT kot;Node* cur = _root;Node* parent = nullptr;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(iterator(cur), false);}}//插入新节点cur = new Node(data);//红色的if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;Node* newnode = cur;//调整颜色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//爷爷节点//父节点在爷爷节点的左边,那么叔叔节点在右边if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况一:叔叔存在且为红if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle->_col = parent->_col = BLACK;cur = grandfather;//爷爷不是根,向上更新parent = cur->_parent;}//情况二:叔叔不存在/存在且为黑else{//单旋if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;//变色grandfather->_col = RED;}//左右双旋 // cur == parent->_rightelse{RotateL(parent);//先左单旋RotateR(grandfather);//再右单旋grandfather->_col = RED;//变色cur->_col = BLACK;}}}else//父节点在右边,叔叔在左边{Node* uncle = grandfather->_left;//情况一:叔叔存在且为红if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle->_col = parent->_col = BLACK;cur = grandfather;//爷爷不是根,向上更新parent = cur->_parent;}//情况二:叔叔不存在/存在且为黑else{//单旋if (cur == parent->_right){RotateL(grandfather);//左单旋parent->_col = BLACK;//变色grandfather->_col = RED;}//右左双旋 // cur == parent->_leftelse{RotateR(parent);//先右单旋RotateL(grandfather);//再左单旋grandfather->_col = RED;//变色cur->_col = BLACK;}break;//经过情况二后跳出}}}_root->_col = BLACK;//统一处理,根必须是黑的return make_pair(iterator(newnode), true);
}

1.5 左单旋和右单旋

这两个就是之前的,这里不作重复叙述了

//左单旋
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;//处理parent如果为根if (parent == _root){_root = subR;subR->_parent = nullptr;}//不为根,处理与ppnode的连接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;}
}

二、树形迭代器(正向)

2.1 前置++

首先要清楚的是++到下一个节点位置是按中序遍历走的,主要有两种情况:

  1. 该节点有右子树
  2. 该节点没有右子树

1️⃣有右子树
在这里插入图片描述
总结:有右子树++后的下一个节点是右子树的最左节点

2️⃣没有右子树
在这里插入图片描述
总结:没有右子树++后下一个节点是祖先节点中左孩子是当前节点(原来节点的位置)或者左孩子是当前节点的父亲的那个祖先

有点弯,再来图捋一捋:
在这里插入图片描述

前置- -的逻辑与前置++刚好相反

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr 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;//cur是parent的左子树,parent就是下一个while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}//前置--Self& operator--()//与前置++的逻辑相反{//左子树存在if (_node->_left){//下一个节点是左子树的最右一个Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}//左子树不存在else{Node* cur = _node;Node* parent = cur->_parent;//cur是parent的右子树时parent就是下一个while (parent && parent->_left == cur){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;}
};

三、模拟实现set

set是k模型,仿函数返回的只有key值。其他接口调用红黑树的

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;typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;//迭代器iterator begin(){return _t.begin();}const_iterator begin() const{return _t.begin();}iterator end(){return _t.end();}const_iterator end() const{return _t.end();}//插入pair<iterator, bool> Insert(const K& key){return _t.Insert(key);}//查找iterator Find(const K& key){_t.Find(key);}
private:RBTree<K, const K, SetKeyOfT> _t;
};

四、模拟实现map

map是kv模型,仿函数返回的取kv中的key值。其他接口调用红黑树的,除此之外,多了一个operator[]

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;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;//迭代器iterator begin(){return _t.begin();}const_iterator begin() const{return _t.begin();}iterator end(){return _t.end();}const_iterator end() const{return _t.end();}//插入pair<iterator, bool> Insert(const pair<K, V>& kv){return _t.Insert(kv);}//查找iterator Find(const K& key){_t.Find(key);}//operator[]V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key, V()));return ret.first->second;}
private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

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

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

相关文章

微信小程序小白易入门基础教程1

微信小程序 基本结构 页面配置 页面配置 app.json 中的部分配置&#xff0c;也支持对单个页面进行配置&#xff0c;可以在页面对应的 .json 文件来对本页面的表现进行配置。 页面中配置项在当前页面会覆盖 app.json 中相同的配置项&#xff08;样式相关的配置项属于 app.js…

android 怎么自定义view

首先了解view的绘制流程: 所以onmeasure ---测量view onlayout---确定view大小----》所以继承ViewGroup必须要重写onlayout,确定子view 而onDraw----是继承view时候需要操作的。 所以:自定义ViewGroup一般是利用现有的组件根据特定的布局方式来组成新的组件。 自定义Vi…

一个可商用私有化部署的基于JAVA的chat-gpt网站

目录 介绍一、核心功能1、智能对话2、AI绘画3、知识库4、一键思维导图5、应用广场6、GPTS 二、后台管理功能1、网站自定义2、多账号登录支持3、商品及会员系统4、模型配置5、兑换码生成6、三方商户用户打通 结语 介绍 java语言的私有化部署的商用网站还是比较少的 这里给大家介…

第 126 场 LeetCode 双周赛题解

A 求出加密整数的和 模拟 class Solution { public:int sumOfEncryptedInt(vector<int> &nums) {int res 0;for (auto x: nums) {string s to_string(x);char ch *max_element(s.begin(), s.end());for (auto &c: s)c ch;res stoi(s);}return res;} };B 执行…

【研发日记】Matlab/Simulink技能解锁(五)——Simulink布线技巧

前言 见《【研发日记】Matlab/Simulink技能解锁(一)——在Simulink编辑窗口Debug》 见《【研发日记】Matlab/Simulink技能解锁(二)——在Function编辑窗口Debug》 见《【研发日记】Matlab/Simulink技能解锁(三)——在Stateflow编辑窗口Debug》 见《【研发日记】Matlab/Simulink…

C++作业day6

编程1&#xff1a; 封装一个动物的基类&#xff0c;类中有私有成员&#xff1a;姓名&#xff0c;颜色&#xff0c;指针成员年纪 再封装一个狗这样类&#xff0c;共有继承于动物类&#xff0c;自己拓展的私有成员有&#xff1a;指针成员&#xff1a;腿的个数&#xff08;整型 …

六种GPU虚拟化:除了直通、全虚拟化 (vGPU)还有谁?

在大类上计算虚拟化技术有这3种&#xff1a; 软件模拟、直通独占(如网卡独占、显卡独占)、直通共享&#xff08;如vCPU 、vGPU&#xff09;。但对于显卡GPU而言我总结细化出至少这6种分类&#xff1a; 第一种、软件模拟&#xff08;eg sGPU&#xff09;, 又叫半虚拟化。第二种…

[论文笔记] Gradient Surgery for Multi-Task Learning

【强化学习 137】PCGrad - 知乎 多任务学习(multi task):任务权重、loss均衡、梯度下降那点事 - 知乎 ICLR 2020 rejected submission:Yu T, Kumar S, Gupta A, et al. Gradient surgery for multi-task learning[J]. arXiv preprint arXiv:2001.06782, 2020. mul…

yocto编译测试

源码下载 git clone -b gatesgarth git://git.yoctoproject.org/poky lkmaolkmao-virtual-machine:~/yocto$ git clone -b gatesgarth git://git.yoctoproject.org/poky Cloning into poky... remote: Enumerating objects: 640690, done. remote: Counting objects: 100% (13…

Java的图书管理系统,确实有两把斧子 ! ! !

本篇会加入个人的所谓‘鱼式疯言’ ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人…

15届蓝桥杯备赛(2)

文章目录 刷题笔记(2)二分查找在排序数组中查找元素的第一个和最后一个位置寻找旋转排序数组中的最小值搜索旋转排序数组 链表反转链表反转链表II 二叉树相同的树对称二叉树平衡二叉树二叉树的右视图验证二叉搜索树二叉树的最近公共祖先二叉搜索树的最近公共祖先二叉树层序遍历…

Qt 图形视图 /基于Qt示例DiagramScene解读图形视图框架

文章目录 概述从帮助文档看示例程序了解程序背景/功能理清程序概要设计 分析图形视图的协同运作机制如何嵌入到普通Widget程序中&#xff1f;形状Item和文本Item的插入和删除&#xff1f;连接线Item与形状Item的如何关联&#xff1f;如何绘制ShapeItem间的箭头线&#xff1f; 下…

干货整理!火石控股创始人吴渔夫的 AI 游戏思维20条

近日&#xff0c;在一场面对面的直播中&#xff0c;自媒体「极新」创始人姜稳与火石控股创始人、奇酷网络董事长吴渔夫进行视频对话中&#xff0c;探讨了AI技术对游戏行业的新机遇和新挑战。 中国网游先锋&#xff0c;火石控股创始人&#xff0c;奇酷网络董事长吴渔夫认为&…

个人网站制作 Part 9 添加发布、管理博客功能 | Web开发项目

文章目录 &#x1f469;‍&#x1f4bb; 基础Web开发练手项目系列&#xff1a;个人网站制作&#x1f680; 添加博客功能&#x1f528;使用Express和MongoDB&#x1f527;步骤 1: 创建博客模型&#x1f527;步骤 2: 创建博客路由 &#x1f528;使用前端框架&#x1f527;步骤 3:…

大模型文本生成——解码策略(Top-k Top-p Temperature)

{"top_k": 10,"temperature": 0.95,"num_beams": 1,"top_p": 0.8,"repetition_penalty": 1.5,"max_tokens": 30000,"message": [{"content": "你好&#xff01;","role"…

电子招投标系统:企业在招标前,需要考虑哪些事项?

招标过程可能非常复杂和耗时&#xff0c;这使得一些企业放弃招标寻源方式。然而&#xff0c;要发展业务和客户群&#xff0c;就不能逃避招标。 在进行招标过程之前&#xff0c;首先要打好基础。让我们来看看企业在设计招标流程时应考虑哪些事项。 1. 确保有购买意向和能力 在…

Vue el-table 合并单元格

一般常见的就是下图这种的单列&#xff0c;上下重复进行合并。 有时候可能也会需要多行多列的合并。 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content&qu…

kkview远程控制: 内网远程桌面控制软件

内网远程桌面控制软件&#xff1a;高效、安全的远程管理方案 在信息技术日新月异的今天&#xff0c;内网远程桌面控制软件已成为许多企业和个人用户不可或缺的工具。这类软件允许用户通过内部网络&#xff0c;实现对其他计算机的远程访问和控制&#xff0c;从而大大提高工作效…

Docker 系列2【docker安装mysql】【开启远程连接】

文章目录 前言开始步骤1. 增加mysql挂载目录2.下载镜像3. 启动mysql容器4. 配置mysql5.无法连接5.测试连接 总结 前言 本文开始&#xff0c;默认已经安装docker&#xff0c;如果你还没有完成这个步骤&#xff0c;请查看这一篇文章【docker安装与使用】 开始步骤 1. 增加mysq…

<Linux> 生产者消费者模型

目录 前言&#xff1a; 一、什么是生产者消费者模型 &#xff08;一&#xff09;概念 &#xff08;二&#xff09;生产者消费者之间的关系 &#xff08;三&#xff09;生产者消费者模型特点 &#xff08;四&#xff09;生产者消费者模型的优点 二、基于阻塞队列实现生产…