关于这两个数据结构的insert接口实现 请看这篇文章 https://blog.csdn.net/l23456789mmmmm/article/details/139500413?spm=1001.2014.3001.5501
map::operator[]底层实现请看这篇文章 c++map类operator[]详解_c++ map operator-CSDN博客
红黑树模拟实现
#pragma once
#include <vector>
#include <iostream>
#include <queue>namespace mystl {enum COLOR {RED,BLACK};template<class K,class V>struct ListNode { // 节点//typedef ListNode<K, V> node;using Node = ListNode<K, V>;ListNode(std::pair<K,V> kv):_kv(kv) {_parent = _left = _right = nullptr;_color = RED;}Node* _parent;Node* _left;Node* _right;std::pair<K, V> _kv;COLOR _color;};template<class K,class V,class Ref = V& ,class Ptr = V*>struct RBTree_Iterator { //迭代器using Node = ListNode<K, V>;using iterator = RBTree_Iterator<K, V>;RBTree_Iterator(Node* node) {_node = node;}Ref operator*() {return _node->_kv.second;}Ptr operator->() {//return &(this->operator*());return &(_node->_kv.second);}bool operator!=(iterator it) {return _node != it._node;}iterator operator++() {if (_node->_right) {Node* leftMin = _node->_right;while (leftMin->_left) {leftMin = leftMin->_left;}_node = leftMin;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Node* _node;};template<class K,class V,class Compare = std::less<K>> // class Alloc = std::allocator<pair<const K, V> > > 这个是空间适配器,先不理他class RBTree { // 红黑树using Node = ListNode<K, V>;public:using iterator = RBTree_Iterator<K, V, V&, V*>;using const_iterator = RBTree_Iterator<K, V, const V&, const V*>;Node* GetRoot() {return _root;}size_t Size() {return _size;}void print() {std::queue<Node*> s1 ,s2;s1.push(_root);while (!s1.empty()) {while (!s1.empty()) {if (s1.front()) {s2.push(s1.front()->_left);//std::cout << s1.front()->_kv.first <<' ';printf(" %d : %d ", s1.front()->_kv.first, s1.front()->_color);s2.push(s1.front()->_right);}else {printf(" # ");}s1.pop();}std::swap(s1, s2);std::cout << std::endl;}}std::pair<iterator,bool> insert(const std::pair<K, V>& kv) {Node* new_node = new Node(kv);_size++;if (_root == nullptr) {new_node->_color = BLACK;_root = new_node;return std::make_pair(iterator(new_node), true);}Node* child = _root;Node* father = _root; // 父子交替,找 新节点应该插入的地方while (child) { //儿子不是空father = child;if (child->_kv.first > kv.first) {child = child->_left;}else if (kv.first > child->_kv.first) {child = child->_right;}else {_size--;return std::make_pair(iterator(child), false);}}//此处儿子是空,代表新节点应该插入的地方add_node(father, new_node);//对插入的节点进行检查,不合理的地方重构reconstitution(new_node);return std::make_pair(iterator(new_node), true);}bool IsValidRBTree(){Node* pRoot = GetRoot();// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_color){std::cout << "违反红黑树性质二：根节点必须为黑色" << std::endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;Node* pCur = pRoot;while (pCur){if (BLACK == pCur->_color)blackCount++;pCur = pCur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);}V& operator[](const K key) {return insert({ key,V() }).first->second;}iterator begin() {Node* tmp = _root;while (tmp && tmp->_left) {tmp = tmp->_left;}return tmp;}iterator end() {return nullptr;}const_iterator cbegin() {Node* tmp = _root;while (tmp && tmp->_left) {tmp = tmp->_left;}return tmp;}const_iterator cend() {return nullptr;}protected:void add_node(Node* father, Node* new_node) {if (new_node->_kv.first > father->_kv.first) {father->_right = new_node;}else {father->_left = new_node;}new_node->_parent = father;}void reconstitution(Node* new_node) {/*1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)*/if (new_node == _root) {return;}if (new_node->_parent->_color == BLACK) // 父亲是黑色,插入红色节点,符合红黑树要求,不做处理return;// 父亲是红色,此时不符合条件三,需要发生重构Node* parent = new_node->_parent; // 新节点的父节点Node* grandparent = new_node->_parent->_parent; // 爷爷节点Node* uncle = nullptr; // 叔叔节点if (grandparent->_left == parent) { // 叔叔节点需要通过父亲节点与爷爷节点的关系来判断uncle = grandparent->_right; }else {uncle = grandparent->_left;}// 判断情况if (uncle == nullptr || uncle->_color == BLACK) { // 叔叔为空,需要发生旋转Node* tmp = revorve(new_node, parent, grandparent);if (tmp == _root) {tmp->_color = BLACK;}else {reconstitution(tmp);}}else if (uncle->_color == RED) {// 叔叔为红色 需要改变颜色,并继续向上重构,因为新的爷爷节点被强制改为红色,需要继续向上重构uncle->_color = parent->_color = BLACK;if (grandparent != _root) {// 爷爷节点不为root的话grandparent->_color = RED;reconstitution(grandparent);}}//else { // 叔叔节点为黑色// // 旋转// reconstitution(revorve(new_node, parent, grandparent));//}}Node* revorve(Node* node,Node* parent,Node* grandparnt) {if (node == parent->_left && parent == grandparnt->_left) {// 子为父左，父为爷左，右旋父revorveR(parent);node->_color = BLACK;return parent;}else if(node == parent->_left && parent == grandparnt->_right) {// 子为父左，父为爷右，右旋子，左旋子revorveR(node);revorveL(node);parent->_color = BLACK;return node;}else if (node == parent->_right && parent == grandparnt->_right) {// 子为父右，父为爷右，左旋父revorveL(parent);node->_color = BLACK;return parent;}else {// 子为父右，父为爷左，左旋子，右旋子revorveL(node);revorveR(node);parent->_color = BLACK;return node;}}void revorveL(Node* node){// 左旋需要改变node节点的 1.本身 2.父节点 3.爷爷节点 4.左孩子节点 共计四个节点// 记录四个节点的值，防止等下修改时混乱Node* parent = node->_parent;Node* grandparent = parent->_parent;Node* leftchild = node->_left;// 1.修改本身节点node->_parent = grandparent;node->_left = parent;// 2.修改父节点parent->_parent = node;parent->_right = leftchild;if (parent == _root)_root = node;// 3. 修改爷爷节点if (grandparent != nullptr) {if (grandparent->_left == parent)grandparent->_left = node;else {grandparent->_right = node;}}// 4. 修改左孩子节点if(leftchild != nullptr)leftchild->_parent = parent;}void revorveR(Node* node){// 右旋需要改变node节点的 1.本身 2.父节点 3.爷爷节点 4.右孩子节点 共计四个节点// 记录四个节点的值，防止等下修改时混乱Node* parent = node->_parent;Node* grandparent = parent->_parent;Node* rightchild = node->_right;// 1.修改本身节点node->_parent = grandparent;node->_right = parent;// 2.修改父节点parent->_parent = node;parent->_left = rightchild;// 3. 修改爷爷节点if (grandparent != nullptr) {if (grandparent->_left == parent)grandparent->_left = node;else {grandparent->_right = node;}}// 4. 修改右孩子节点if(rightchild!=nullptr)rightchild->_parent = parent;}bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount) {//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){std::cout << "违反性质四：每条路径中黑色节点的个数必须相同" << std::endl;return false;}return true;}// 统计黑色节点的个数if (BLACK == pRoot->_color)k++;// 检测当前节点与其双亲是否都为红色Node* pParent = pRoot->_parent;if (pParent && RED == pParent->_color && RED == pRoot->_color){std::cout << "违反性质三：没有连在一起的红色节点" << std::endl;return false;}return _IsValidRBTree(pRoot->_left, k, blackCount) &&_IsValidRBTree(pRoot->_right, k, blackCount);}private:Node* _root = nullptr;size_t _size = 0;};
}set封装
#pragma once
#include "RBTree.h"
namespace mystl {template<class K>class set {public:using RBT = RBTree< const K, K>;using iterator = RBTree_Iterator<const K, K, K&, K*>;using const_iterator = RBTree_Iterator<const K, K, const K&, const K*>;iterator begin() {return _Tree.begin();}iterator end() {return _Tree.end();}const_iterator cbegin() const {return _Tree.cbegin;}const_iterator cend() const {return _Tree.cend();}bool operator != (set<K>& newset) {return _Tree != newset._Tree;}std::pair<iterator, bool>& insert(const K k) {return _Tree.insert(std::make_pair(k,k));}iterator find(const K& key) {return insert({ key,key }).first;}size_t size() {return _Tree.Size();}bool IsRBTree() {return _Tree.IsValidRBTree();}private:RBT _Tree;};
}map封装
#pragma once
#include "RBTree.h"
namespace mystl {template<class K,class V>class map { public:using RBT = RBTree< const K, std::pair<const K, V>>;using iterator = RBTree_Iterator<const K, std::pair<const K, V>, std::pair<const K,V>&,std::pair<const K, V> *>;using const_iterator = RBTree_Iterator<const K, std::pair<const K, V>, const std::pair<const K, V>&,const std::pair<const K, V>*>;iterator begin() {return _Tree.begin();}iterator end() {return _Tree.end();}const_iterator cbegin() const {return _Tree.cbegin;}const_iterator cend() const {return _Tree.cend();}std::pair<iterator, bool> insert(const std::pair<K, V> &kv) {return _Tree.insert({ kv.first,kv });}iterator find(const K& key) {return insert({key,V()}).first;}bool operator != (const map<K,V>& newmap) {return _Tree != newmap._Tree;}V& operator[](const K& key) {//_Tree.insert(std::pair<key,std::pair<key,V()> >);iterator ret = _Tree.insert({key,{key,V()}}).first;//iterator ret = _Tree.insert({ key,{key,V()} }).first;//std::pair<iterator, bool> ret = _Tree.insert(std::make_pair(key, V()));return ret._node->_kv.second.second;}size_t size() {return _Tree.Size();}bool IsRBTree() {return _Tree.IsValidRBTree();}private:RBT _Tree;};
}
