当前位置：首页 > news >正文

用一颗红黑树同时封装出map和set

news 来源：原创 2025/8/2 15:31:52

1. 红黑树源代码

2. 红黑树模版参数的控制

3. 红黑树节点当中存储的数据

4. 模板参数中仿函数的增加

5. 正向迭代器的实现

6. set模拟实现

7. map的模拟实现

8. 封装后的代码

8.1 红黑树的代码

8.2 正向迭代器的代码

8.3 set的代码

8.4 map的代码

1. 红黑树源代码

#pragma onceenum Colour
{RED,BLACK
};//定义的是红黑树中节点类型
template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;
};//定义红黑树
template<class K, class V>
class RBTree
{public:typedef RBTreeNode<K, V> Node;// 获取红黑树最左侧节点Node* LeftMost(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return cur;}// 获取红黑树最右侧节点Node* RightMost(){Node* cur = _root;while (cur && cur->_right){cur = cur->_right;}return cur;}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{//在树中找到了kv（插入失败）return false;}}//新建节点cur = new Node(kv);//如果kv大于父亲就插入到父亲的右边if (parent->_kv.first < kv.first){parent->_right = cur;}else{//如果kv小于父亲就插入到父亲的左边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){//   g// p   u//这里走的是情况1parent->_col = uncle->_col = BLACK;//最后我们会统一把根节点变黑，//所以就不怕grandfather是根节点而我们还让其变红grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u存在且为黑或不存在 --> 旋转+变色//    g//  p   u//c//单旋if (parent->_left == cur){//右旋RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//    g//  p   u//    c//双选//先左旋在右旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}}else{//父亲在爷爷的右边u//    g//  u   p//		 c//这里走的也是情况1Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//uncle存在为黑或者不存在走情况2和3if (parent->_right == cur){//    g//  u   p//		 c//左旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g//  u   p//	  c//先右旋在左旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}}}//根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）_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;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){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;}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}//判断是否为红黑树bool ISRBTree(){if (_root == nullptr){return true;}int BlackCount = 0;Node* cur = _root;while (cur){//我们获得最左边路径黑色节点的个数if (cur->_col == BLACK)BlackCount++;cur = cur->_left;}int count = 0;return _ISRBTree(_root, count, BlackCount);}//判断是否为红黑树的子函数bool _ISRBTree(Node* root, int count, int BlackCount){if (root == nullptr){if (count != BlackCount)return false;elsereturn true;}Node* cur = root;if (cur->_col == BLACK)count++;//如果当前节点是红色，那它一定有父节点if (cur->_col == RED && cur->_parent->_col == RED)return false;return _ISRBTree(root->_left, count, BlackCount) && _ISRBTree(root->_right, count, BlackCount);}void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first;cout << endl;_InOrder(root->_right);}Node* _root = nullptr;
};

2. 红黑树模版参数的控制

我们都知道，set是K模型的容器，而map是KV模型的容器，那我们如何用一棵KV模型的红黑树同时实现map和set呢？

这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。

template<class K, class T>
class RBTree

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key：

template<class K>
class set
{
public://...
private:RBTree<K, K> _t;
};

但如果是map容器，那么它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对：

template<class K, class V>
class map
{
public://...
private:RBTree<K, pair<K, V>> _t;
};

那能不能不要红黑树的第一个模板参数，只保留第二个模板参数呢？

乍眼一看好像是可以的，因为此时红黑树的第二个模板参数当中也是有键值Key的，但实际上红黑树的第一个模板参数是不能省略的。

对于set容器来说，省略红黑树的第一个参数当然没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase（通过Key来在红黑树中查找节点或者删除节点）。

3. 红黑树节点当中存储的数据

现在红黑树的模板参数变成了K和T，那么红黑树结点当中存储的应该是什么呢？

前面说到，由于上层容器的不同，底层红黑树当中的K和T也是不同的：

set容器：K和T都代表键值Key。
map容器：K代表键值Key，T代表由Key和Value构成的键值对。

对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。

这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对。

更改后代码如下：

enum Colour
{RED,BLACK
};//定义的是红黑树中节点类型
template<class T>
struct RBTreeNode
{RBTreeNode(const T& date):_left(nullptr), _right(nullptr), _parent(nullptr), _date(date), _col(RED){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _date;Colour _col;
};

4. 模板参数中仿函数的增加

现在由于结点当中存储的是T，这个T可能是Key，也可能是<Key, Value>键值对。那么当我们需要进行结点的键值比较时，应该如何获取结点的键值呢？

当上层容器是set的时候T就是键值Key，直接用T进行比较即可，但当上层容器是map的时候就不行了，此时我们需要从<Key, Value>键值对当中取出键值Key后，再用Key值进行比较。

因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。

仿函数，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

template<class K, class V>
class map
{//仿函数struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key{return kv.first;}};
public://...
private:RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

但是对于底层红黑树来说，它并不知道上层容器是map还是set，因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较。

因此，set容器也需要向底层红黑树传入一个仿函数，虽然这个仿函数单独看起来没什么用，但却是必不可少的。（毕竟set和map是都是通过传入的模版参数来构造红黑树，因为map需要向红黑树传递仿函数，因此set也被迫需要）

template<class K>
class set
{//仿函数struct SetKeyOfT{const K& operator()(const K& key) //返回键值Key{return key;}};
public://...
private:RBTree<K, K, SetKeyOfT> _t;
};

这样一来，当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较，下面以红黑树的查找函数为例：

Iterator* Find(const K& key)
{KeyOfT kot;Node* cur = _root;while (cur){//取cur->_date的key值//如果是pair那就是其firstif (kot(cur->_date) < key){cur = cur->_right;}else if (kot(cur->_date) > key){cur = cur->_left;}else{//这里返回迭代器需要传入root//是为了End(),这个我们后面再说//这里找到了返回当前位置的迭代器return Iterator(cur, _root);}}//找不到返回指向nullptr的迭代器return Iterator(nullptr,_root);
}

注意： 所有进行结点键值比较的地方，均需要通过仿函数获取对应结点的键值后再进行键值的比较。

5. 正向迭代器的实现

红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针

但由于如果是迭代器是从End()开始指向，然后减减进行逆向遍历，而此时End()返回的是指向nullptr位置的迭代器，因此如果只有一个节点指针我们是无法找到红黑树中最右的节点（最右节点存最大值）

因此我们这边在实现迭代器时，我们成员变量有2个，一个是保存指向树中节点的指针（能找到的情况下），另一个就是保存能指向根节点的指针（但保存能指向根节点的指针有可能旋转的时候会导致迭代器失效，这个我们后面再讲，现在大家可以先不考虑这个点）

template<class T, class Ref, class Ptr>
class RBTreeIterator
{//节点的类型，这里迭代器就是对节点进行封装typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;private:Node* _node;Node* _root;
};

因此，我们通过2个结点的指针便可以构造出一个正向迭代器。

RBTreeIterator(Node* node, Node* root):_node(node), _root(root)
{
}

当对正向迭代器进行解引用操作时，我们直接返回对应结点数据的引用即可。

Ref operator*()
{return _node->_date;
}

当对正向迭代器进行->操作时，我们直接返回对应结点数据的指针即可。

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走到了13这个节点的位置，那此时右不为空，所以++it，我们因该走到右子树当中的最左节点（这里说的最左节点，就是中序遍历最左节点），而当15走完时右为空，那如果cur节点是在父亲的左边，那++，就走到父亲就停下了，如图：15是在17的左边，所以++it（it没++前指向15这个位置）迭代器就走到指向17这个节点的位置

而如果it指向的是6这个节点，我们++it，此时6是在父亲的右边，那就说明父亲已经走过了，因为中序遍历是左根右，只有访问完1才会走到6，因此如果cur是父亲的右边，那就需要继续向上判断，直到找到cur是父亲的左边才停下来，或者走到parent为空

总结：

如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。
如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。

代码如下：

Self operator++()
{Node* cur = _node;//如果右边不为空，那就找右边中序(最左边)if (cur->_right){Node* leftMost = cur->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* parent = cur->_parent;//右为空有两种情况//下面这种情况就是一路找祖先parent->_right == curwhile (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}cur = parent;_node = cur;}return *this;
}

实现红黑树的正向迭代器时，一个结点的正向迭代器进行--操作后，应该根据红黑树中序遍历的序列找到当前结点的前一个结点。

具体逻辑如下：

首先，当it走到了13这个位置，那就说明13的右子树全都已经遍历完了，那如果13的左子树不为空，--it，就要找其左子树中的最右节点，如果如所示，如果it指向13，那--it迭代器就因该走到11这个节点。

那如果左子树为空，就比如现在it指向的是11这个节点，因为11是在8的右边，因此--it迭代器就因该指向8，也就是如果左子树为空，并且cur是在parent的右边，那--it，迭代器就指向parent即可。

那如果左子树为空，cur是在parent的左边，那要怎么办？那我们就要一直向上寻找孩子在父亲右边的祖先，如图：如果it指向的是15，那我们向上找祖先，我们发现当cur是17的时候parent是13，并且cur是在父亲的右边，因此--it，我们就让迭代器指向13节点即可。那如果it是在1这个节点，其parent在8，我们会发现如果一直向上找，当cur为13的时候，parent就是nullptr，那就说明我们整颗树都已经遍历完成了。

总结：

如果当前结点的左子树不为空，则--操作后应该找到其左子树当中的最右结点。
如果当前结点的左子树为空，则--操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。

代码如下：

Self operator--()
{if (_node == nullptr){Node* cur = _root;while (cur->_right){cur = cur->_right;}_node = cur;}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 && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

我们这个代码还而外判断了当_node等于nullptr的时候，因为要满足下面这种场景

因为End我们是用nullptr来构造的，因此当出现了it从指向end开始向前遍历的场景我们就需要通过传入的_root来找到树中的最右节点。

而之前我们说如果迭代器成员变量中加上了_root在旋转的过程中可能会出现迭代器失效的问题是：我们在插入或者寻找节点的时候返回的是迭代器，而如果出现旋转可能整颗树的根节点会改变，而此时我们寻找或者插入时返回的迭代器中_root就会失效（保存的根节点改变了，不是最新的根节点）

正向迭代器实现后，我们需要在红黑树的实现当中进行迭代器类型的typedef。需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。

然后在红黑树当中实现成员函数begin和end：

begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
end函数返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器。

//定义红黑树
template<class K, class T, class KeyOfT>
class RBTree
{public:typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> Const_Iterator;Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Const_Iterator End() const{return Const_Iterator(nullptr, _root);}Const_Iterator Begin()const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}
}

6. set模拟实现

完成上述操作后，set的模拟实现也就很简单了，其中的成员函数都是调用底层红黑树的对应接口就行了，只不过我这里要补充一个关于iterator和const_iterator的点

template <class K>
class set
{struct SetKeyOfT{const K& operator()(const K& k){return k;}};
public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::Const_Iterator const_iterator;pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin()const{return _t.Begin();}const_iterator end()const{return _t.End();}iterator find(const K& key) {_t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t; 
};

首先set和map我们都不希望修改元素的key值，而set在K前面加const进行修饰传给红黑树的模板参数，就能使得我们节点中的元素无法被修改。

注意点：

我们在定义迭代器的时候，我们需要再第二个参数K前面加上const，我们在使用的时候可以把_t前面的模板参数直接复制上去就可以了。那如果在声明定义的时候我们不加const，那我们定义出来的迭代器不是_t中的，因为类型不匹配，那生成红黑树也不同。

而这里我重点说下通过我们传入的模板参数，在_t中生成的迭代器是怎样的（map有类似）

首先我们要了解下面的生成的迭代器我们需要一个共识

如下图所示

其实typeid().name()打印出来有些时候也不真实

是这样子的，typeid().name的方式打印出来的类型非常的简单和粗糙，不能作为真实类型的依据，就简单看看就好了，并且精确类型的打印，标准库中没有专门提供，所以一般来说，后期如果有需要，是会通过下载boost库的
因为在boost库中，有一个boost::typeindex库，他这个就可以做到非常精确的打印

因此我们就以下图为准

我们可以看见const int和const const int是同一类型，因此我们继续往下看

7. map的模拟实现

map的模拟实现也是相同的道理，其成员函数也是调用底层红黑树的对应接口，但对于map来说，我们是希望对pair<K,V>中的first值不能修改，但是second是可以修改的，并且在实现map的时候我们还需要额外实现[]运算符的重载函数。

class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& k){return k.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;pair<iterator, bool> insert(const pair<K, V>& T){return _t.Insert(T);}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}V& operator[](const K& k){pair<iterator, bool> ret = _t.Insert({k, V()});return ret.first->second;}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

8. 封装后的代码

虽然封装过程已经阐述完毕了，但在代码更改过程中还是有许多细节的，下面给出完整封装后的代码。

8.1 红黑树的代码

#pragma onceenum Colour
{RED,BLACK
};//定义的是红黑树中节点类型
template<class T>
struct RBTreeNode
{RBTreeNode(const T& date):_left(nullptr), _right(nullptr), _parent(nullptr), _date(date), _col(RED){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _date;Colour _col;
};template<class T, class Ref, class Ptr>
class RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;
public:RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}//判断两个正向迭代器是否不同bool operator!=(const Self& s) const{return _node != s._node; //判断两个正向迭代器所封装的结点是否是同一个}//判断两个正向迭代器是否相同bool operator==(const Self& s) const{return _node == s._node; //判断两个正向迭代器所封装的结点是否是同一个}Ref operator*(){return _node->_date;}Ptr operator->(){return &(_node->_date);}Self operator++(){Node* cur = _node;//如果右边不为空，那就找右边中序(最左边)if (cur->_right){Node* leftMost = cur->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* parent = cur->_parent;//右为空有两种情况//下面这种情况就是一路找祖先parent->_right == curwhile (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}cur = parent;_node = cur;}return *this;}Self operator--(){if (_node == nullptr){Node* cur = _root;while (cur->_right){cur = cur->_right;}_node = cur;}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 && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self s1){return _node != s1._node;}private:Node* _node;Node* _root;
};//定义红黑树
template<class K, class T, class KeyOfT>
class RBTree
{public:typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> Const_Iterator;Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Const_Iterator End() const {return Const_Iterator(nullptr, _root);}Const_Iterator Begin()const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}pair<Iterator, bool> Insert(const T& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return { Iterator(_root, _root),true };}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_date) < kot(kv)){parent = cur;cur = cur->_right;}else if (kot(cur->_date) > kot(kv)){parent = cur;cur = cur->_left;}else{return { Iterator(cur,_root),false };}}cur = new Node(kv);Node* Newnode = cur;if (kot(parent->_date) < kot(kv)){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){//   g// p   u//这里走的是情况1parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u存在且为黑或不存在 --> 旋转+变色//    g//  p   u//c//单旋if (parent->_left == cur){//右旋RotateR(grandfather);grandfather->_col = cur->_col = RED;parent->_col = BLACK;}else{//    g//  p   u//    c//双选//先左旋在右旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}}else{//父亲在爷爷的右边u//    g//  u   p//		 c//这里走的也是情况1Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//uncle存在为黑或者不存在走情况2和3if (parent->_right == cur){//    g//  u   p//		 c//左旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g//  u   p//	  c//先右旋在左旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}}}_root->_col = BLACK;return { Iterator(Newnode,_root),true };}//左旋void RotateL(Node* parent){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){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;}}Iterator* Find(const K& key)
{KeyOfT kot;Node* cur = _root;while (cur){//取cur->_date的key值//如果是pair那就是其firstif (kot(cur->_date) < key){cur = cur->_right;}else if (kot(cur->_date) > key){cur = cur->_left;}else{//这里返回迭代器需要传入root//是为了End(),这个我们后面再说//这里找到了返回当前位置的迭代器return Iterator(cur, _root);}}//找不到返回指向nullptr的迭代器return Iterator(nullptr,_root);
}//判断是否为红黑树bool ISRBTree(){if (_root == nullptr){return true;}int BlackCount = 0;Node* cur = _root;while (cur){//我们获得最左边路径黑色节点的个数if (cur->_col == BLACK)BlackCount++;cur = cur->_left;}int count = 0;return _ISRBTree(_root, count, BlackCount);}//判断是否为红黑树的子函数bool _ISRBTree(Node* root, int count, int BlackCount){if (root == nullptr){if (count != BlackCount)return false;elsereturn true;}Node* cur = root;if (cur->_col == BLACK)count++;if (cur->_col == RED && cur->_parent->_col == RED)return false;return _ISRBTree(root->_left, count, BlackCount) && _ISRBTree(root->_right, count, BlackCount);}void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first;cout << endl;_InOrder(root->_right);}Node* _root = nullptr;
};

8.2 正向迭代器的代码

在红黑中的代码中，我们是有包含迭代器的代码，但是这里为了更好的了解，我在单独拿出来展示

template<class T, class Ref, class Ptr>
class RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;
public:RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}//判断两个正向迭代器是否不同bool operator!=(const Self& s) const{return _node != s._node; //判断两个正向迭代器所封装的结点是否是同一个}//判断两个正向迭代器是否相同bool operator==(const Self& s) const{return _node == s._node; //判断两个正向迭代器所封装的结点是否是同一个}Ref operator*(){return _node->_date;}Ptr operator->(){return &(_node->_date);}Self operator++(){Node* cur = _node;//如果右边不为空，那就找右边中序(最左边)if (cur->_right){Node* leftMost = cur->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* parent = cur->_parent;//右为空有两种情况//下面这种情况就是一路找祖先parent->_right == curwhile (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}cur = parent;_node = cur;}return *this;}Self operator--(){if (_node == nullptr){Node* cur = _root;while (cur->_right){cur = cur->_right;}_node = cur;}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 && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self s1){return _node != s1._node;}private:Node* _node;Node* _root;
};

8.3 set的代码

template <class K>
class set
{struct SetKeyOfT{const K& operator()(const K& k){return k;}};
public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::Const_Iterator const_iterator;pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin()const{return _t.Begin();}const_iterator end()const{return _t.End();}iterator find(const K& key) {_t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t; 
};

8.4 map的代码

template<class K, class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& k){return k.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;pair<iterator, bool> insert(const pair<K, V>& T){return _t.Insert(T);}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}V& operator[](const K& k){pair<iterator, bool> ret = _t.Insert({k, V()});return ret.first->second;}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

1. 红黑树源代码

2. 红黑树模版参数的控制

3. 红黑树节点当中存储的数据

4. 模板参数中仿函数的增加

5. 正向迭代器的实现

6. set模拟实现

7. map的模拟实现

8. 封装后的代码

8.1 红黑树的代码

8.2 正向迭代器的代码

8.3 set的代码

8.4 map的代码

相关文章：