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

embedded/2024/9/23 20:13:29/

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

 


http://www.ppmy.cn/embedded/37650.html

相关文章

探索（淘宝京东1688）电商API接口：新一代电商问题解决方案

探索（淘宝京东1688）电商API接口：新一代电商问题解决方案

前言 随着电子商务的蓬勃发展&#xff0c;电商平台的API接口成为了连接商家、开发者与电商平台的桥梁。淘宝、京东、1688等主流电商平台提供的API接口&#xff0c;不仅极大地丰富了电商服务的多样性&#xff0c;也为解决传统电商问题提供了新的解决方案。本文将深入探讨这些电商…
阅读更多...
基于SSM的农产品销售管理系统

基于SSM的农产品销售管理系统

文章目录 项目介绍一、项目功能介绍二、部分页面展示三、部分源码四、底部获取全部源码&#xff08;9.9&#xffe5;带走&#xff09; 项目介绍 农产品销售管理系统 一、项目功能介绍 一、介绍 系统分为两个角色 用户功能&#xff1a;登陆&#xff0c;注册&#xff0c;商品分…
阅读更多...
IoTDB 入门教程 基础篇⑥——数据库SQL操作 | 数据库管理和数据读写

IoTDB 入门教程 基础篇⑥——数据库SQL操作 | 数据库管理和数据读写

文章目录 一、前文二、数据库管理2.1 创建数据库2.2 查询数据库2.3 删除数据库 三、数据读写3.1 查询数据3.2 新增数据3.3 修改数据3.4 删除数据 四、参考 一、前文 IoTDB入门教程——导读 本博文主要讲述数据库管理和数据读写 二、数据库管理 2.1 创建数据库 CREATE DATABASE…
阅读更多...
Rust：用 Warp 库实现 Restful API 的简单示例

Rust：用 Warp 库实现 Restful API 的简单示例

直接上代码&#xff1a; 1、源文件 Cargo.toml [package] name "xcalc" version "0.1.0" edition "2021"# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html[dependencies] warp "…
阅读更多...
Linux守护进程

Linux守护进程

进程组和会话在 UNIX 系统中是非常重要的概念&#xff0c;特别是在进行作业控制和终端会话管理时。下面是关于进程组和会话的详细解释&#xff1a; 进程组&#xff08;Process Group&#xff09; 定义与作用&#xff1a; 进程组是一个或多个进程的集合&#xff0c;这些进程通常…
阅读更多...
042.最近的请求次数

042.最近的请求次数

刷算法题&#xff1a; 第一遍&#xff1a;1.看5分钟&#xff0c;没思路看题解 2.通过题解改进自己的解法&#xff0c;并且要写每行的注释以及自己的思路。 3.思考自己做到了题解的哪一步&#xff0c;下次怎么才能做对(总结方法) 4.整理到自己的自媒体平台。 5.再刷重复的类…
阅读更多...
前后端分离项目中的一些疑惑

前后端分离项目中的一些疑惑

1、前后端分离项目&#xff0c;浏览器发起请求后&#xff0c;请求的是前端服务器还是后端服务器&#xff1f; 在前后端分离的项目中&#xff0c;当浏览器发起请求时&#xff0c;它首先会请求的是前端服务器。 前后端分离的工作流程大致如下&#xff1a; 用户在浏览器中输入网…
阅读更多...
windows10打印机共享完美解决方案

windows10打印机共享完美解决方案

提到文件共享大家并不陌生，相关的还有打印机共享，这个多见于单位、复印部，在一个区域网里多台电脑共用一台打印机，打印资料非常方便，就包括在家里，我们现在一般都会有多台电脑或设备，通过家庭网络联接，如果共享一台打印机的话也是件便捷的事。 但是随着操作系统的更新…
阅读更多...
最新文章

Copyright @ 2022~2023