【C++】红黑树的应用（封装map和set）
island1314 2024-08-21 14:05:02 阅读 53
✨ 青山一道同云雨，明月何曾是两乡 🌏
📃个人主页：island1314
🔥个人专栏：C++学习
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞
红黑树的应用
🚀 前言
1. 红黑树的改造
🌈1.1. 红黑树节点的改造
🌈1.2 红黑树的主体框架
2. 红黑树的迭代器
🎈2.1 迭代器基本设计
🎈2.2 begin()与end()
🎈2.3 operator++()与operator–()
3. 红黑树相关接口的改造
✨3.1 Find 函数的改造
✨3.2 Insert 函数的改造
4. Set 和 map的模拟实现
🧩4.1 Set的基本设计
🧩4.2 Map的基本设计
📖5. 红黑树改造的完整代码及总结
🚀 前言
红黑树类的实现参考上一篇文章：【C++】红黑树的全面探索和深度解析-CSDN博客
之前我们已经学习了如何手搓一棵红黑树，现在让我们来对红黑树进行改造，并且封装成map和set.
map 和 set 的底层本质上还是复用，通过对红黑树的改造，再分别套上一层 map 和 set 的 “壳子”，以达到 “一树二用” 的目的。
在改造红黑树的过程中，我们应该就解决以下几个需要重点解决的问题：
📒(1) 对红黑树节点的改造。关联式容器中存储的是<key, value>的键值对，K为key的类型，如果是 set 则是 K，如果是map，则为pair<K, V>。如何用一个节点结构控制两种类 型，使用类模板参数T。
📜(2) 在插入操作时，如何完成数据的比较。由于我们的节点类型的泛型，如果是 set 则是 K，如果是map，则为pair<K, V>，而pair的比较是由 first 和 second 共同决定的，这显然不符合要求。因此插入数据时不能直接比较，要在 set 和 map 类中实现一个 KeyOfT 的仿函数，以便单独获取两个类型中的 key 数据。
📙(3) 在红黑树中实现普通迭代器和const迭代器，再套上 “壳子”。
📝(4) 关于 key 的修改问题。在STL库中，set 和 map 的 key 都是不能修改的，因为要符合二叉搜索树的特性，但是 map 中的 value 又是可以修改的。这个问题需要单独处理。
📚(5) 红黑树相关接口的改造。其中包括对 Find 和 Insert 函数的改造，特别是 Insert，因为在 map 里实现 operator[] 时需要依赖 Insert 函数。
1. 红黑树的改造
📒改造红黑树以适配map和set容器，主要涉及到如何根据这两种容器的特性来设计和实现红黑树节点的存储以及相应的操作。map和set的主要区别在于它们存储的元素类型：map存储键值对（key-value pairs），而set仅存储唯一的键值（通常是键本身作为值）。尽管如此，它们在底层数据结构（如红黑树）的实现上有很多相似之处
改造内容：
K：key的类型T：如果是map，则为pair<K, V>; 如果是set，则为KKeyOfT：通过T来获取key的一个仿函数类
<code>// Map 与 Set
// set -> RBTree<K, K, SetKeyOfT> _t;
// map -> RBTree<K, pair<const K, V, MapKeyOfT>> _t;
🌈1.1. 红黑树节点的改造
//枚举颜色
enum Color
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
// pair<K, V> _kv; // 上节内容使用的这种方式
T _data;
Color _col;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
🌈1.2 红黑树的主体框架
(1) K 是给find，erase用的，T 是给节点，insert用的；
(2) KeyOfT 是由于下面需要比较，但是比较时不知道T的类型， set是key类型的比较，map是pair类型的比较，要统一变成key的比较。
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; //const 迭代器
//其他功能的实现……
private:
Node* _root = nullptr;
};
2. 红黑树的迭代器
🎈2.1 迭代器基本设计
// 通过模板来达到const的迭代器的复用
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++()
{}
Self& operator--() //右根左
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator == (const Self& s)
{
return _node == s._node;
}
bool operator != (const Self& s)
{
return _node != s._node;
}
};
🎈2.2 begin()与end()
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置
实现代码如下：
(注意：此步需要在RBTree类的内部实现)，以便map,set的使用）
<code>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);
}
🎈2.3 operator++()与operator–()
operator++()
右不为空，右子树的最左节点右为空，沿着到根的路径找孩子是父亲左的那个祖先
operator–()
左不为空，左子树的最右节点左为空，沿着到根的路径找孩子是父亲右的那个祖先
注意：++和–正好是完全相反的
实现代码如下：
//从局部的某一个过程考虑
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()，特殊处理，走到中序最后一个节点
Node* rightMost = _root;
while (right && 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;
}
3. 红黑树相关接口的改造
✨3.1 Find 函数的改造
查找成功，返回查找到的那个节点的迭代器，查找失败，就返回 nullptr。
Iterator* Find(const K& key)
{
Node* cur = _root;
while (cur){
if (cur->_kv.first < key){
cur = cur->_right;
}
else if (cur->_kv.first > key){
cur = cur->_left;
}
else{
return Iterator(cur, _root);
}
}
return End();
}
✨3.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;// 通过仿函数KeyOfT来比较数据的大小
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 make_pair(Iterator(_root,_root), false);
}
}
cur = new Node(data);
// 注意，这里需要保存一个新增节点，以便用来返回
Node* newnode = cur;
// 新增节点。颜色红色给红色
cur->_col = RED;
// 此处省略变色的代码
return make_pair(Iterator(newnode,_root), true);
}
4. Set 和 map的模拟实现
🧩4.1 Set的基本设计
set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。
为了解决 set 中 key 值不能修改的问题，在传给 RBTree 的第二个模板参数前加 const 即可。
template<class K>
class set
{// SetKeyOfT：通过T来获取key的一个仿函数类
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
// typename告诉编译器这是类型，
// 因为set不能够进行修改，所以我们用const迭代器来初始化普通迭代器，来达到不能修改的目的
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;
};
//使用 const 迭代器
void Print(const set<int>& s) {
set<int>::const_iterator it = s.end();
while (it != s.begin()) {
--it;
cout << *it << " ";
}
cout << endl;
}
//测试代码
void test_set(){
set<int> s;
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 << " ";
cout << endl;
set<int>::iterator it = s.end();
while (it != s.begin())
{
--it;
cout << *it << " ";
}
//it += 10;
cout << endl;
Print(s);
}
🧩4.2 Map的基本设计
<code>template<class K, class V>
class map
{// MapKeyOfT：通过pair来获取kv.first的一个仿函数类
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:// map是一个key不能修改，value能够修改的结构
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();
}
// 复用RBTree中的插入
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
iterator find(const K& key)
{
return _t.Find(key);
}
// 重载map中的operatorp[]
// operatorp[] 当原数据中没有时，插入并初始化，有则修改second
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;
}
}
📖红黑树改造的完整代码及总结
<code>#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
//枚举颜色
enum Colour
{
RED,
BLACK
};
//节点类
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
// pair<K, V> _kv; // 上节内容使用的这种方式
T _data;
Colour _col;
RBTreeNode(const T& data)
: _data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};
// 通过模板来达到const的迭代器的复用
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()，特殊处理，走到中序最后一个节点
Node* rightMost = _root;
while (right && 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;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator == (const Self& s)
{
return _node == s._node;
}
bool operator != (const Self& s)
{
return _node != s._node;
}
};
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& t)
{
_root = Copy(t._root);
}
RBTree& operator=(RBTree 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;// 通过仿函数KeyOfT来比较数据的大小
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 make_pair(Iterator(_root,_root), false);
}
}
cur = new Node(data);
// 注意，这里需要保存一个新增节点，以便用来返回
Node* newnode = cur;
// 新增节点。颜色红色给红色
cur->_col = RED;
// 旋转变色
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;
// g
// p u
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
{
//u存在且为黑或不存在 ->变色再继续往上处理 + 变色
if (cur == parent->_left) { //cur存在那么cur一定为红色
// g
// p u
//c
//单旋，把p旋转上去，p作为子树根节点，g作为p的右
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
//双旋，将cur旋转上去，p作为cur的左，然后再旋转把cur旋转上去，g作为cur右边
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
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
// 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);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_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);
}
Iterator* Find(const K& key)
{
Node* cur = _root;
while (cur){
if (cur->_kv.first < key){
cur = cur->_right;
}
else if (cur->_kv.first > key){
cur = cur->_left;
}
else{
return Iterator(cur, _root);
}
}
return End();
}
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 << "存在连续的红色节点" << endl;
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 _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
void RotateL(Node* parent)
{
_rotateNum++;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
_rotateNum++;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
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;
}
private:
Node* _root = nullptr;
public:
int _rotateNum = 0;
};
以上就是红黑树的改造及封装map和set全部内容，需要我们好好掌握，希望我的博客能够帮助到你，感谢观看。
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。