旅游电子商务网站建设规划方案,手机代理企业网站,下载 wordpress语言包,零基础小程序开发教程文章目录 红黑树封装map和set1. 改良红黑树1.1 改良后的节点1.2 改良后的类分别添加仿函数代码 3. 封装map和set3.1 set3.2 map 3. 迭代器3.1 begin 和 end3.2 operator()和operator--()3.3 const迭代器set的迭代器map的迭代器 4. map的operator[]的重载5. 完整代码实现5.1 RBT… 文章目录 红黑树封装map和set1. 改良红黑树1.1 改良后的节点1.2 改良后的类分别添加仿函数代码 3. 封装map和set3.1 set3.2 map 3. 迭代器3.1 begin 和 end3.2 operator()和operator--()3.3 const迭代器set的迭代器map的迭代器 4. map的operator[]的重载5. 完整代码实现5.1 RBTree.h5.2 set.h5.3 map.h 红黑树封装map和set
1. 改良红黑树 如何改良可以参考stl源码 我们先看库中,map和set的大框架, 发现set在底层红黑树存储的是k,k的键值对不像我们平时认知以为只存储一个kmap在底层红黑树存储的是k,v的键值对。继续看库中红黑树的源码 发现在红黑树节点这里并不是我们之前实现的K, V形式而是只给了一个Value形式。 对于set第二个模板参数是K其节点中存储的就是K这里的Value就代表的是K; 对于map第二个模板参数是pairconst KV其节点中存储的就是pairconst KV这里的Value就代表的是pairconst KV; 那么在红黑树模板参数设计时为什么要多设计一个Key的模板参数呢? 是为了拿到单独的K类型find和erase这些接口函数的参数是K第二个模板参数才真正决定节点里面存储什么 1.1 改良后的节点
templateclass T
struct RBTreeNode //三叉链
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) //默认颜色给红色{}
};1.2 改良后的类
分别添加仿函数 插入和查找的过程中的比较不能想红黑树一样实现成kv.first的形式我们要实现成用节点中实际存储的类型去比较对于set存储的是K可以直接去比较对于map存储的是pair比较时是用pair比较但是pair的比较并不是我们想要的我们还是想要pair中的K比较 上面的问题我们可以看库中源码发现多给了一个模板参数KeyOfValue其目的是取出K可以分别给具体的仿函数来实现。 set这里直接返回key就行
struct SetKeyOfT
{const K operator()(const K key){return key;}
};map这里需要返回pair的first, 即K
struct MapKeyOfT
{const K operator()(const pairconst K, V kv){return kv.first;}
};那么为什么需要这么做对于set来说直接比较不就行了吗当然可以但是map并不是直接用_data类型比较(即pair本身), set为了和map复用同一棵红黑树所以要实现成这种形式 同样我们插入和查找时也需要修改用map和set传过来的仿函数定义出一个对象kot帮助我们取出帮助我们取出_data中的Key。
代码
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:~RBTree(){_Destroy(_root);_root nullptr;}Node* Find(const K key){Node* cur _root;KeyOfT kot; //仿函数定义出对象帮助我们取出_data中的Keywhile (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return cur; }}return nullptr;}bool Insert(const T data){//第一次插入if (_root nullptr){_root new Node(data);_root-_col BLACK; //根节点给黑色return true;}KeyOfT 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;}else{return false; //该元素已经在树中存在了, 无法插入}}//链接cur new Node(data);Node* newnode cur; //cur可能会变色, 需要提前记录curif (kot(parent-_data) kot(data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//处理红黑树颜色while (parent parent-_colRED){Node* grandfather parent-_parent;//找叔叔 看父亲在祖父的哪边if (grandfather-_left parent) {Node* uncle grandfather-_right;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整curgrandfather;parent cur-_parent;}else //情况23: u不存在/u存在且为黑, 旋转 变色{// g// p u// cif(curparent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else //(grandfather-_right parent){Node* uncle grandfather-_left;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else //情况23: u不存在/u存在且为黑, 旋转 变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK; //根节点是黑色的return true;}
private:Node* _root nullptr;
}; 3. 封装map和set
3.1 set
namespace yj
{templateclass Kclass set{//作用是将T中的key提取出来struct SetKeyOfT{const K operator()(const K key){return key;}};public:bool insert(const K key){return _t.Insert(key);}private:RBTreeK, K, SetKeyOfT _t;};
}3.2 map
namespace yj
{templateclass K, class Vclass map{//作用是将T中的key提取出来struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:bool insert(const pairconst K, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};
}3. 迭代器
迭代器的好处是可以方便遍历是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器需要考虑以前问题
3.1 begin 和 end
STL明确规定begin()与end()代表的是一段前闭后开的区间而对红黑树进行中序遍历后可以得到一个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置end()放在最大节点(最右侧节点)的下一个位置STL是将end()放在头结点的位置我们上次设计的RBTree没有头结点这个结构因此我们也就不与STL的实现方式完全一样end()就直接设置为nullptr。
iterator begin() // 中序遍历第一个
{Node *cur _root;while (cur cur-_left) //找最左侧节点{cur cur-_left;}return iterator(cur); // 节点指针构造的迭代器
}iterator end() // 最后一个节点的下一个
{return iterator(nullptr);
}3.2 operator()和operator–()
的实现思路: 右不为空, 下一个就是右子树的最左节点 右为空, 沿着到根的路径, 找孩子是父亲左的那个祖先
Self operator()
{if (_node-_right){// 1. 右不为空, 下一个就是右子树的最左节点Node *subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft; // 将节点的地址赋值即可}else{// 2. 右为空, 沿着到根的路径, 找孩子是父亲左的那个祖先Node *cur _node;Node *parent _node-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;
}–的实现思路: 与相反 左不为空, 下一个就是左子树的最右节点 左为空, 沿着到根的路径, 找孩子是父亲右的那个祖先
Self operator--()
{if (_node-_left){// 1. 左不为空, 下一个就是左子树的最右节点Node *subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight; // 将节点的地址赋值即可}else{// 2. 左为空, 沿着到根的路径, 找孩子是父亲右的那个祖先Node *cur _node;Node *parent _node-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;
}3.3 const迭代器
如果是const迭代器那可以在迭代器类中多加上两个模板参数T, T*偏特化当然实际上是RefPtr的全特化
那如何实现set的const迭代器呢由于set不能修改普通迭代器就是const迭代器const迭代器还是const迭代器
对于map来说普通迭代器就是普通迭代器const迭代器就是const迭代器但是map的pair中的value是可以修改的因此我们就需要在RBTree中把普通迭代器和const迭代器均实现出来同时也要支持从普通迭代器 隐式类型转换 成构造const迭代器的构造函数。当map的迭代器类模板被实例化成普通迭代器时它就是拷贝构造迭代器类模板被实例化成const迭代器时它是一个支持用普通迭代器构造初始化const迭代器的构造函数。 template class T, class Ref, class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT, Ref, Ptr Self;Node *_node;_RBTreeIterator(Node *node): _node(node){}// 1. typedef _RBTreeIteratorT, T, T* iterator; 拷贝构造//// 支持普通迭代器构造const迭代器的构造函数// 2. typedef _RBTreeIteratorT, const T, const T* const_iterator;// 支持从普通迭代器 隐式类型转换 成构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIteratorT, T , T * it): _node(it._node){}
}set的迭代器
typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;
typedef typename RBTreeK, 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();
}map的迭代器
typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;
typedef typename RBTreeK, pairconst 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();
}4. map的operator[]的重载
根据map的[]性质: 返回make_pairiterator,bool的first解引用找到节点value, 借助Insert函数同时需要将我们插入函数返回类型的从bool变成pair类型
V operator[](const K key)
{pairiterator, bool ret _t.Insert(make_pair(key, V())); //V()构造一个匿名对象return ret.first-second; // 找到retmake_pairiterator,bool的first解引用找到节点value
}pairiterator, bool Insert(const T data)
{// 第一次插入if (_root nullptr){_root new Node(data);_root-_col BLACK; // 根节点给黑色return make_pair(iterator(_root), true);}KeyOfT 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;}else{return make_pair(iterator(cur), false); // 该元素已经在树中存在了, 无法插入}}// 链接cur new Node(data);Node *newnode cur; // cur可能会变色, 需要提前记录curif (kot(parent-_data) kot(data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;// 处理红黑树颜色while (parent parent-_col RED){Node *grandfather parent-_parent;// 找叔叔 看父亲在祖父的哪边if (grandfather-_left parent){Node *uncle grandfather-_right;// 3种情况// 情况1: u存在且为红, 变色处理, 并继续向上处理// 变色: p,u变黑, g变红if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续向上调整cur grandfather;parent cur-_parent;}else // 情况23: u不存在/u存在且为黑, 旋转 变色{// g// p u// cif (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else //(grandfather-_right parent){Node *uncle grandfather-_left;// 3种情况// 情况1: u存在且为红, 变色处理, 并继续向上处理// 变色: p,u变黑, g变红if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续向上调整cur grandfather;parent cur-_parent;}else // 情况23: u不存在/u存在且为黑, 旋转 变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK; // 根节点是黑色的return make_pair(iterator(newnode), true);
}5. 完整代码实现
5.1 RBTree.h
#includeiostream
#includeutility
#includeassert.h
#includestdlib.h
using namespace std;//节点的颜色
enum Colour
{RED,BLACK,
};templateclass T
struct RBTreeNode //三叉链
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) //默认颜色给红色{}
};templateclass T,class Ref, class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT,Ref,Ptr Self;Node* _node;_RBTreeIterator(Node* node):_node(node){}// 1. typedef _RBTreeIteratorT, T, T* iterator; 拷贝构造// // 支持普通迭代器构造const迭代器的构造函数// 2. typedef _RBTreeIteratorT, const T, const T* const_iterator; //支持从普通迭代器 隐式类型转换 成构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIteratorT, T, T*it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_right){//1. 右不为空, 下一个就是右子树的最左节点Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft; //将节点的地址赋值即可}else{//2. 右为空, 沿着到根的路径, 找孩子是父亲左的那个祖先Node* cur _node;Node* parent _node-_parent;while (parent curparent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left){//1. 左不为空, 下一个就是左子树的最右节点Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight; //将节点的地址赋值即可}else{//2. 左为空, 沿着到根的路径, 找孩子是父亲右的那个祖先Node* cur _node;Node* parent _node-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}
};//仿函数
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:~RBTree(){_Destroy(_root);_root nullptr;}typedef _RBTreeIteratorT, T, T* iterator;typedef _RBTreeIteratorT, const T, const T* 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);}Node* Find(const K key){Node* cur _root;KeyOfT kot; //仿函数定义出对象帮助我们取出_data中的Keywhile (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return cur; }}return nullptr;}pairiterator,bool Insert(const T data){//第一次插入if (_root nullptr){_root new Node(data);_root-_col BLACK; //根节点给黑色return make_pair(iterator(_root), true);}KeyOfT 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;}else{return make_pair(iterator(cur), false); //该元素已经在树中存在了, 无法插入}}//链接cur new Node(data);Node* newnode cur; //cur可能会变色, 需要提前记录curif (kot(parent-_data) kot(data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//处理红黑树颜色while (parent parent-_colRED){Node* grandfather parent-_parent;//找叔叔 看父亲在祖父的哪边if (grandfather-_left parent) {Node* uncle grandfather-_right;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整curgrandfather;parent cur-_parent;}else //情况23: u不存在/u存在且为黑, 旋转 变色{// g// p u// cif(curparent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else //(grandfather-_right parent){Node* uncle grandfather-_left;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else //情况23: u不存在/u存在且为黑, 旋转 变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK; //根节点是黑色的return make_pair(iterator(newnode), true);}void Inorder(){_Inorder(_root);}int Height(){return _Height(_root);}bool IsBalance() //重点检查规则{//先检查根节点if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0; //基准值Node* cur _root;while(cur) //走最左路径{if (cur-_col BLACK)benchmark;cur cur-_left;}//连续红色节点return _Check(_root, 0,benchmark);}private://左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (ppnode nullptr) //parent本身就是根{_root subR;_root-_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 (ppnode nullptr){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}int _Height(Node* root){if (root nullptr)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _Check(Node* root, int blackNum, int benchmark) //基准值{if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}//DFS检查黑色节点数量if (root-_col BLACK){blackNum;}//反向检查 --- 红色节点不能连续if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}Node* _root nullptr;
};5.2 set.h
#includeRBTree.hnamespace yj
{templateclass Kclass set{//作用是将T中的key提取出来struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator, bool insert(const K key){return _t.Insert(key);}private:RBTreeK, K, SetKeyOfT _t;};
}5.3 map.h
#includeRBTree.hnamespace yj
{templateclass K, class Vclass map{//作用是将T中的key提取出来struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public://取类模板的内嵌类型前需要添加typename, 因为编译器无法区分取到的是内嵌类型还是静态变量//加typename告诉编译器这是类模板的内嵌类型typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator[](const K key){pairiterator,bool ret _t.Insert(make_pair(key, V()));return ret.first-second; //找到retmake_pairiterator,bool的first解引用找到节点value}pairiterator, bool insert(const pairconst K, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};
}
