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

做网站项目流程图模板网站程序语言那个好

news 2025/9/18 8:08:08
做网站项目流程图模板,网站程序语言那个好,公司官网如何搭建,网页设计欢迎页面1、红黑树的概念及性质 1.1概念 概念： 红黑树是一种二叉搜索树，以颜色(Red or Black)互斥来限制每条路径不会比另外的路径长出两倍，来达到近似平衡 1.2性质 红黑树的性质： 每个节点不是黑色就是红色根节点是黑色的如果一个节点是…

1、红黑树的概念及性质

1.1概念

概念：

红黑树是一种二叉搜索树，以颜色(Red or Black)互斥来限制每条路径不会比另外的路径长出两倍，来达到近似平衡

1.2性质

红黑树的性质：

  1. 每个节点不是黑色就是红色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子节点必须是黑色的(无连续的红节点)
  4. 对于每个节点，从该节点到其所有的后代叶节点的简单路径上，均包含相同数目的黑节点(每条路径都包含相同数量的黑色节点)
  5. 每个叶子节点都是黑色的(此叶子节点指的是NULL)

得知上面的有关红黑树的情况后，思考一个一个问题

它的性质如何保证最长路径不会超过最短路径的两倍？

考虑极端场景：

最短路径： 全黑                                最长路径：一直一黑一红

对比AVL树，高度是很接近logN

红黑树高度是很接近2*logN(红黑树搜索效率相对差一些，但几乎可以忽略不计)

但插入同样的数据，AVL树的高度更低，是通过多次旋转而得来的

2、红黑树的简单实现

2.1红黑树节点的定义

enum(枚举)里存的是节点的颜色

节点要有指向左节点、右节点、父节点的指针；节点存的值(数据)及节点的颜色

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;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

初始化(构造)节点，三指针指向空；_kv(值or数据)取决于传的值，_col默认为红色

为什么(插入)节点的颜色默认为红色呢？

如果插入黑色节点就会破坏规则：每条路径上黑色节点的数量相同

所以(插入)节点的默认颜色为红色

2.2插入

以下为简写：

u uncle 叔叔

p parent 父亲

g grandfather 爷爷

c cur遍历节点(可能是新插入节点)

情况一：

u(叔叔)存在且为红

g必为黑，若为红早就违反没有连续两个红色节点的规则

此时c节点一定是新插入的节点，且c节点的插入破坏了没有连续的红色节点的规则，所以我们需要对这颗红黑树进行调整

把g的颜色改为红色，将p/u的颜色改为黑色

注意：

g节点可能为根节点

若g节点为根节点，那么再将g节点变黑(根节点的颜色必须为黑色)，所有路径的黑色节点+1，所有路径的黑色节点数依然相等

若g节点非根节点，那么只需要将g作为cur继续向上调整颜色

情况二 

叔叔不存在或叔叔存在且为黑

 若叔叔不存在

那么c节点一定是新插入节点，因为叔叔不存在，那么p父亲下面就不能再挂黑色节点了(往p下面挂p路径有黑色节点，而u却没有)，不然就会违反"所有路径的黑色节点数量都相等"这条规则

若叔叔存在且为黑

那么c节点一定不是新插入的节点，若c节点为新插入节点，则在插入c之前就会违反"所有路径黑色节点数量相同"这一规则(g和u都为黑而p却非黑，c为插入默认为红，不平衡了)；c不是新插入节点那么c节点下面一定有黑色节点对应黑色的u节点以达到平衡

 这时候我们就要用到之前AVL数所用的旋转了

叔叔不存在

叔叔存在且为黑

对g进行右旋(p为g的左、c为p的左)，然后将p改为黑色，g改为红色

 上面的情况都是基于c节点在p节点左子树(左孩子节点)的条件下

当cur在p节点的右边，情况又是怎样的呢？

叔叔不存在

叔叔存在且为黑

当p为g的左而c为p的右边，单纯的单选已经解决不了了

要先对p进行左单旋，在对g进行右单旋(对比上下两个图就知道，其实只多了一步)

 

以上的所有情况都是基于父亲在爷爷左边的基础上的，还有父亲在爷爷右边的几种情况，不过和上面的大差不差，我就不细讲了 

红黑树其本质还是二叉搜索树，红黑树的插入还是以二叉搜索树的插入为基础所更改的

大概可以分为两步：

1. 以二叉搜索树的方式插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏(对其进行旋转或变色)

 代码

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); // 红色的//判断插入的节点该连接到父节点的左还是右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;if (parent == grandfather->_left)//父亲在爷爷左{Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){RotateR(grandfather);						//       gparent->_col = BLACK;						//    p    ugrandfather->_col = RED;					// c}else{RotateL(parent);RotateR(grandfather);						//        gcur->_col = BLACK;							//    p       ugrandfather->_col = RED;					//      c}break;}}else//父亲在爷爷右边{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑if (cur == parent->_right){RotateL(grandfather);		//      gparent->_col = BLACK;		//   u     pgrandfather->_col = RED;	//            c}else{RotateR(parent);RotateL(grandfather);						//		 gcur->_col = BLACK;							//  u        pgrandfather->_col = RED;					//          c}break;}}}_root->_col = BLACK;return true;
}

左旋右旋的代码

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_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;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}

 

2.3红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

一般写验证的话要跟他的性质反着来，比如根节点的颜色是黑色的，那么如果根节点的颜色为红色就返回false

具体性质可以列为以下三条

根节点颜色为黑色

没有连续的红色节点

所有路径的黑色节点数量相同

根节点颜色为黑色已经讲过了

没有连续的红色节点可以在走中序的同时判断，(cur为遍历节点)若cur的颜色为红色且cur的parent的颜色也为红色那么返回false

至于所有路径的黑色节点数量相同

可以先统计一下最左路径黑色节点的数量作为参考值，然后如果有哪条路径的黑色节点数量不等于这个参考值的话就返回false

bool IsValidRBTRee()
{if (_root && _root->_col == RED){return false;}int refBlackNum = 0;//黑节点参考值Node* cur = _root;while (cur){if (cur->_col == BLACK){refBlackNum++;}cur = cur->_left;}return _IsValidRBTRee(_root, 0, refBlackNum);
}bool _IsValidRBTRee(Node* cur, size_t blackCount, size_t refBlack)
{if (cur == nullptr){if (refBlack != blackCount){cout << "黑色节点不相等" << endl;return false;}return true;}if (cur->_col == RED && cur->_parent->_col == RED){cout << "存在连续红色节点" << endl;return false;}if (cur->_col == BLACK)blackCount++;return _IsValidRBTRee(cur->_left, blackCount, refBlack)&& _IsValidRBTRee(cur->_right, blackCount, refBlack);
}

3.全部代码

#pragma once
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;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};template<class K, class V>
class 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); // 红色的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;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){RotateR(grandfather);						//       gparent->_col = BLACK;						//    p    ugrandfather->_col = RED;					// c}else{RotateL(parent);RotateR(grandfather);						//        gcur->_col = BLACK;							//    p       ugrandfather->_col = RED;					//      c}break;}}else{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑if (cur == parent->_right){RotateL(grandfather);		//      gparent->_col = BLACK;		//   u     pgrandfather->_col = RED;	//            c}else{RotateR(parent);RotateL(grandfather);						//		 gcur->_col = BLACK;							//  u        pgrandfather->_col = RED;					//          c}break;}}}_root->_col = BLACK;return true;}/*获取红黑树最左侧节点*/Node* LeftMost(){Node* cur = _root;if (cur == nullptr ){return _root;}while (cur->_left){cur = cur->_left;}return cur;}// 获取红黑树最右侧节点Node* RightMost(){Node* cur = _root;if (nullptr == cur){return _root;}while (cur->_right){cur = cur->_right;}return cur;}// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){if (_root && _root->_col == RED){return false;}int refBlackNum = 0;//黑节点参考值Node* cur = _root;while (cur){if (cur->_col == BLACK){refBlackNum++;}cur = cur->_left;}return _IsValidRBTRee(_root, 0, refBlackNum);}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first<<" ";_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_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;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}bool _IsValidRBTRee(Node* cur, size_t blackCount, size_t refBlack){if (cur == nullptr){if (refBlack != blackCount){cout << "黑色节点不相等" << endl;return false;}return true;}if (cur->_col == RED && cur->_parent->_col == RED){cout << "存在连续红色节点" << endl;return false;}if (cur->_col == BLACK)blackCount++;return _IsValidRBTRee(cur->_left, blackCount, refBlack)&& _IsValidRBTRee(cur->_right, blackCount, refBlack);}
private:Node* _root = nullptr;
};void TestRBTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,10,12};RBTree<int,int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsValidRBTRee() << endl;
}

http://www.yayakq.cn/news/893006/

相关文章：

  • 怎么制作手机网站做网站的收益来源
  • 网站开发的基础课程阿里外贸平台
  • 成都专业的网站设计公司wordpress字数统计
  • 北京最大的网站建设有限公司家庭带宽100m做网站
  • 便宜高端网站设计wordpress如何备份数据库结构
  • 网站备案后换空间产品关键词大全
  • 网站主页设计素材培训教育机构
  • 效果好的网站制作公司自己做微信优惠券需要网站
  • 长沙营销型网站制制作英文网站案例
  • 金乡网站建设多少钱建设银行网站怎么查余额
  • 个人网站备案审批网站html模板
  • 西安 网站 高端 公司建站公司费用
  • 做网站的需要什么资质证明成都大学网站建设特色
  • 做简单的网站链接php网站建设实训引言
  • 网站规划与网页设计合肥大建设
  • 宁波网站建设制作网络公司知名做网站公司
  • wap网站在线生成公司开办流程
  • 网站中英文切换代码免费网站免费网站平台
  • 精通网站开发书籍做影视网站用什么网盘最好
  • 网站设计结果哪里app开发公司好
  • 建立个人网站主题wordpress 应用商店
  • 中国工程建设造价信息网站自助建站系统官网
  • 百度多久收录网站网站做两个版本
  • 不备案的网站很慢机械加工网论坛
  • 做外贸出口的网站万界商城系统
  • 医院网站如何备案旅游网站怎么做的
  • 黄石网站建网站logo
  • 菜鸟如何建网站注册官网
  • 网站采集来源成都网站开发等项目外包公司
  • 网站建设销售需要懂的知识大连营销型网站