图书网站策划书,帮做ppt的网站,东莞华为外包公司,杭州建设网站公司红黑树里面具体存的是什么类型的元素#xff0c;是由模板参数 T 来决定#xff1a; 如果 T 是 Key 那么就是 set。 如果 T 是 pairconst Key, V#xff0c;那么就是 map。 1、定义红黑树的节点结构
// 定义红黑颜色
enum Colour
{RED,BLACK
};templateclass … 红黑树里面具体存的是什么类型的元素是由模板参数 T 来决定 如果 T 是 Key 那么就是 set。 如果 T 是 pairconst Key, V那么就是 map。 1、定义红黑树的节点结构
// 定义红黑颜色
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){}
}; 2、 定义红黑树结构 定义红黑树结构KV K键值 key 的类型。T数据的类型如果是 map则为 pairconst K, V如果是 set则为 K。 【改造前】
templateclass K, class T
class RBTree
{typedef RBTreeNodeT Node; // 红黑树节点
public:RBTree() :_root(nullptr) {} // 构造函数bool Insert(const T data); // 插入节点// ...
private:Node* _root;
}; 红黑树的插入节点接口中要先通过比较节点中数据的大小来查找适合插入的位置但是红黑树并不知道数据 data 到底是 key 还是 pair。如果数据 data 是 key那么直接取 key 来作比较如果数据 data 是 pair则需要取 first 来作比较。 【思考】这该如何去实现对传进来的不同类型的数据都能进行比较呢
STL 源码是这样实现的通过传给模板参数 KeyOfValue 的是 set 的仿函数还是 map 的仿函数来应对不同类型数据的比较 【改造后】 改造后的红黑树结构增加了仿函数类还没完善好还差迭代器insert 和 operator[] 接口还没实现 我们自己写的代码通过给红黑树增加一个模板参数 KeyOfTKeyOfT 是一个仿函数类把 map 和 set 中实现的仿函数传给 KeyOfT根据传的不同数据类型 T (key / pair) 和该类型对应的仿函数 (SetKey / MapFirst)调用仿函数取出要比较的值(key / first)来进行比较。 红黑树的定义 K键值key的类型。T数据的类型如果是 map则为 pairconst K, V如果是 set则为 K。KeyOfT通过 T 的类型来获取 key 值的一个仿函数类。 templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node; // 红黑树节点
public:RBTree() :_root(nullptr) {} // 构造函数bool Insert(const T data); // 插入节点接口返回值目前是bool后续要改为pair// ...
private:Node* _root;
}; 【画图说明】
通过 T 的类型和对应的取 T 类型对象的值的仿函数就可以进行不同类型数据的比较了 #pragma onceenum 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){}
};templateclass T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, 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){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){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}
};templateclass K, class T, class KeyOfT
struct RBTree
{typedef RBTreeNodeT Node;
public:typedef __RBTreeIteratorT, T, T* iterator;iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}pairiterator, bool Insert(const T data){KeyOfT kot;if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root), 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(iterator(cur), 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* grandfater parent-_parent;assert(grandfater);assert(grandfater-_col BLACK);// 关键看叔叔if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况1uncle存在且为红变色继续往上处理if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况23uncle不存在存在且为黑else{// 情况2右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况3左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况2左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况3右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newnode), 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);}private:bool PrevCheck(Node* root, int blackNum, int benchmark){if (root nullptr){//cout blackNum endl;//return;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-_parent parent;}Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (_root parent){_root subR;subR-_parent nullptr;}else{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;}}private:Node* _root nullptr;
}; 一、红黑树的迭代器 迭代器的好处是可以方便遍历是数据结构的底层实现与用户透明。map 和 set 的迭代器是封装的红黑树的迭代器。 如果想要给红黑树增加迭代器需要考虑以前问题
1、begin() 与 end()
STL 明确规定begin() 与 end() 代表的是一段前闭后开的区间而对红黑树进行中序遍历后可以得到一个有序的序列。 SGI-STL源码中红黑树有一个哨兵位的头节点begin() 是放在红黑树中最小节点(即最左侧节点)的位置end() 是放在 end() 放在头结点的位置。 begin() 可以放在红黑树中最小节点即最左侧节点的位置end() 放在最大节点最右侧节点的下一个位置关键是最大节点的下一个位置在哪块 因为这里我们只是对它进行模拟理解它的底层原理即可为了不让代码太过复杂我们这里的模拟实现就不设定 header 结点直接让 end() 为 nullptr 即可。 templateclass K, class T, class KeyOfT
struct RBTree
{typedef RBTreeNodeT Node; // 红黑树节点
public:typedef _RBTreeIteratorT, T, T* iterator; // 迭代器iterator begin() // begin(): 指向红黑树的最左节点的迭代器{Node* left _root;while (left left-_left){left left-_left;}return iterator(left);// 注意单参数的构造函数支持隐式类型转换节点会被构造成迭代器// 所以也可以这样写return left;}iterator end() // end(): 指向nullptr的迭代器{return iterator(nullptr);}
private:Node* _root nullptr;
}; 2、operator()与operator--()
按照中序遍历左子树 -- 根 -- 右子树 来走分为以下几种情况 1、it 指向节点的右子树不为空 则 it 要访问的节点是右子树中序左子树 -- 根 -- 右子树的第一个节点也就是右子树中的最左节点即最大节点。 2、it 指向节点的右子树为空说明以 it 为根的子树已经访问完了且 it 的父亲存在it 是它父亲的右孩子说明 it 被访问完之后以 it 父亲为根的子树也就访问完了此时该访问 it 父亲的父亲了 则 it 要访问的节点是it 指向节点的父亲的父亲即节点 13。 3、it 指向节点的右子树为空且 it 父亲存在it 是它父亲的左孩子 则 it 要访问的节点是it 指向节点的父亲节点即节点 17。 【注意】 当 it 访问完最后一个节点后最后一个节点右子树为空此时整棵树已经访问完了cur 和 parent 会一直迭代走到根节点然后返回 _node parentparent为空我们在红黑树中 end() 的值给的也是空这样当 it 访问完最后一个节点后就等于 end() 了。 T数据的类型如果是 map则为 pairconst K, V如果是 set则为 K。 Ref数据的引用。Ptr数据的指针。 templateclass T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node; // 红黑树节点typedef __RBTreeIteratorT, 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() // 前置{// 按照中序来走分为两种情况// 1、当前节点右子树不为空则访问右子树的最大节点if (_node-_right ! nullptr){// 下一个就是右子树的最左节点Node* left _node-_right;while (left-_left){left left-_left;}_node left;}// 2、当前节点右子树为空else{// 找祖先里面孩子不是祖先的右的那个Node* parent _node-_parent;Node* cur _node;// (1)cur父亲存在且cur是父亲的右孩子则访问cur的父亲的父亲// (2)cur父亲存在且cur是父亲的左孩子则访问cur的父亲while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent; // 现在的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){cur cur-_parent;parent parent-_parent;}_node parent;}return *this; // 返回上一个节点的迭代器的引用}
}; 二、map和set的插入
map 和 set 的 insert 是封装的红黑树的插入节点接口所以我们先要模拟实现红黑树的插入。 功能插入元素时先通过该元素的 key 查找并判断该元素是否已在树中 如果在返回pair指向该元素的迭代器, false。如果不在先插入节点再返回pair指向该元素的迭代器, true。 T数据的类型如果是 map则为 pairconst K, V如果是 set则为 K。
pairiterator, bool Insert(const T data)
{//KeyOfT kot; // 实例化仿函数对象if (_root nullptr){_root new Node(data); // 插入新节点_root-_col BLACK; // 根节点为黑色return make_pair(iterator(_root), true); // 返回指向插入节点的迭代器, true}Node* parent nullptr;Node* cur _root; // 记录当前节点和它的父节点while (cur) // cur为空时说明找到插入位置了{if (KeyOfT()(data) KeyOfT()(cur-_data)) // 键值大于当前节点{parent cur;cur cur-_right;}else if (KeyOfT()(data) KeyOfT()(cur-_data)) // 键值小于当前节点{parent cur;cur cur-_left;}else // (KeyOfT()(data) KeyOfT()(cur-_data)) // 键值等于当前节点{// 不允许数据冗余return make_pair(iterator(cur), false); // 返回指向已有节点的迭代器, false}}// 插入新节点颜色为红色可能会破坏性质3产生两个连续红色节点cur new Node(data);Node* newnode cur; // 保存下插入的新节点的位置cur-_col RED;// 判断新节点是其父亲的左孩子还是右孩子if (KeyOfT()(cur-_data) KeyOfT()(parent-_data)){parent-_right cur;}else{parent-_left cur; }cur-_parent parent; // 更新cur的双亲指针while (parent parent-_col RED){Node* grandfater parent-_parent;assert(grandfater);assert(grandfater-_col BLACK);// 关键看叔叔if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况1uncle存在且为红变色继续往上处理if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况23uncle不存在存在且为黑else{// 情况2右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况3左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况2左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况3右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newnode), true); // 返回指向插入节点的迭代器, true
} 三、map 的模拟实现 map 的底层结构就是红黑树因此在 map 中直接封装一棵红黑树然后将其接口包装下即可。 namespace xyl
{templateclass K, class Vclass map{// 作用将value中的key提取出来struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first; // 返回pair对象中的key}};public:// 编译到这里的时候类模板RBTreeK, pairconst K, V, MapFirst可能还没有实例化// 那么编译器就不认识这个类模板更别说去它里面找iterator了// 所以要加typename告诉编译器这是个类型等它实例化了再去找它typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator, bool insert(const pairK, V kv){return _t.Insert(kv); // 底层调用红黑树的接口}// 功能传入键值key通过该元素的key查找并判断是否在map中// 1、在map中返回key对应的映射值的引用// 2、不在map中插入pairkey, value()再返回key对应映射值的引用V operator[](const K key){// 注意这里的V()是缺省值调用V类型的默认构造函数去构造一个匿名对象pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second; // 返回key对应映射值的引用}private:RBTreeK, pairK, V, MapKeyOfT _t; // 红黑树};
} 四、set 的模拟实现 set 的底层为红黑树因此只需在 set 内部封装一棵红黑树即可将该容器实现出来具体实现可参考 map。 namespace xyl
{templateclass Kclass set{// 作用是将value中的key提取出来struct SetKeyOfT{const K operator()(const K key){return key; 返回key对象中的Key}};public:// 编译到这里的时候类模板RBTreeK, K, SetKey可能还没有实例化// 那么编译器就不认识这个类模板更别说去它里面找iterator了// 所以要加typename告诉编译器这是个类型等它实例化了再去找它typedef typename RBTreeK, K, SetKeyOfT::iterator iterator; // 红黑树类型重命名iterator begin(){return _t.begin();}iterator end(){return _t.end();}// 插入元素keypairiterator, bool insert(const K key){return _t.Insert(key); // 底层调用红黑树的接口}// 中序遍历void inorder(){_t.InOrder();}private:RBTreeK, K, SetKeyOfT _t; // 红黑树};
}
