当前位置： 首页 > news >正文

【C++红黑树应用】模拟实现STL中的map与set

news 来源：原创 2024/9/20 0:13:44

目录

  • 🚀 前言
  • 一： 🔥 红黑树的修改
  • 二： 🔥 红黑树的迭代器
  • 三： 🔥 perator++() 与 operator--()
  • 四： 🔥 红黑树相关接口的改造
    • ✨ 4.1 Find 函数的改造
    • ✨ 4.2 Insert 函数的改造
  • 五：🔥 Set 和 map的模拟实现
    • ✨ 5.1 Set的基本设计
    • ✨ 5.2 Map的基本设计
  • 六：📖 红黑树改造的完整代码及总结

🚀 前言

红黑树类的实现参考上一篇文章：【C++高阶数据结构】红黑树：全面剖析与深度学习
之前我们已经学习了如何手搓一棵红黑树，现在让我们来对红黑树进行改造，并且封装成map和set.

我们通过观察其stl源码切入进行仿写：
在这里插入图片描述
我们发现无论是map还是set都复用的一个红黑树，模板参数都是k，v模型。通过源码我们可以发现：set -> rb_tree<k, k> | | map<k, v> -> rb_tree<k, pair<const k, v>>。所以节点中存什么内容是由v决定的，不是k决定的。将红黑树写成泛型，所以我们必须将之前写的红黑树的模板进行修改！

一： 🔥 红黑树的修改

【改造前】


template<class K, class T>
class RBTree
{typedef RBTreeNode<T> Node; // 红黑树节点
public:RBTree() :_root(nullptr) {}  // 构造函数bool Insert(const T& data);  // 插入节点// ...
private:Node* _root;
};

红黑树的插入节点接口中要先通过比较节点中数据的大小来查找适合插入的位置，但是红黑树并不知道数据 data 到底是 key 还是 pair。如果数据 data 是 key，那么直接取 key 来作比较；如果数据 data 是 pair，则需要取 first 来作比较。

  • 所以我们就得使用仿函数进行操作，我们创建keyoft仿函数取出T对象中的key即可。

在这里插入图片描述
【改造后】

红黑树的定义

  • K：键值key的类型。
  • T：数据的类型，如果是 map，则为 pair<const K, V>；如果是 set，则为 K。
  • KeyOfT：通过 T 的类型来获取 key 值的一个仿函数类。
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node; // 红黑树节点
public:RBTree() :_root(nullptr) {}  // 构造函数bool Insert(const T& data);  // 插入节点（接口返回值目前是bool，后续要改为pair）// ...
private:Node* _root;
};

二： 🔥 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代
器，需要考虑以前问题：begin()与end()

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，
可以得到一个有序的序列。

SGI-STL源码中，红黑树有一个哨兵位的头节点，begin() 是放在红黑树中最小节点(即最左侧节点)的位置，end() 是放在 end() 放在头结点的位置。

本文所采取的方式并没有使用头节点，而是通过其他方法实现，使用空指针代表end（）


template<class K, class T, class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node; // 红黑树节点
public:typedef _RBTreeIterator<T, T&, T*> iterator; // 迭代器iterator begin() // begin(): 指向红黑树的最左节点的迭代器{Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);// 注意：单参数的构造函数支持隐式类型转换，节点会被构造成迭代器// 所以也可以这样写：return left;}iterator end() // end(): 指向nullptr的迭代器{return iterator(nullptr);}
private:Node* _root = nullptr;
};

三： 🔥 perator++() 与 operator–()

  1. operator++()
  • 右不为空，右子树的最左节点
  • 右为空，沿着到根的路径找孩子是父亲左的那个祖先
  1. operator–()
  • 左不为空，左子树的最右节点
  • 左为空，沿着到根的路径找孩子是父亲右的那个祖先

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Self& operator++(){if (_node->_right){// 右不为空，右子树最左节点就是中序下一个Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr)            // end()情况特殊处理{// end()--  走到最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 右不为空，右子树最左节点就是中序下一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}
};
}

四： 🔥 红黑树相关接口的改造

✨ 4.1 Find 函数的改造

查找成功，返回查找到的那个节点的迭代器，查找失败，就返回 nullptr。

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, _root);}}return End();
}

✨ 4.2 Insert 函数的改造

注意：map 里的 operator[] 需要依赖 Insert 的返回值

pair<Iterator, bool> Insert(const T& data)
{if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root, _root), true);}KeyOfT kot;        // 仿函数// 找到插入位置Node* cur = _root, * 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, _root), false);}}cur = new Node(data);Node* newnode = cur;//	新增节点 颜色优先选择红色cur->_col = RED;if (kot(data) > kot(parent->_data)) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 1、parent不存在，cur就是根了，出去后把根处理成黑的// 2、parent存在，且为黑// 3、parent存在，且为红，继续循环处理// 变色了之后持续网上处理while (parent && parent->_col == RED)          // 父亲颜色是红色就需要继续处理（来连续的红节点， 关键看叔叔）{Node* grandfather = parent->_parent;if (parent == grandfather->_left)               // 父亲在爷爷的左边 右边就是对称的{Node* uncle = grandfather->_right;//    g//  p   uif (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  p   u// c// 单旋if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  p   u//    c// 双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}else {//    g//  u   pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  u   p//        c// 单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  u   p//    c// 双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}}_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);
}

五：🔥 Set 和 map的模拟实现

✨ 5.1 Set的基本设计

set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。

为了解决 set 中 key 值不能修改的问题，在传给 RBTree 的第二个模板参数前加 const 即可。

#pragma once#include"RBTree.h"namespace bit
{template<class K>class set{   // 取出 keyofvalue 的仿函数类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>::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};void Print(const set<int>& s){set<int>::const_iterator it = s.end();while (it != s.begin()){--it;//*it += 2;cout << *it << " ";}cout << endl;}void test_set(){bit::set<int> s;int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}for (auto e : s){cout << e << ' ';}set<int>::iterator it = s.end();while (it != s.begin()){--it;cout << *it << " ";}cout << '\n';}
}

✨ 5.2 Map的基本设计

#pragma once#include"RBTree.h"namespace bit
{template<class K, class V>class map{// 取出 keyofvalue 的仿函数类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>::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}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){return _t.Find(key);}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;};void test_map(){map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边，剩余";dict["insert"] = "插入";dict["string"];map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;}}

六：📖 红黑树改造的完整代码及总结

#pragma once#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#include <assert.h>using namespace std;enum Color
{RED,BLACK
};template<class T>
struct RBTreeNode {T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;		Color _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Self& operator++(){if (_node->_right){// 右不为空，右子树最左节点就是中序下一个Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr)            // end()情况特殊处理{// end()--  走到最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 右不为空，右子树最左节点就是中序下一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!= (const Self& s){return _node != s._node;}
};// T可以是key 也可以是map 三个参数中第一个key是给find和 erase的   pair和第二个key是给insert的
template<class K, class T, class KeyOfT>
class RBTree {typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return Iterator(leftMost, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return ConstIterator(leftMost, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}RBTree() = default;RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}pair<Iterator, bool> Insert(const T& data){if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root, _root), true);}KeyOfT kot;        // 仿函数// 找到插入位置Node* cur = _root, * 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, _root), false);}}cur = new Node(data);Node* newnode = cur;//	新增节点 颜色优先选择红色cur->_col = RED;if (kot(data) > kot(parent->_data)) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 1、parent不存在，cur就是根了，出去后把根处理成黑的// 2、parent存在，且为黑// 3、parent存在，且为红，继续循环处理// 变色了之后持续网上处理while (parent && parent->_col == RED)          // 父亲颜色是红色就需要继续处理（来连续的红节点， 关键看叔叔）{Node* grandfather = parent->_parent;if (parent == grandfather->_left)               // 父亲在爷爷的左边 右边就是对称的{Node* uncle = grandfather->_right;//    g//  p   uif (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  p   u// c// 单旋if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  p   u//    c// 双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}else {//    g//  u   pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  u   p//        c// 单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  u   p//    c// 双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}}_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);}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, _root);}}return End();}Node* Copy(Node * root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_kv);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destroy(Node * root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void InOrder(){_InOrder(_root);}int Height(){return _Height(_root);}// 检查是否是红黑树bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED){return false;}// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}private:bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << '\n';return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}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;}void RotateL(Node * parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;Node* parent_parent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent_parent == nullptr){_root = subR;subR->_parent = nullptr;}else {if (parent == parent_parent->_left) parent_parent->_left = subR;else parent_parent->_right = subR;subR->_parent = parent_parent;}}void RotateR(Node * parent){Node* subL = parent->_left;Node* subLR = parent->_left->_right;parent->_left = subLR;if (subLR) subLR->_parent = parent;Node* parent_parent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent_parent == nullptr){_root = subL;subL->_parent = nullptr;}else {if (parent == parent_parent->_left){parent_parent->_left = subL;}else {parent_parent->_right = subL;}subL->_parent = parent_parent;}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << '\n';_InOrder(root->_right);}Node* _root = nullptr;};//void TestRBTree1()
//{
//	RBTree<int, int> t;
//	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//	// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//	for (auto e : a)
//	{
//
//		t.Insert({ e, e });
//	}
//
//	t.InOrder();
//	cout << t.IsBalance() << endl;
//}

以上就是红黑树的改造及封装map和set全部内容，需要我们好好掌握，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~😉
在这里插入图片描述

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 基于多种机器学习算法的短信垃圾分类模型
  • 机器学习第四章-决策树
  • 10个计算机二级考试的试题及其答案
  • 常见的jmeter面试题及答案
  • 解决win10蓝屏“选择一个选项”的问题!
  • 学习笔记之Java篇（0729）
  • 设计模式实战：订单处理系统的设计与实现
  • 使用java自带的队列进行存取数据ArrayBlockingQueue 多线程读取ExecutorService
  • 数学基础 -- 隐函数与隐函数求导
  • VUE 基础(二)
  • Selenium clear无效解决办法
  • 基于PaddleClas的人物年龄分类项目
  • 【SuperMap iServer 服务列表未授权访问漏洞】怎么处理
  • 【扒代码】X = output[:,:,y1:y2,x1:x2].sum()
  • Linux：core文件无法生成排查步骤
  • 2017-09-12 前端日报
  • canvas 高仿 Apple Watch 表盘
  • canvas实际项目操作，包含：线条，圆形，扇形，图片绘制，图片圆角遮罩，矩形，弧形文字...
  • Cookie 在前端中的实践
  • JavaScript 是如何工作的:WebRTC 和对等网络的机制！
  • Laravel 中的一个后期静态绑定
  • miaov-React 最佳入门
  • npx命令介绍
  • pdf文件如何在线转换为jpg图片
  • QQ浏览器x5内核的兼容性问题
  • Vue全家桶实现一个Web App
  • Webpack入门之遇到的那些坑，系列示例Demo
  • 动态魔术使用DBMS_SQL
  • 基于Volley网络库实现加载多种网络图片（包括GIF动态图片、圆形图片、普通图片）...
  • 判断客户端类型，Android，iOS，PC
  • 前端知识点整理（待续）
  • 如何使用 JavaScript 解析 URL
  • 使用 Docker 部署 Spring Boot项目
  • 数组大概知多少
  • 算法-插入排序
  • 小程序开发中的那些坑
  • 一、python与pycharm的安装
  • 用 vue 组件自定义 v-model， 实现一个 Tab 组件。
  • 哈罗单车融资几十亿元，蚂蚁金服与春华资本加持 ...
  • ​iOS实时查看App运行日志
  • #define 用法
  • （1）Nginx简介和安装教程
  • （3）llvm ir转换过程
  • (c语言版)滑动窗口 给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度
  • （HAL）STM32F103C6T8——软件模拟I2C驱动0.96寸OLED屏幕
  • （STM32笔记）九、RCC时钟树与时钟 第一部分
  • （附源码）spring boot基于小程序酒店疫情系统 毕业设计 091931
  • （附源码）springboot猪场管理系统 毕业设计 160901
  • (过滤器)Filter和(监听器)listener
  • (文章复现)基于主从博弈的售电商多元零售套餐设计与多级市场购电策略
  • （转）大道至简，职场上做人做事做管理
  • .NET Core 网络数据采集 -- 使用AngleSharp做html解析
  • .NET Core 项目指定SDK版本
  • .NET DevOps 接入指南 | 1. GitLab 安装
  • .NET MAUI Sqlite程序应用-数据库配置（一）