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

asp.net mvc 手机网站百度热搜榜历史

asp.net mvc 手机网站,百度热搜榜历史,桂林漓江阳朔,网站建设流程有目录 一、红黑树的概念 二、红黑树的性质 三、红黑树节点的定义 四、红黑树的插入(步骤) 1.为什么新插入的节点必须给红色? 2、插入红色节点后,判定红黑树性质是否被破坏 五、插入出现连续红节点情况分析图解(看…

目录

一、红黑树的概念

二、红黑树的性质

三、红黑树节点的定义

四、红黑树的插入(步骤)

1.为什么新插入的节点必须给红色?

2、插入红色节点后,判定红黑树性质是否被破坏

五、插入出现连续红节点情况分析+图解(看uncle节点)

5.1、uncle存在且为红

5.2、uncle不存在

1、单旋

2、双旋

5.3、uncle存在且为黑

1、单旋

2、双旋

六、插入总结

1、红黑树插入的两种步骤

 2、插入代码

七、红黑树总结及代码


一、红黑树的概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制

红黑树确保——没有一条路径会比其他路径长出两倍,因而是接近平衡的


二、红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的 

3. 如果一个节点是红色的,则它的两个孩子结点是黑色的 (没有连续的红节点

4. 从任一结点到其所有后代叶结点的简单路径上,均包含相同数目的黑结点 

5. 每个叶子结点都是黑色的(此处的叶子结点指的是NIL空结点)

        最优情况:全黑或每条路径都是一黑一红的满二叉树,高度logN

        最差情况:每颗子树左子树全黑,右子树一黑一红。高度2*logN。

        可以发现,最坏情况的时间复杂度和AVL树一样,都是O(logN),但是红黑树这种近似平衡的结构减少了大量旋转,综合性能优于AVL树。


三、红黑树节点的定义

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){}
};

四、红黑树的插入(步骤)

1.为什么新插入的节点必须给红色?

(1)新节点给红色,可能出现连续红节点

(2)如果新节点给黑色,必定会违反性质4(其每条路径的黑色节点数量相同

2、插入红色节点后,判定红黑树性质是否被破坏

因为新节点的默认颜色是红色,所以

(1)双亲节点的颜色是黑色,没有违反红黑树任何 性质,则不需要调整;

(2)双亲节点为红色,就会出现连续的红节点,此时需要对红黑树分情况来讨论:见下一部分


五、插入出现连续红节点情况分析+图解(看uncle节点)

约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点

下面的分析都是以p为g的左孩子为例

5.1、uncle存在且为红

cur插入后,p和u变黑,g变红

(1)g没有父亲,g为根,g变黑

(2)g有父亲。其为黑,结束;其为红,后把g当成cur,继续向上调整

5.2、uncle不存在

u不存在,则cur一定是新插入的节点

(如果cur不是新插入的节点,则cur和p一定有一个节点是黑色,否则每条路径黑色节点不相同

下图为解释:

1、单旋

右单旋

2、双旋

 左单旋 + 右单旋 

5.3、uncle存在且为黑

uncle存在且为黑,是情况一变来的,所以cur原来的节点一定是黑色的

现在其是红色的原因是,cur的子树在调整过程中将cur的颜色由黑变红。

1、单旋

右单旋

2、双旋

左单旋 + 右单旋

六、插入总结

1、红黑树插入的两种步骤

1、uncle存在且为红

2、uncle不存在 或者 uncle存在且为黑

通过分析,

uncle不存在的单旋 和 uncle存在且为黑的单旋 可以写在一起,

uncle不存在的双旋 和 uncle存在且为黑的双旋 可以写在一起,

不论uncle存在或者不存在,都不影响此步的单旋或者双旋

当p为g的右孩子时,操作都相反。

详细步骤见其中while (parent && parent->_col == RED)这一步。

 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);cur->_col = RED;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;//p为g左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况1:u存在且为红 if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{//情况2.1 , 3.1if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况2.2 , 3.2{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//p为g右孩子else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

七、红黑树总结及代码

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(logN),红黑树不追求绝对平衡,只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数, 所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。

using namespace std;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>
struct 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);cur->_col = RED;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;//p为g左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况1:u存在且为红 if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{//情况2.1 , 3.1if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况2.2 , 3.2{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//p为g右孩子else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}private:Node* _root = nullptr;public:int _rotateCount = 0;
};

http://www.ds6.com.cn/news/17866.html

相关文章:

  • 做办公家具在哪个网站推销好营销推广的工具有哪些
  • 做房地产公司网站的费用网络营销方法有几种类型
  • 建立网站站点的过程中不正确的是白嫖永久服务器
  • 个人服务器网站备案广告主广告商对接平台
  • 做高端品牌网站建设如何制作网页教程
  • 苏州优化外包北京专门做seo
  • 哔哩哔哩推广网站软文有哪些
  • 旅游网站建设风险分析自助建站系统下载
  • dw主页制作网站排名优化+o+m
  • 国外做内容网站精准广告投放
  • 柳州商城网站开发怎么创建网站链接
  • 做网站推广什么好百度热门排行榜
  • 成都快速做网站互动营销案例分析
  • 建设一个网站app全过程seo优化报价公司
  • 做实验网站网络营销的方法有哪些?举例说明
  • 响应式网站是什么南宁网络推广外包
  • 政府网站建设岗位说明免费注册网址
  • 网站建设的原理厦门网站推广公司哪家好
  • 找人做网站内容自己编辑吗关联词有哪些小学
  • 网站多级导航效果百度有什么办法刷排名
  • 网站ww正能量武汉seo管理
  • 沙市做网站weisword最好的免费信息发布平台
  • 专业企业网站建设报价拼多多怎么查商品排名
  • 南通做网站软件在线看crm系统
  • 自己建网站难吗拉新平台
  • 有域名怎么建网站咖啡的营销推广软文
  • 互联网公司排名2024优化设计电子课本下载
  • 网站开发 公司 深圳电话销售外呼系统软件
  • 哪家公司做企业网站类似58的推广平台有哪些平台
  • 找人做网站排名优化千锋教育培训机构地址