目录
1. set和map中的红黑树
2. 仿函数比较键值对
3. 红黑树迭代器的实现
3.1 迭代器++
3.2 迭代器--
3.3 map的operator[ ]
4. 完整代码
Set.h
Map.h
RedBlackTree.h
Test.cpp
本章完,
1. set和map中的红黑树
前一篇红黑树的源代码:
#pragma once#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;enum Colour // 枚举颜色
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col; // 比AVL树少了平衡因子,多了颜色RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}
};template<class K, class V>
struct RBTree
{typedef RBTreeNode<K, V> Node;
public: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{return false;}}cur = new Node(kv);cur->_col = RED; // 默认插入红色结点if (parent->_kv.first < kv.first) // 找到位置后插入结点{parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED) // 父亲存在且为红才需要处理{Node* grandfather = parent->_parent;assert(grandfather); // 确定的可以断言下,否则就是插入前就不是红黑树assert(grandfather->_col == BLACK);if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) // 情况一,叔叔存在且为红(可以直接复制到下面uncle在左边){ // 将父亲和叔叔改为黑,祖父改为红,然后把祖父当成cur,parent变祖父parent继续向上调整。parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况二或情况三:叔叔存在且为黑或叔叔不存在{if(cur == parent->_left) // 情况二的右旋+变色(parent在左){// g // p u// cRotateR(grandfather);parent->_col = BLACK; // 父亲变为根了grandfather->_col = RED;}else // 情况二的左右双旋+变色(parent在左){// g // p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK; // cur变为根了grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED) // 情况一,叔叔存在且为红{ // 将父亲和叔叔改为黑,祖父改为红,然后把祖父当成cur,parent变祖父parent继续向上调整。parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况二或情况三:叔叔存在且为黑或叔叔不存在{if (cur == parent->_right) // 情况二的左旋+变色(parent在右){// g // u p// cRotateL(grandfather);parent->_col = BLACK; // 父亲变为根了grandfather->_col = RED;}else // 情况二的右左双旋+变色(parent在右){// g // u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK; // cur变为根了grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED) // 验证性质二{cout << "根节点不是黑色" << endl;return false;}int benchmark = 0; // 黑色节点数量基准值//Node* cur = _root; // 这种方法是先遍历一遍,然后传值,不过我们可以传引用//while (cur)//{// if (cur->_col == BLACK)// {// ++benchmark;// }// cur = cur->_left;//}return PrevCheck(_root, 0, benchmark); // 验证性质三和四}protected:bool PrevCheck(Node* root, int blackNum, int& benchmark){if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark) // 验证性质三{cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED) // 验证性质四{cout << "存在连续的红色节点" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}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){Node* subR = parent->_right; // 动了三个标记了的结点,共更新六个指针,这更新两个指针Node* subRL = subR->_left;parent->_right = subRL;if (subRL) // subRL不为空才更新{subRL->_parent = parent;}Node* ppNode = parent->_parent; // 记录parent的parent,防止parent是一颗子树的头结点subR->_left = parent; // 再更新两个指针parent->_parent = subR;if (_root == parent) // 最后更新两个指针{_root = subR;subR->_parent = nullptr;}else // parent是一颗子树的头结点{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR; // 更新两个节点if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent; // 再更新两个节点parent->_parent = subL;if (_root == parent) // 最后更新两个结点{_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}Node* _root = nullptr;
};
在前一篇学习红黑树的时候,实现的是KV模型,节点中存放的是键值对pair。
而set中的节点只存放一个key值,map中的节点存放的是键值对。
但是map和set却使用的是同一颗红黑树。
这到底是怎么实现的呢?怎么做到一会儿是键值,一会又是键值对的呢?
看一下STL库中是如何实现的:
map和set中都既有key值,又有数据类型,map中的数据类型是键值对pair<const Key, T>,
而set中的数据类型也是key值。STL模板中,红黑树中的数据类型只有一个。
无论是map还是set,底层封装的都是红黑树,
区别在于给红黑树实例化的是什么类型的模板参数。
map给红黑树传的模板参数是键值对pair<const Key, T>。
set给红黑树传的模板参数是键值Key。
对于红黑树而言,它是不知道接收到的第二个模板参数value是什么类型的,
它只能推演。所以set对应的红黑树中的数据类型就是一个key值,
而map对应的红黑树中的数据类型就是一个键值对。
接下来就是对我们实现的红黑树进行改造,(配合上一篇一起看)
首先就是对结点进行改造,将原本的KV键值对数据类型改成T,像STL中一样,只有一个,
让编译器自己去推演这个数据类型是key值还是键值对:
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data; // 结点中的数据Colour _col; // 比AVL树少了平衡因子,多了颜色RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data){}
};
红黑树中也不再用键值对去构建新节点,而是使用那一个数据类型T。
先改一点是这样的:
Set.h:
#pragma once#include "RedBlackTree.h"namespace rtx
{template <class K>class set{protected:RBTree <K, K> _t;};
}
Map.h:
#pragma once#include "RedBlackTree.h"namespace rtx
{template <class K,class V>class map{protected:RBTree <K, pair<K, V>> _t;};
}
set中,向红黑树传的模板参数是<K,K>,第二个K传给节点,作为节点是数据类型。
map中,向红黑树传的模板参数是<K,pair<const K,T>>键值对,
第二个参数键值对pair<const K, T>传给节点,作为节点的数据类型。
现在有一个问题,给红黑树传模板参数时,第一个参数K类型的作用是什么?
对于insert来说,set和map中都可以不要第一个参数K,因为第二个参数中就有K,
可以用来比较。但是对于find接口来说,它需要的只是K。set中第二个参数也是K,
所以第一个K也可以省略。map中第二个参数是一个键值对,如果省略了第一K后,
红黑树中只有一个键值对类型,在使用find的时候,无法确定拿到first的数据类型,
此时就需要第一个模板参数K来确定find的类型了。
虽然set中可以不需要第一个模板参数K,但是map不可以,因它两使用的一个红黑树,
所以为了统一,第一个模板参数K不能省略。
2. 仿函数比较键值对
改了数据那插入的所有比较都要改了,
站在红黑树的角度,并不知道它接收到的模板参数value是来自set中的键值还是map中的键值对。
在插入结点进行比较时:
set:cur->data 与 data进行比较,插入结点中的key值直接和树中的key值比较大小,决定插入左还是右即可。
map:cur->data.first 与 data.first进行比较,插入结点中的键值对的first和树种键值对的first比较,决定插入左还是右。
既然使用的是模板,是泛型编程,那么在比较处到底该写成map和set中的哪种比较方式呢?
要知道set中的data不是键值对,是没有first的,而map中的data直接比较又不符合我们的要求。
(pair也能比较键值对,不过它在first一样时比较了second,但我们不想比较second)
(关于set和map的细节可以回去看看从C语言到C++_26,后面实现方括号也要知道细节)
此时我们也不能自己重新定义键值对的比较方式,因为人家库中已经有了,
我们无法再重载一个函数名,返回值,参数都相同的比较方式。
为了能够在红黑树中使用统一的比较方式,这里采用仿函数的方式:
在set和map中各定义一个仿函数,专门用来获取key值的,
并且将这个仿函数当作模板参数传给红黑树。
实现下仿函数和封装下insert,现在的部分代码就是这样:
- set中存放的数据本身就是key,所以获取key时有点多此一举,但是为了和红黑树的结构以及map的结构统一,也需要写一个。
- map中存放的数据是键值对,所以仿函数返回的是键值对中的first,依次来获取到key值。
在插入函数inset中,创建仿函数对象koft。
在需要进行键值key比较的位置,使用仿函数koft获取键值进行比较,然后决定插入左边函数右边。
使用仿函数的方法,压根就不用关心比较的是键值还是键值对,因为set和map都会给红黑树传它自己获取键值的仿函数,最终比较的都是键值。
set和map中的插入直接复用红黑树中的插入即可。
但是set中插入的是一个键值,而map中插入的是一个键值对。
跑一下测试用例:
#include "RedBlackTree.h"
#include "Set.h"
#include "Map.h"namespace rtx
{void TestSet(){set<int> s;s.insert(1);s.insert(5);s.insert(3);s.insert(5);}void TestMap(){map<int,int> m;m.insert(make_pair(6, 1));m.insert(make_pair(2, 1));m.insert(make_pair(3, 1));m.insert(make_pair(2, 1));}
}int main()
{rtx::TestSet();rtx::TestMap();return 0;
}
如果想遍历,那么就要实现迭代器了:
3. 红黑树迭代器的实现
这里实现的和库里的不太一样,库里的实现是带哨兵位头结点的,它指向根结点,
它的左指向中序遍历的第一个结点,右指向中序遍历的最后一个结点。
但不用哨兵位头结点也能实现,所以不改了。
set和map的迭代器就是红黑树的迭代器:
这里可以参考list的迭代器,红黑树也是通过指针来链接的。
template<class T, class Ref, class Ptr>
struct __RBTreeInterator
{
public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}
};
最基本的迭代如上面所示代码,迭代器中只有一个成员变量,那就是节点node。
下面就是逐渐完善迭代器支持的功能了,比如解引用,等于,加加,减减,等操作。
解引用+箭头+等于+不等于:(这里和链表是一样的,就不再详细讲解了)
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}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;}
};
比较的内容是两个迭代器指向节点是否相同,而不是节点中的值。
无论是普通对象还是const对象,都可以调用const版本,并且仅仅是进行比较,
所以只有const版本的就够用了。
3.1 迭代器++
set和map迭代器的++按照中序遍历的顺序进行加加的。
时刻铭记中序遍历的顺序:左子树 根 右子树
现在设想 it 迭代器在树的任意一个位置,它++可以分为以下情况:
① 右子树存在:
当++it以后,it指向的应是右子树中的最左节点,如图所示。
解决步骤:
将当前it指向节点的有子节点开始,一直寻找最左节点。找到后,让it指向最左节点。
② 右子树不存在:
it处于下图所示位置,位于子树的最右边,当++it后,it会指向哪呢?
it的右子树为空,肯定不能像上面那样找右子树最左边的节点。
解决步骤:
it是parent的右子树,说明父节点parent已经被访问过了,所以还需要继续向上走。
garent又是grandfather的右子树,说明祖父节点grandfather也被访问过了,
所以还需要继续向上走。grandfather是它父节点的左子树,按照中序遍历的顺序,
grandfather的父节点还没有被访问,所以it应该指向这里,也就是grandfather->parent节点。
当it右子树不存在时,++it后,it指向的是it所在子树是左子树的最近祖宗节点。
右子树不存在,如果it是中序最后一个节点呢?
当it指向的是红黑树最右边的节点时,再++it后,it应该指向最后一个节点的下一个节点。
但是红黑树最后一个节点的下一个节点并没有,所以我们让it指向nullptr。
我们按上面的步骤走,it也能指向空:
在代码中,无论是找到了++it后的位置,
还是it是最后一个节点,都会跳出循环,将it指向跳出循环的parent即可:
前置++:
Self& operator++(){if (_node->_right) // 右子树存在,++后就到右子树的最左结点{Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else // 右子树不存在,++后就到:所在子树是左子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的右的那个Node* cur = _node;while (parent && cur == parent->_right){ // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
后置++和前置++的唯一不同就是返回的是++之前的位置,
其他操作都一样,所以在改变it指向的位置之前,需要提前记录下要返回的it。
后置++返回类型不能用引用,因为记录位置的临时变量会销毁:
Self operator++(int){Self ret = Self(_node); // 记录当前位置 最后返回if (_node->_right) // 右子树存在,++后就到右子树的最左结点{Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else // 右子树不存在,++后就到:所在子树是左子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的右的那个Node* cur = _node;while (parent && cur == parent->_right){ // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return ret;}
3.2 迭代器--
迭代器减减的逻辑和加加是相反的,所以它的顺序应该是:右子树 根 左子树
① 左子树存在:
当左子树存在时,it减减后,应该指向的是左子树最右边的节点,如上图所示。
② 左子树不存在:
it是左子树,说明它的根节点就已经被访问过来,所以需要继续向上。
当找到it所在子树是右子树的最近祖宗时,将it指向这个祖宗节点。
因为是–,逻辑相反,所以此时减减it后,it指向it所在子树是右子树的最近祖宗节点,
同样,当it指向是第一个节点时,减减it会指向空节点。
前置--:
Self& operator--(){if (_node->_left) // 左子树存在,++后就到左子树的最右结点{Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else // 左子树不存在,++后就到:所在子树是右子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的左的那个Node* cur = _node;while (parent && cur == parent->_left){ // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
后置--:
Self& operator--(){if (_node->_left) // 左子树存在,++后就到左子树的最右结点{Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else // 左子树不存在,++后就到:所在子树是右子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的左的那个Node* cur = _node;while (parent && cur == parent->_left){ // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
迭代器写好之后,还要在红黑树中封装它,因为我们都是通过红黑树来使用的。
begin返回的是中序遍历的第一个结点,end返回的是最后结点的下一个,所以直接给空:
3.3 map的operator[ ]
map有一个特有的[],可以实现查找,插入,修改三个功能,下面来实现一下。
(我们在讲解map的时候放过这段代码)
V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}
需要对红黑树底层中的insert做修改:
1. 返回值改成pair<iterator, bool> : pair<iterator, bool> Insert(const T& data)
2. 空树时返回根的迭代器和true的键值对:return make_pair(iterator(_root), true);
3. 存在新插入的数据,返回原本存在的数据的迭代器和false
4. 插入成功,返回新插入数据的迭代器和true
红黑树底层的inset已经被修改了,set和map中的insert也需要被修改,改返回值就行。
4. 完整代码
底层的迭代器做好了,下一步就需要把它封装到set和map中:
Set.h
#pragma once#include "RedBlackTree.h"namespace rtx
{template <class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;//必须得加关键字typename。//当模板类没有进行实例化时,它就是一张图纸,在编译的时候并不参与编译。//因为域作用限定符::的存在,编译器在处理这条语句的时候,可能会将::后的iterator当作静态变量处理,参与编译。//所以就需要加关键字typename来告诉编译器这是一个模板类型,暂时不参与编译。iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}protected:RBTree <K, K, SetKeyOfT> _t;};
}
Map.h
#pragma once#include "RedBlackTree.h"namespace rtx
{template <class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; // 为什么+typename在set里iterator begin(){return _t.begin();}iterator end(){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(make_pair(key, V()));return ret.first->second;}protected:RBTree <K, pair<K, V>, MapKeyOfT> _t;};
}
RedBlackTree.h
#pragma once#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;enum Colour // 枚举颜色
{RED,BLACK
};template<class T>
struct RBTreeNode
{
public:RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data; // 结点中的数据Colour _col; // 比AVL树少了平衡因子,多了颜色RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data){}
};template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
public:typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}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;}Self& operator++(){if (_node->_right) // 右子树存在,++后就到右子树的最左结点{Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else // 右子树不存在,++后就到:所在子树是左子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的右的那个Node* cur = _node;while (parent && cur == parent->_right){ // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator++(int){Self ret = Self(_node); // 记录当前位置 最后返回if (_node->_right) // 右子树存在,++后就到右子树的最左结点{Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else // 右子树不存在,++后就到:所在子树是左子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的右的那个Node* cur = _node;while (parent && cur == parent->_right){ // 是右子树就往上走,parent存在是处理_node是中序最后一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return ret;}Self& operator--(){if (_node->_left) // 左子树存在,++后就到左子树的最右结点{Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else // 左子树不存在,++后就到:所在子树是右子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的左的那个Node* cur = _node;while (parent && cur == parent->_left){ // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self operator--(int){Self ret = Self(_node); // 记录当前位置 最后返回if (_node->_left) // 左子树存在,++后就到左子树的最右结点{Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else // 左子树不存在,++后就到:所在子树是右子树的最近祖宗节点。{Node* parent = _node->_parent; // 找祖先里面孩子不是祖先的左的那个Node* cur = _node;while (parent && cur == parent->_left){ // 是左子树就往上走,parent存在是处理_node是中序第一个结点的情况cur = cur->_parent;parent = parent->_parent;}_node = parent;}return ret;}
};template<class K, class T, class KeyOfT> // KeyOfT仿函数,把key取出来
struct RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}pair<iterator, bool> Insert(const T& data) // 1. 返回值改成pair<iterator, bool>{KeyOfT kot; // 定义一个仿函数的对象if (_root == nullptr){_root = new Node(data);_root->_col = BLACK; // 根给黑色return make_pair(iterator(_root), true); // 2. 空树时返回根的迭代器和true的键值对}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(cur, false); // 3. 存在新插入的数据,返回原本存在的数据的迭代器和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;assert(grandfather); // 确定的可以断言下,否则就是插入前就不是红黑树assert(grandfather->_col == BLACK);if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) // 情况一,叔叔存在且为红(可以直接复制到下面uncle在左边){ // 将父亲和叔叔改为黑,祖父改为红,然后把祖父当成cur,parent变祖父parent继续向上调整。parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况二或情况三:叔叔存在且为黑或叔叔不存在{if (cur == parent->_left) // 情况二的右旋+变色(parent在左){// g // p u// cRotateR(grandfather);parent->_col = BLACK; // 父亲变为根了grandfather->_col = RED;}else // 情况二的左右双旋+变色(parent在左){// g // p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK; // cur变为根了grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED) // 情况一,叔叔存在且为红{ // 将父亲和叔叔改为黑,祖父改为红,然后把祖父当成cur,parent变祖父parent继续向上调整。parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况二或情况三:叔叔存在且为黑或叔叔不存在{if (cur == parent->_right) // 情况二的左旋+变色(parent在右){// g // u p// cRotateL(grandfather);parent->_col = BLACK; // 父亲变为根了grandfather->_col = RED;}else // 情况二的右左双旋+变色(parent在右){// g // u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK; // cur变为根了grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true); // 4. 插入成功,返回新插入数据的迭代器和true}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED) // 验证性质二{cout << "根节点不是黑色" << endl;return false;}int benchmark = 0; // 黑色节点数量基准值//Node* cur = _root; // 这种方法是先遍历一遍,然后传值,不过我们可以传引用//while (cur)//{// if (cur->_col == BLACK)// {// ++benchmark;// }// cur = cur->_left;//}return PrevCheck(_root, 0, benchmark); // 验证性质三和四}protected:bool PrevCheck(Node* root, int blackNum, int& benchmark){if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark) // 验证性质三{cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED) // 验证性质四{cout << "存在连续的红色节点" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}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){Node* subR = parent->_right; // 动了三个标记了的结点,共更新六个指针,这更新两个指针Node* subRL = subR->_left;parent->_right = subRL;if (subRL) // subRL不为空才更新{subRL->_parent = parent;}Node* ppNode = parent->_parent; // 记录parent的parent,防止parent是一颗子树的头结点subR->_left = parent; // 再更新两个指针parent->_parent = subR;if (_root == parent) // 最后更新两个指针{_root = subR;subR->_parent = nullptr;}else // parent是一颗子树的头结点{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR; // 更新两个节点if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent; // 再更新两个节点parent->_parent = subL;if (_root == parent) // 最后更新两个结点{_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}Node* _root = nullptr;
};
Test.cpp
#include "RedBlackTree.h"
#include "Set.h"
#include "Map.h"namespace rtx
{void TestSet(){set<int> s;s.insert(3);s.insert(2);s.insert(1);s.insert(5);s.insert(3);s.insert(6);s.insert(4);s.insert(9);s.insert(7);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}void TestMap(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& str : arr){// 1、str不在countMap中,插入pair(str, int()),然后在对返回次数++// 2、str在countMap中,返回value(次数)的引用,次数++;countMap[str]++;}map<string, int>::iterator it = countMap.begin();while (it != countMap.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (const auto& kv : countMap) // 范围for也能用了(傻瓜替换){cout << kv.first << ":" << kv.second << endl;}}
}int main()
{rtx::TestSet();rtx::TestMap();return 0;
}
本章完,
下一部分:(哈希)闭散列和开散列(哈希桶)的实现,再然后是unordered_set和unordered_map介绍+哈希桶封装。