C++ 使用红黑树对set和map进行封装
前言
改造红黑树
优化节点
优化红黑树
没有迭代器的set和map
set.h
map.h
实现迭代器
迭代器封装
迭代器的++操作
迭代器的--操作
有迭代器的set和map（完全）
前言
使用前面实现的红黑树封装set和map，set是K模型的容器，map是KV模型的容器
改造红黑树
优化节点
enum Color
{BLACK,RED,
};template
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;Color _col;RBTreeNode(const T& data):_parent(nullptr),_left(nullptr),_right(nullptr),_data(data),_col(RED){}
}; 将之前的双参数
优化红黑树
// set->RBTree _t;
// map->RBTree, MapKeyOfT> _t;
template // 多传了一个仿函数，用于比较节点
class RBTree
{typedef RBTreeNode Node;public:bool Insert(const T& data){// 1.按搜索树的规则进行插入if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT koft; // 定义一个仿函数Node* parent = nullptr;Node* cur = _root;while (cur){if (koft(data) < koft(cur->_data)) // 获取set的K，或者pair里的K进行比较{parent = cur;cur = cur->_left;}else if (koft(data) > koft(cur->_data)){parent = cur;cur = cur->_right;}else{return false; // 这里不能写break}}cur = new Node(data);Node* newnode = cur;if (koft(parent->_data) < koft(data)){parent->_right = cur;}else if (koft(parent->_data) > koft(data)){parent->_left = cur;}cur->_parent = parent;// 新增红的结点cur->_col = RED;while (parent && parent -> _col == RED){// 红黑色的条件关键看叔叔Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1：uncle存在，且为红// 情况2 or 情况3：uncle不存在 or uncle存在,且为黑if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent; // 如果parent为空，即cur为_root,直接在最后将根变黑}else{// 情况三：双旋 -> 单旋if (cur == parent->_right){RotateL(parent);swap(parent, cur);}// 第二种情况（ps：有可能是第三种变过来的）RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}else if (grandfather->_right == parent){Node* uncle = grandfather->_left;// 情况1：uncle存在，且为红// 情况2 or 情况3：uncle不存在 or uncle存在,且为黑if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent; // 如果parent为空，即cur为_root,直接在最后将根变黑}else{// 情况三：双旋 -> 单旋if (cur == parent->_left){RotateR(parent);swap(parent, cur); // 交换的两个结点的指针}// 第二种情况（ps：有可能是第三种变过来的）RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}}_root->_col = BLACK;return true;}// 左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRLeft = subR->_left;parent->_right = subRLeft;if (subRLeft){subRLeft->_parent = parent;}Node* pparent = parent->_parent;subR->_left = parent;//parent->_parent = subR;// parent 是根// parent 不是根if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLRight = subL->_right;parent->_left = subLRight;if (subLRight){subLRight->_parent = parent;}Node* pparent = parent->_parent;subL->_right = parent; // parent->_parent = subL;// parent 是根// parent 不是根if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}}bool find(const K& key){KeyOfT koft;Node* cur = _root;while (cur){if (koft(cur->_data) > key)cur = cur->left;else if (koft(cur->_data) < key)cur = cur->right;elsereturn true;}return false;}void _InOrder(Node* root) // 注意是Node* 类型的{if (root == nullptr) return;_InOrder(root->_left);//cout << root->_kv.first << " " << root->_kv.second << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}private:Node* _root = nullptr;}; 没有迭代器的set和map
set.h
#include"RBTree2.h"templateclass set{struct SetKeyOfT // 仿函数返回k{const K& operator()(const K& k){return k;}}; public:pair Insert(const K& k){return _t.Insert(k);}private:RBTree _t;}; map.h
#include"RBTree2.h"template
class map
{struct MapKeyOfT{const K& operator()(const pair& kv)// 仿函数返回k{return kv.first;}};
public:bool Insert(const pair& kv){return _t.Insert(kv);}private:RBTree, MapKeyOfT> _t;
}; 实现迭代器
迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题：begin()与end()
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最后一个元素，此处就不行，因此最好的方式是下图
由于没有实现头结点，无法实现倒序打印
迭代器封装
template
class __TreeIterator
{typedef RBTreeNode Node;
public:typedef __TreeIterator Self;//如果Ref和Ptr都是非const，则下面与上面没区别，但如果是const，则下面仍是非const，//typedef __TreeIterator Self;typedef __TreeIterator iterator;Node* _node;__TreeIterator(Node* node):_node(node){}// 普通迭代器的时候，他是拷贝构造// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器__TreeIterator(const iterator& s)//加上这个，就满足普通迭代器赋值给const迭代器:_node(s._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){// 1、如果右不为空，中序的下一个就是右子树的最左节点// 2、如果右为空，表示_node所在的子树已经完成,在下一个节点在他的祖先中找// 沿着路径往上找孩子是它的左的那个祖先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 = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == 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;}}; 迭代器的++操作
1、如果右不为空，中序的下一个就是右子树的最左节点
2、如果右为空，表示_node所在的子树已经完成,下一个节点在他的祖先中找
沿着路径往上找孩子是它的左的那个祖先
Self& operator++(){// 1、如果右不为空，中序的下一个就是右子树的最左节点// 2、如果右为空，表示_node所在的子树已经完成,在下一个节点在他的祖先中找// 沿着路径往上找孩子是它的左的那个祖先if (_node->_right)// 右不为空{// 中序的下一个就是右子树的最左节点Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else // 右为空{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}迭代器的--操作
1、如果左不为空，中序的上一个就是左子树的最右节点
2、如果左为空，表示_node所在的子树已经完成,下一个节点在他的祖先中找
沿着路径往上找孩子是它的右的那个祖先
Self& operator--(){if (_node->_left){Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left) // 在父亲的右边即停止{cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}红黑树的优化
template // 多传了一个仿函数
class RBTree
{typedef RBTreeNode Node;public:typedef __TreeIterator iterator;typedef __TreeIterator const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left) {cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator end()const{return const_iterator(nullptr);}private:Node* _root = nullptr;}; 有迭代器的set和map（完全）
红黑树（RBTree2.h）
#pragma onceenum Color
{BLACK,RED,
};template
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;Color _col;RBTreeNode(const T& data):_parent(nullptr),_left(nullptr),_right(nullptr),_data(data),_col(RED){}
};template
class __TreeIterator
{typedef RBTreeNode Node;
public:typedef __TreeIterator Self;//如果Ref和Ptr都是非const，则下面与上面没区别，但如果是const，则下面仍是非const，//typedef __TreeIterator Self;typedef __TreeIterator iterator;Node* _node;__TreeIterator(Node* node):_node(node){}// 普通迭代器的时候，他是拷贝构造// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器__TreeIterator(const iterator& s)//加上这个，就满足普通迭代器赋值给const迭代器:_node(s._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){// 1、如果右不为空，中序的下一个就是右子树的最左节点// 2、如果右为空，表示_node所在的子树已经完成,在下一个节点在他的祖先中找// 沿着路径往上找孩子是它的左的那个祖先if (_node->_right)// 右不为空{// 中序的下一个就是右子树的最左节点Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else // 右为空{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == 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->RBTree _t;
// map->RBTree, MapKeyOfT> _t;
template // 多传了一个仿函数
class RBTree
{typedef RBTreeNode Node;public:typedef __TreeIterator iterator;typedef __TreeIterator const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left) {cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator end()const{return const_iterator(nullptr);}pair Insert(const T& data){// 1.按搜索树的规则进行插入if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root),true);}KeyOfT koft;Node* parent = nullptr;Node* cur = _root;while (cur){if (koft(data) < koft(cur->_data)){parent = cur;cur = cur->_left;}else if (koft(data) > koft(cur->_data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur), false); // 这里不能写break}}cur = new Node(data);Node* newnode = cur;if (koft(parent->_data) < koft(data)){parent->_right = cur;}else if (koft(parent->_data) > koft(data)){parent->_left = cur;}cur->_parent = parent;// 新增红的结点cur->_col = RED;while (parent && parent -> _col == RED){// 红黑色的条件关键看叔叔Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1：uncle存在，且为红// 情况2 or 情况3：uncle不存在 or uncle存在,且为黑if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent; // 如果parent为空，即cur为_root,直接在最后将根变黑}else{// 情况三：双旋 -> 单旋if (cur == parent->_right){RotateL(parent);swap(parent, cur);}// 第二种情况（ps：有可能是第三种变过来的）RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}else if (grandfather->_right == parent){Node* uncle = grandfather->_left;// 情况1：uncle存在，且为红// 情况2 or 情况3：uncle不存在 or uncle存在,且为黑if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent; // 如果parent为空，即cur为_root,直接在最后将根变黑}else{// 情况三：双旋 -> 单旋if (cur == parent->_left){RotateR(parent);swap(parent, cur); // 交换的两个结点的指针}// 第二种情况（ps：有可能是第三种变过来的）RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}// 左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRLeft = subR->_left;parent->_right = subRLeft;if (subRLeft){subRLeft->_parent = parent;}Node* pparent = parent->_parent;subR->_left = parent;//parent->_parent = subR;// parent 是根// parent 不是根if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLRight = subL->_right;parent->_left = subLRight;if (subLRight){subLRight->_parent = parent;}Node* pparent = parent->_parent;subL->_right = parent; // parent->_parent = subL;// parent 是根// parent 不是根if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}}iterator* find(const K& key){KeyOfT koft;Node* cur = _root;while (cur){if (koft(cur->_data) > key)cur = cur->left;else if (koft(cur->_data) < key)cur = cur->right;elsereturn iterator(cur);}return iterator(nullptr);}void _InOrder(Node* root) // 注意是Node* 类型的{if (root == nullptr) return;_InOrder(root->_left);//cout << root->_kv.first << " " << root->_kv.second << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance()//检查是否为红黑树结构{if (_root == nullptr){return true;}if (_root->_col != BLACK){return false;}int ref = 0;Node* left = _root;while (left){if (left->_col == BLACK){++ref;}left = left->_left;} //遍历这棵树，就好了，检查是否存在连续的红结点。//检查父亲，因为孩子不一定有，但是一定有父亲return Check(_root, 0, ref);}
private:Node* _root = nullptr;bool Check(Node* root, int blackNum, int ref){if (root == nullptr){if (blackNum != ref){cout << "违反规则：一条路径上的黑色节点数量不同" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则，出现连续红色结点" << endl;}if (root->_col == BLACK){++blackNum;}return Check(root->_left, blackNum, ref)&& Check(root->_right, blackNum, ref);}
}; set.h
#pragma once
#include"RBTree2.h"namespace hek
{templateclass set{struct SetKeyOfT // 仿函数返回k{const K& operator()(const K& k){return k;}}; public://加上typename是由于没有实例化的模板不能进行typedef。//由于set是不能修改的，因此均用consttypedef typename RBTree::const_iterator iterator;typedef typename RBTree< K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin()const{return _t.begin();}iterator end()const{return _t.end();}pair Insert(const K& k){pair::iterator, bool> ret = _t.Insert(k);return pair(ret.first, ret.second);//return _t.Insert(k);}private:RBTree _t;};void test_set2(const set& s){set::const_iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;set::const_iterator rit = s.begin();while (rit != s.end()){//*rit = 1; 报错cout << *rit << " ";--rit;}cout << endl;}void test_set(){set s;s.Insert(1);s.Insert(3);s.Insert(4);s.Insert(2);s.Insert(5);test_set2(s);set::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}
} map.h
#pragma once
#include"RBTree2.h"namespace hek
{templateclass map{struct MapKeyOfT{const K& operator()(const pair& kv)// 仿函数返回k{return kv.first;}};public:typedef typename RBTree, MapKeyOfT>::iterator iterator;typedef typename RBTree, MapKeyOfT>::const_iterator 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 Insert(const pair& kv){return _t.Insert(kv);}V& operator[](const K& key){pair ret = _t.Insert(make_pair(key, V()));// class T类型 是一个pair return ret.first->second;// ret.first >> 树的结点 节点存pair}private:RBTree, MapKeyOfT> _t;};void test_map2(const map& s){map::const_iterator it = s.begin();while (it != s.end()){cout << it->first << " " << it->second << endl;++it;}cout << endl;}void test_map(){map m;m.Insert(make_pair(1, 1));m.Insert(make_pair(3, 3));m.Insert(make_pair(6, 6));m.Insert(make_pair(7, 3));m.Insert(make_pair(8, 3));test_map2(m);map::iterator it = m.begin();while (it != m.end()){cout << it->first << " " << it->second << endl;++it;}cout << endl;string strArr[] = { "西瓜","西瓜","桃子","橘子","柚子","葡萄","黄瓜","西瓜","西瓜" };map countMap;for (auto& str : strArr){// 1、如果水果不在map中，则operator[]会插入pair，返回映射对象(次数)的引用进行了++// 2、如果水果在map中，则operator[]返回水果对应的映射对象(次数)的引用，对它++。.countMap[str]++;}for (auto& i : countMap){cout << i.first << ":" << i.second << endl;}}
} test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;
#include"RBTree2.h"
#include"map.h"
#include"set.h"int main()
{hek::test_map();hek::test_set();return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！