【C++历练之路】红黑树——map与set的封装实现

2024-05-08 09:44
文章标签 c++ 实现 封装 set 红黑树 map 历练

本文主要是介绍【C++历练之路】红黑树——map与set的封装实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

W...Y的个人主页💕

gitee代码仓库分享😊 

 

前言：上篇博客中，我们为了使二叉搜索树不会出现”一边倒“的情况，使用了AVL树对搜索树进行了处理，从而解决了数据在有序或者接近有序时出现的情况。但是AVL树还会有一大缺陷就是其性能的原因，当我们在使其满足AVL树的规则时，其付出的旋转代价是非常大的，所以经常修改的结构就不适合AVL树。但是红黑树就可以补足AVL树的缺陷。

目录

1. 红黑树

1.1 红黑树的概念

1.2 红黑树的性质 

 1.3红黑树节点的定义

 1.4红黑树的插入

1.5 红黑树与AVL树的比较 

2. 红黑树模拟实现STL中的map与set

2.1 红黑树的迭代器

2.2 红黑树的改写与迭代器完整代码

2.3 map的封装

2.4 set的封装

1. 红黑树

1.1 红黑树的概念

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

假设最短路径为h，则最长路径为2h。 

1.2 红黑树的性质 

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

为什么满足上述性质，红黑树就可以保证其最长路径的节点树不会超过最短路径的两倍呢？  

 前两个性质非常通俗易懂，我们从第三个性质开始解读：

3.没有连续的两个红色节点。

4.每条路径的黑色节点数是相同的。

所以我们就可以假设一颗红黑树中每条路径有两个黑色节点(满足性质4)，那最短路径只可能是全黑节点，最长路径一定是一黑一红节点(假设最短路径与最长路径都存在),那么红色节点只能在黑色节点中间插入，这样才能满足性质3，所以红黑树就可以保证其最长路径的节点树不会超过最短路径的两倍。

对比AVL树与红黑树的结构，其AVL树的高度近似logN，而红黑树的高度近似2logN，所以相对于AVL树，红黑树的搜索效率差一些，但是几乎可以忽略不计，因为logN足够小，所以他们之间的搜索差距微乎其微。

 1.3红黑树节点的定义

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}
};

在节点定义时我们默认将节点设置成红色节点，这样如果出现连续的红色节点时，我们可以进行变色操作，通过维护一个子树来使红黑树合法，但是如果插入一个黑色节点时，我们就无法下手，因为每条路的黑色节点数必须相同，这样我们无法很好的进行操作使其合法化。 

 1.4红黑树的插入

 红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点：

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{return false;}}cur = new Node(kv); // 红色的if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;
}
private:Node* _root = nullptr;
};

2. 检测新节点插入后，红黑树的性质是否造到破坏:
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点 

 情况一: cur为红，p为红，g为黑，u存在且为红

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。 

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

 如果u存在且为黑， 则cur一定不是新增节点，因为这样就不满足性质4：每条路径黑色节点个数相同。所以我们将上面图补充完整就是下图所示，先是由情况一进行调整，然后向上调整后才得到上图。所以情况一向上调整后的情况不一定又是情况一！！

这时我们就无法用情况一的做法进行调整， 如果继续用情况一法则已经违反规则了。左右极度不均衡只能进行选择，这时我们就可以类比使用AVL树中的旋转法则。(旋转+变色)

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色--p变黑，g变红

在变色时我们不区分其p与u节点的左右，但是在旋转时我们就要进行区分。

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑 

 这种情况并不是一边高，而是两边都高左边高右边也高。所以我们得使用左右/右左双旋转。

p为g的左孩子，cur为p的右孩子，左右双旋+变色

p为g的右孩子，cur为p的左孩子，右左双旋+变色

针对每种情况进行相应的处理即可。

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{return false;}}cur = new Node(kv); // 红色的if (parent->_kv.first < kv.first){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){++rotateSize;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){++rotateSize;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;}

1.5 红黑树与AVL树的比较 

 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追
求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，
所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红
黑树更多。

2. 红黑树模拟实现STL中的map与set

我们模拟实现了红黑树，接下来就是对map与set的封装。

我们通过观察其stl源码切入进行仿写：

 我们发现无论是map还是set都复用的一个红黑树，模板参数都是k，v模型。通过源码我们可以发现：set<k> -> rb_tree<k,k> map<k,v> ->rb_tree<k,pair<const k,v>>。所以节点中存什么内容是由v决定的，不是k决定的。将红黑树写成泛型，所以我们必须将上面写的红黑树的模板进行修改！

进行封装后就可以解决复用红黑树的模板。 

 但是使用红黑树的模板时，set和map所比较的对象不一样，因为set比较的就是key，而map比较的是value，所以我们就得使用仿函数进行操作，我们创建keyoft仿函数取出T对象中的key即可。

//set
struct SetKeyOfT{const K& operator()(const K& key){return key;}};//map
struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};

2.1 红黑树的迭代器

首先我们得封装一个红黑树的迭代器用来实现++、--、*、->、!=。这里的迭代器与list的迭代器非常类似，可以用一个指针来实现其内容。但是++与--必须确定下一个与上一个节点的关系，这里我们可以使用中序遍历解决，但是得用一个栈来辅助，这里我们不想使用这样的方法，我们可以找规律来实现：

++逻辑

1.it指向节点，右不为空，下一个就是右子树的最左节点

2.it指向节点，右为空，意味着这个节点的子树中序访问完了，下一个节点找祖先里面的孩子==父亲左的那个祖先。

--逻辑与++相反！

这样迭代器就很好解决了：

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 operato == (const Self & s){return _node == s._node;}
};

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

begin()与end()
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，
可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位
置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最
后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置： 

typedef RBTreeIterator<T> iterator;iterator begin()
{Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);
}iterator end()
{return iterator(nullptr);
}
//map
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>& kv)
{return _t.Insert(kv);
}
//settypedef 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);
}

2.2 红黑树的改写与迭代器完整代码

#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 operato == (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;
};

2.3 map的封装

namespace why
{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>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}

2.4 set的封装

#include"RBTree.h"
namespace why
{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;};
}

 

这篇关于【C++历练之路】红黑树——map与set的封装实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/969989。

相关文章

Spring Retry 实现乐观锁重试实践记录

Spring Retry 实现乐观锁重试实践记录

《SpringRetry实现乐观锁重试实践记录》本文介绍了在秒杀商品SKU表中使用乐观锁和MybatisPlus配置乐观锁的方法,并分析了测试环境和生产环境的隔离级别对乐观锁的影响,通过简单验证,... 目录一、场景分析 二、简单验证 2.1、可重复读 2.2、读已提交 三、最佳实践 3.1、配置重试模板
阅读更多...
Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)

Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)

《Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)》文章介绍了如何使用dhtmlx-gantt组件来实现公司的甘特图需求,并提供了一个简单的Vue组件示例,文章还分享了一... 目录一、首先 npm 安装插件二、创建一个vue组件三、业务页面内 引用自定义组件：四、dhtmlx
阅读更多...
Vue ElementUI中Upload组件批量上传的实现代码

Vue ElementUI中Upload组件批量上传的实现代码

《VueElementUI中Upload组件批量上传的实现代码》ElementUI中Upload组件批量上传通过获取upload组件的DOM、文件、上传地址和数据,封装uploadFiles方法,使... ElementUI中Upload组件如何批量上传首先就是upload组件 <el-upl
阅读更多...
Docker部署Jenkins持续集成(CI)工具的实现

Docker部署Jenkins持续集成(CI)工具的实现

《Docker部署Jenkins持续集成(CI)工具的实现》Jenkins是一个流行的开源自动化工具,广泛应用于持续集成（CI）和持续交付（CD）的环境中,本文介绍了使用Docker部署Jenkins... 目录前言一、准备工作二、设置变量和目录结构三、配置 docker 权限和网络四、启动 Jenkins
阅读更多...
Python3脚本实现Excel与TXT的智能转换

Python3脚本实现Excel与TXT的智能转换

《Python3脚本实现Excel与TXT的智能转换》在数据处理的日常工作中,我们经常需要将Excel中的结构化数据转换为其他格式,本文将使用Python3实现Excel与TXT的智能转换,需要的可以... 目录场景应用：为什么需要这种转换技术解析：代码实现详解核心代码展示改进点说明实战演练：从Excel到
阅读更多...
如何使用CSS3实现波浪式图片墙

如何使用CSS3实现波浪式图片墙

《如何使用CSS3实现波浪式图片墙》：本文主要介绍了如何使用CSS3的transform属性和动画技巧实现波浪式图片墙，通过设置图片的垂直偏移量，并使用动画使其周期性地改变位置，可以创建出动态且具有波浪效果的图片墙，同时，还强调了响应式设计的重要性，以确保图片墙在不同设备上都能良好显示，详细内容请阅读本文，希望能对你有所帮助...
阅读更多...
C# string转unicode字符的实现

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码：输出：2. 将 Unicode 值格式化
阅读更多...
python安装whl包并解决依赖关系的实现

python安装whl包并解决依赖关系的实现

《python安装whl包并解决依赖关系的实现》本文主要介绍了python安装whl包并解决依赖关系的实现,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录一、什么是whl文件？二、我们为什么需要使用whl文件来安装python库？三、我们应该去哪儿下
阅读更多...
Python脚本实现图片文件批量命名

Python脚本实现图片文件批量命名

《Python脚本实现图片文件批量命名》这篇文章主要为大家详细介绍了一个用python第三方库pillow写的批量处理图片命名的脚本,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录前言源码批量处理图片尺寸脚本源码GUI界面源码打包成.exe可执行文件前言本文介绍一个用python第三方库pi
阅读更多...
Java中将异步调用转为同步的五种实现方法

Java中将异步调用转为同步的五种实现方法

《Java中将异步调用转为同步的五种实现方法》本文介绍了将异步调用转为同步阻塞模式的五种方法：wait/notify、ReentrantLock+Condition、Future、CountDownL... 目录异步与同步的核心区别方法一：使用wait/notify + synchronized代码示例关键
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2