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

哪家专门做特卖网站浏览器下载安装2023最新版

哪家专门做特卖网站,浏览器下载安装2023最新版,推广软件赚钱的平台,网站建设企业最新报价文章目录一、红黑树二、用泛型红黑树模拟实现set三、用泛型红黑树模拟实现map一、红黑树 红黑树作为set和map的底层容器,既要实现插入key又要实现插入pair,所以做了稍许的改动,使其成为一颗泛型结构的红黑树,通过不同的实例化参数…

文章目录

  • 一、红黑树
  • 二、用泛型红黑树模拟实现set
  • 三、用泛型红黑树模拟实现map

一、红黑树

    红黑树作为set和map的底层容器,既要实现插入key又要实现插入pair,所以做了稍许的改动,使其成为一颗泛型结构的红黑树通过不同的实例化参数,实现set和map。如果要生成set,就传(key,key);如果要生成map,就传(key,pair),由第二个参数来控制生成容器的结构。


改动

    在定义模板的红黑树节点时,由template<class K, class V> 改为template<class T>,因为是泛型,所以原本的pair<K, V> _kv;改为T _data;。红黑树的模板template<class K, class V>也改为template<class T> ,在内部代码中,将所有的pair<K, V>都改为Tkv改为data

     在模拟实现set时,定义成员变量为RBTree<K, K> _t; ,在模拟实现map的时候,定义成员变量为RBTree<K, pair<K, V>> _t; 。但是在插入的过程中,比较大小时,不能用data来比较,因为对于map而言,data是pair,要用pair中的first来比较,可以使用仿函数来实现。


set的底层成员

RBTree<K, K, SetKeyOfT> _t;

map的底层成员

RBTree<K, pair<K, V>, MapKeyOfT> _t; 

红黑树的迭代器

     红黑树的begin迭代器是整棵树的最左侧节点,end迭代器是空。

     迭代器++分为两种情况,如果该节点右子树不为空,就找右子树的最左节点。如果该节点的右子树为空,就找祖先里面孩子不是祖先的右的那个。

     迭代器–分为两种情况,如果该节点右子树不为空,就找左子树的最右节点。如果该节点的右子树为空,就找祖先里面孩子不是祖先的左的那个。


泛型红黑树

#pragma once
enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data){}
};template<class T, class Ref, class Ptr> //此处的模版参数采用三个可以同时兼顾类型,引用,指针
struct __RBTreeIterator
{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){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;}
};template<class K, class T, class KeyOfT>
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){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;// 情况一 : uncle存在且为红,变色+继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 继续往上处理cur = grandfater;parent = cur->_parent;}// 情况二+三:uncle不存在 + 存在且为黑else{// 情况二:右单旋+变色//     g //   p   u// cif (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三:左右单旋+变色//     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{// 情况二:左单旋+变色//     g //   u   p//         cif (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三:右左单旋+变色//     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;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;
};

二、用泛型红黑树模拟实现set

#include "TRBTree.hPP"
namespace Jared
{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 begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};
}

三、用泛型红黑树模拟实现map

#include "TRBTree.hPP"
namespace Jared
{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告诉编译器这一段代码是类型,不是静态变量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;}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};
}
http://www.yayakq.cn/news/339250/

相关文章:

  • 好享购物官方网站购物多语言网站建设应注意哪些事项
  • 网站域名有什么用做软件下载网站有哪些
  • 网站建设案例策划qq官网在线登录网页版
  • 国外网站平台网站建设子目录
  • 专业平台网站建设网络推广是什么专业
  • 苏州建网站流程门花网站建设
  • 搭建网站的平台有哪些师德师风建设好的小学网站
  • 美妆网站开发背景网站建设焦作
  • 公司想做个网站怎么办网站建设 艺麟盛世
  • 西宁哪家网络公司做网站网站怎么做到秒收录
  • 企业网站优化分为哪两个方向宜昌seo优化
  • 中国电信网站备案流程石排网站仿做
  • 建网站大公司服装设计学校
  • 上海个人医疗网站备案表南京网站c建设云世家
  • 模板和网站是一体的吗诸城人才网招聘网
  • 网站手机端怎么制作教程商城建设网站
  • 网站推广策划书天河区做网站公司
  • 好的flash网站青岛网站建设 上流
  • 申请完域名怎么做网站html友情链接代码
  • 网站的关键词在哪设置苏州建站模板展示
  • 上市公司协会网站建设汇报全国新冠疫苗接种率
  • 3d建站网站开发必须要搭建环境吗
  • 上海的设计网站手机编辑网页的软件有哪些
  • 企业网站建设都需要什么准备揭阳 网站建设
  • 东莞专业网站推广平台wordpress添加友情练级
  • 南京网络推广建站计算机网站建设 是什么意思
  • 接网站开发的公司举报网站建设情况
  • 网站上做百度广告赚钱么网站上如何设置行间距
  • 爱网郑州互联网seo使用教程
  • 长春网站制作方案定制PHP网站开发工程师招聘