C++：基于红黑树封装map和set

目录

红黑树的修改

红黑树节点

红黑树结构

红黑树的迭代器

红黑树Insert函数

红黑树的默认成员函数

修改后完整的红黑树 

set、map的模拟实现

set

map

测试封装的set和map

---

红黑树的修改

想要用红黑树封装map和set，需要对之前实现的key-value红黑树进行修改，因为map是key-value结构而set是key结构，之前实现的红黑树不能满足需求。

我们需要将key和key-value抽象统一成成一个类型T，需要修改红黑树节点类和红黑树类进行。

红黑树节点

enum Color{RED,BLACK};//T代表set传过来的key或者map传过来的（pair）key-valuetemplate<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 K, class T, class KeyOfT>class RBTree{typedef RBTreeNode<T> Node;public:    //...private:Node* _root = nullptr;};

3个模板参数的解释：

1.对于K，代表的是key的类型，无论你是set和map，key的类型都是需要传入的，因为在Find函数的参数需要用到key的类型，如果是set，K和T都代表key的类型，第一个模板参数可有可没有，但是对于map来说，T代表的key-value类型（pair），没有第一个参数的话就无法拿到key的类型，从而无法实现Find函数。

2.对于T，代表的是红黑树里存的是key还是key-value。

3.对于KeyOfT，这个参数其实是一个仿函数（对一个struct类重载  () ），这个仿函数是为了拿到T里面的key的具体值，因为Insert函数涉及到key的比较，如果是map的话，T是key-value，拿不到具体的key值，就无法实现Insert函数，对于set的话，KeyOfT是可有可没有的。

红黑树的迭代器

红黑树的迭代器是对红黑树节点指针的封装，其实现与list的迭代器类似，但是由于红黑树的遍历走的是中序遍历，所以其迭代器的++走的是当前节点中序遍历的下一个节点，其--也是类似的道理。所以想要实现迭代器关键是实现++和--，其余部分与list的迭代器类似。

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){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};

实现红黑树中序遍历++

实现++的核心就是只关注局部逻辑而不看全局，只考虑中序遍历的下一个节点。

迭代器it++时：

1.如果it指向的当前节点的右子树不为空，则去找当前节点的右子树的最左节点。2.如果it指向的当前节点的右子树为空，则去向上寻找一个特殊节点，该特殊节点是其父亲的左节点，此时特殊节点的父亲就是当前节点中序遍历的下一个节点。

 上述逻辑是根据二叉树中序遍历总结而来。

//前置++，返回++之后的值Self operator++(){// 当前节点的右子树不为空，中序的下一个节点是// 当前节点的右子树的最左（最小）节点if (_node->_right){Node* rightMin = _node->_right;while (rightMin->_left)rightMin = rightMin->_left;_node = rightMin;}//当前节点的右子树为空，说明当前节点所属的子树已经中序遍历访问完毕//往上寻找中序遍历的下一个节点，找到一个节点是父亲的左节点的特殊节点//此时特殊节点的父亲就是当前节点中序遍历的下一个节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//后置++Self operator++(int){Self tmp = *this;++(*this);return tmp;}

由于有关迭代器的函数 begin() 和 end() 是左闭右开区间，这里我们就用nullptr作为 end() ，这里的++逻辑也是可以兼顾到 end()。

假设当前节点是中序遍历的最后一个节点，也就是整棵树的最右节点，其右子树为空，向上寻找的过程中，找不出满足条件的特殊节点（根节点的父亲是nullptr），parent为空时退出循环，给_node赋值，还是找到了当前节点中序遍历的下一个节点。

实现红黑树中序遍历--

这与++的逻辑是相反的，也可以当成反中序遍历右根左的++。

//前置--Self operator--(){//处理end()的情况//--end()得到的应该是中序遍历的最后一个节点//整一棵树的最右节点if (_node == nullptr){Node* rightMost = _root;while (rightMost && rightMost->_right)rightMost = rightMost->_right;_node = rightMost;}//当前节点的左子树不为空，找左子树的最右节点else if (_node->_left){Node* leftMost = _node->_left;while (leftMost && leftMost->_right)leftMost = leftMost->_right;_node = leftMost;}//当前节点的左子树为空else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//后置--Self operator--(int){Self tmp = *this;--(*this);return tmp;}

实现迭代器的完整代码

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* rightMin = _node->_right;while (rightMin->_left)rightMin = rightMin->_left;_node = rightMin;}//当前节点的右子树为空，说明当前节点所属的子树已经中序遍历访问完毕//往上寻找中序遍历的下一个节点，找到一个节点是父亲的左节点的特殊节点//此时特殊节点的父亲就是当前节点中序遍历的下一个节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//后置++Self operator++(int){Self tmp = *this;++(*this);return tmp;}//前置--Self operator--(){//处理end()的情况//--end()得到的应该是中序遍历的最后一个节点//整一棵树的最右节点if (_node == nullptr){Node* rightMost = _root;while (rightMost && rightMost->_right)rightMost = rightMost->_right;_node = rightMost;}//当前节点的左子树不为空，找左子树的最右节点else if (_node->_left){Node* leftMost = _node->_left;while (leftMost && leftMost->_right)leftMost = leftMost->_right;_node = leftMost;}//当前节点的左子树为空else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//后置--Self operator--(int){Self tmp = *this;--(*this);return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};

红黑树Insert函数

对Insert函数的修改，主要修改其返回值和key的比较逻辑，返回值应改为pair<Iterator, bool>，key的比较逻辑用KeyOfT实例化出来的对象比较即可。

pair<Iterator, bool> Insert(const T& data){//按二叉搜索树插入if (_root == nullptr){_root = new Node(data);//根节点为黑色_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(_root, _root), true);return { Iterator(_root, _root), true };}//仿函数，获取T中的具体的keyKeyOfT 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;}elsereturn { Iterator(cur, _root), false };}cur = new Node(data);Node* newnode = cur;//非空树插入红色节点cur->_col = RED;//判断cur应该插入到parent的左节点还是右节点if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;//链接父亲cur->_parent = parent;//父亲是红色节点，出现连续的红色节点，要处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//判断叔叔是grandfather的左节点还是右节点if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新颜色cur = grandfather;parent = cur->_parent;}else  //uncle不存在 或者 uncle存在且为黑{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 if (parent == grandfather->_right){Node* uncle = grandfather->_left;//uncle存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新颜色cur = grandfather;parent = cur->_parent;}else //uncle不存在 或者 uncle存在且为黑{if (cur == parent->_right){//     g//   u   p//        cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u    p //      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//更新颜色时，_root的颜色可能会改变//当grandfather是_root时//    g        更新颜色时，parent和uncle会变黑//  p   u      grandfather会变红// c//所以必须加这句代码保证_root的颜色为黑。_root->_col = BLACK;return { Iterator(newnode, _root), true };}

红黑树的默认成员函数

主要是补充之前实现红黑树时没有写的拷贝构造函数、赋值重载函数和析构函数。

​    //默认构造RBTree() = default;//拷贝构造RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}//赋值重载RBTree<K, T, KeyOfT>& operator=(const RBTree<K, T, KeyOfT> t){std::swap(_root, t._root);return *this;}//析构~RBTree(){Destroy(_root);_root = nullptr;}    Node* Copy(Node* root)    {    if (root == nullptr)    return nullptr;    //前序遍历复制    Node* newnode = new Node(root->_data);    newnode->_col = root->_col;    newnode->_left = Copy(root->_left);    if (root->_left)    root->_left->_parent = newnode;    newnode->_right = Copy(root->_right);    if (root->_right)    root->_right->_parent = newnode;        return newnode;    }    void Destroy(Node* root)    {    if (root == nullptr)    return;    Destroy(root->_left);    Destroy(root->_right);    delete root;    root = nullptr;    }​

修改后完整的红黑树 

​enum Color{RED,BLACK};//T代表set传过来的key或者map传过来的（pair）key-valuetemplate<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* rightMin = _node->_right;while (rightMin->_left)rightMin = rightMin->_left;_node = rightMin;}//当前节点的右子树为空，说明当前节点所属的子树已经中序遍历访问完毕//往上寻找中序遍历的下一个节点，找到一个节点是父亲的左节点的特殊节点//此时特殊节点的父亲就是当前节点中序遍历的下一个节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//后置++Self operator++(int){Self tmp = *this;++(*this);return tmp;}//前置--Self operator--(){//处理end()的情况//--end()得到的应该是中序遍历的最后一个节点//整一棵树的最右节点if (_node == nullptr){Node* rightMost = _root;while (rightMost && rightMost->_right)rightMost = rightMost->_right;_node = rightMost;}//当前节点的左子树不为空，找左子树的最右节点else if (_node->_left){Node* leftMost = _node->_left;while (leftMost && leftMost->_right)leftMost = leftMost->_right;_node = leftMost;}//当前节点的左子树为空else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//后置--Self operator--(int){Self tmp = *this;--(*this);return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{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*> Const_Iterator;//默认构造RBTree() = default;//拷贝构造RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}//赋值重载RBTree<K, T, KeyOfT>& operator=(const RBTree<K, T, KeyOfT> t){std::swap(_root, t._root);return *this;}//析构~RBTree(){Destroy(_root);_root = nullptr;}//中序遍历的第一个节点是整棵树的最左节点Iterator begin(){Node* cur = _root;while (cur && cur->_left)cur = cur->_left;return Iterator(cur, _root);}Iterator end(){return Iterator(nullptr, _root);}Const_Iterator begin() const{Node* cur = _root;while (cur && cur->_left)cur = cur->_left;return Const_Iterator(cur, _root);}Const_Iterator end() const{return Const_Iterator(nullptr, _root);}void RotateR(Node* parent){//subL为parent的左孩子节点Node* subL = parent->_left;//subLR为subL的右子节点Node* subLR = subL->_right;// 将parent与subLR节点进行链接parent->_left = subLR;//在SubLR的情况下更改，让其指向正确的父亲if (subLR)subLR->_parent = parent;//提前记录祖父节点Node* pParent = parent->_parent;//链接subL与parentsubL->_right = parent;parent->_parent = subL;//根据parent是否是根节点进行不同处理if (parent == _root){_root = subL;subL->_parent = nullptr;}else{//将pParent和subL链接//但得先判断parent是pParent的左节点还是右节点if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;//修改subL的parent指针，让其指向正确的父亲subL->_parent = pParent;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}}pair<Iterator, bool> Insert(const T& data){//按二叉搜索树插入if (_root == nullptr){_root = new Node(data);//根节点为黑色_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(_root, _root), true);return { Iterator(_root, _root), true };}//仿函数，获取T中的具体的keyKeyOfT 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;}elsereturn { Iterator(cur, _root), false };}cur = new Node(data);Node* newnode = cur;//非空树插入红色节点cur->_col = RED;//判断cur应该插入到parent的左节点还是右节点if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;//链接父亲cur->_parent = parent;//父亲是红色节点，出现连续的红色节点，要处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//判断叔叔是grandfather的左节点还是右节点if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新颜色cur = grandfather;parent = cur->_parent;}else  //uncle不存在 或者 uncle存在且为黑{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 if (parent == grandfather->_right){Node* uncle = grandfather->_left;//uncle存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上更新颜色cur = grandfather;parent = cur->_parent;}else //uncle不存在 或者 uncle存在且为黑{if (cur == parent->_right){//     g//   u   p//        cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u    p //      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//更新颜色时，_root的颜色可能会改变//当grandfather是_root时//    g        更新颜色时，parent和uncle会变黑//  p   u      grandfather会变红 // c//所以必须加这句代码保证_root的颜色为黑。_root->_col = BLACK;return { Iterator(newnode, _root), true };}Iterator Find(const K& key)    {    Node* cur = _root;    KeyOfT kot;    while (cur)    {    if (key > kot(cur->_data))    cur = cur->_right;    else if (key < kot(cur->_data))    cur = cur->_left;    else    return Iterator(cur, _root);    }    return Iterator(nullptr, _root);    }int Height(){return _Height(_root);}int Size(){return _Size(_root);}private: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;}int _Size(Node* root){if (root == nullptr) return 0;return _Size(root->_left) + _Size(root->_right) + 1;}Node* Copy(Node* root){if (root == nullptr)return nullptr;//前序遍历复制Node* newnode = new Node(root->_data);newnode->_col = root->_col;newnode->_left = Copy(root->_left);if (root->_left)root->_left->_parent = newnode;newnode->_right = Copy(root->_right);if (root->_right)root->_right->_parent = newnode;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}private:Node* _root = nullptr;};​

set、map的模拟实现

对红黑树进行修改后，只需对其接口函数进行封装和实现KeyOfT仿函数即可。

set

template<class K>class set{//实现keystruct 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>::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<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator Find(const K& key){return _t.Find(key);}private://加const令其不能修改keyRBTree<K, const K, SetKeyOfT> _t;};

map

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;typedef typename RBTree<K, pair<const K, V>, 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<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert({ key, V() });return ret.first->second;}iterator Find(const K& key){return _t.Find(key);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

测试封装的set和map

void test_myset1(){zh::set<int> s;s.insert(3);s.insert(1);s.insert(5);s.insert(4);s.insert(6);auto it = s.Find(3);cout << *it << endl;it++;cout << *it << endl;auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}

void test_Mymap1(){zh::map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });auto it = dict.Find("sort");cout << it->first << ":" << it->second << endl;cout << endl;it = dict.begin();while (it != dict.end()){//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;it++;}cout << endl;it = dict.end();it--;while (it != dict.begin()){cout << it->first << ":" << it->second << endl;it--;}cout << endl;dict["left"] = "左边，剩余";dict["insert"] = "插入";dict["string"];for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}}

---

 拜拜，下期再见?

摸鱼ing?✨?