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

网站 优点合肥制作网站公司

网站 优点,合肥制作网站公司,界面设计报价,山东青岛网站建设公司1.什么是红黑树 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍#xff0c;因…1.什么是红黑树 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 性质 1. 每个结点不是红色就是黑色。 2. 根节点是黑色的。 3. 如果一个节点是红色的则它的两个孩子结点是黑色的即红色不能连续。 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点即每条路径黑色节点相同。 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 注意黑色节点相同红色节点不连续所以最长路径中节点个数不会超过最短路径节点个数的两倍。 2.红黑树的插入实现 由于红黑树是一颗二叉平衡搜索树所以它的性质和AVL树差不多AVL树的特性左右子树高度差的绝对值不超过一。 红黑树的插入可以分为两部分按照二叉搜索树的规则插入新节点然后判断是否需要旋转交换和改变颜色。 检测新节点的插入需要判断是否破坏了红黑树的性质因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论。 插入代码的实现 #pragma once using namespace std; #include assert.h namespace sss {enum Color{red,black};templateclass K,class Vstruct RedBlackTreeNode{RedBlackTreeNodeK,V* _left;RedBlackTreeNodeK, V* _right;RedBlackTreeNodeK, V* _parent;pairK, V _date;Color _col;RedBlackTreeNode(const pairK, V datemake_pair(0,0)):_left(nullptr),_right(nullptr),_parent(nullptr),_date(date)//, _col(black){}};templateclass K, class Vclass RedBlackTree{typedef RedBlackTreeNodeK, V Node;public:typedef RedBlackTree Tree;bool insert(const pairK, V date){if (_root nullptr){_root new Node(date);_root-_col black;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_date date){parent cur;cur cur-_right;}else if (cur-_date date){parent cur;cur cur-_left;}else{return false;}}cur new Node(date);cur-_col red;if (parent-_date.first date. first){parent-_right cur;}else {parent-_left cur;}cur-_parent parent;//Node* uncleparent-_parent-while (parent parent-_col red){Node* grandfater parent-_parent;assert(grandfater);assert(grandfater-_colblack);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{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 true;}void Inorder(){_Inorder(_root);}private://右旋void RotateR(Node* parent){Node* subl parent-_left;Node* sublr subl-_right;Node* prev parent-_parent;parent-_left sublr;if (sublr)sublr-_parent parent;parent-_parent subl;subl-_right parent;if (_root parent){_root subl;subl-_parent nullptr;}else{if (prev-_left parent){subl-_parent prev;prev-_left subl;}else{subl-_parent prev;prev-_right subl;}}}//左旋void RotateL(Node* parent){Node* subr parent-_right;Node* subrl subr-_left;Node* prev parent-_parent;parent-_right subrl;if (subrl)subrl-_parent parent;subr-_left parent;parent-_parent subr;if (_root parent){_root subr;subr-_parent nullptr;}else{if (prev-_left parent){subr-_parent prev;prev-_left subr;}else{subr-_parent prev;prev-_right subr;}}}void _Inorder(Node* _root){if (_root nullptr)return;_Inorder(_root-_left);cout _root-_date.first _root-_date.second endl;_Inorder(_root-_right);}private:Node* _root nullptr;};}
http://www.pierceye.com/news/329454/

相关文章:

  • 厦门国外网站建设公司排名上海自贸区注册公司优惠政策
  • 网站建设的公司实习做什么成都住建局官网住建智慧建管
  • 建一个免费看电影的网站犯法不国家企业信用信息没有网站怎么做
  • 长春网站vantage wordpress
  • 帝国cms如何做网站地图自己做的网站还要买域名么
  • 网站建设与维护税率网络营销案例及视频
  • 网站建设 繁体精品课网站制作
  • 常州 招网站开发seo的名词解释
  • 二级域名网站seo竞价网站建设
  • 麻栗坡网站建设正规网站建设
  • 邯郸网站建设哪家好重庆app开发
  • 自学网站开发多久大型网站建站
  • 网站设计定制多少钱新增备案网站负责人
  • 匿名聊天网站开发网站关键字挖掘
  • 外国域名注册很多网站做网站的人找不到了
  • 好的学习网站打广告免费浏览器网站
  • 美团先做网站还是app学生网站建设的总结与评价
  • 网站建设代理网站wordpress微博
  • dw建设网站视频宁波seo优化项目
  • 网站里添加百度地图浙江网站建设公司
  • php网站开发最新需求排名优化百度
  • 网站制作的电话智慧校园信息门户网站建设
  • 网站备案申请福田企业网站优化方案
  • 企业网站seo怎么做有空间站的国家
  • Linux网站建设总结网站建设目的确定
  • 怎么做网站的内部链接wordpress 写php页面跳转
  • 推广自己的网站网页设计代码html文件怎么查
  • 网站在线制作软件邯郸公众号小程序制作
  • 网站后台生成静态页面天津百度推广电话号码
  • 网站单个页面301跳转湖南省建设局网站