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

网站开发 财务自由wordpress怎么验证谷歌

news 2025/9/17 6:25:59
网站开发 财务自由,wordpress怎么验证谷歌,宣城seo,为朋友做的网站目录 一、概念 二、红黑树的性质 三、红黑树的定义 四、红黑树的插入操作 情况一（叔叔节点存在且为红色）——变色向上调整： 情况二（叔叔节点不存在或为黑色）——旋转变色： 2.1叔叔节点不存在 2.2叔叔…

目录

一、概念

二、红黑树的性质

三、红黑树的定义

四、红黑树的插入操作

情况一（叔叔节点存在且为红色）——变色+向上调整：

情况二（叔叔节点不存在或为黑色）——旋转+变色：

2.1叔叔节点不存在

2.2叔叔节点为黑色

插入的代码实现：

五、红黑树的验证

六、红黑树完整代码

一、概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

二、红黑树的性质

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

三、红黑树的定义

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_kv(kv),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响{}pair<K, V> _kv;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _parent;Colour _col;
};

C++STL中的set和map底层就是使用红黑树实现的，而map是存放键值对的，所以我们给红黑树的节点中的值存放一个键值对，以及左右孩子的指针和指向父节点的指针，还有一个存放颜色的标记。

四、红黑树的插入操作

红黑树的插入首先和普通二叉搜索树的插入操作一样，新建一个节点，左节点的值小于根，右节点的值大于根，找到位置进行插入。插入后应如果破坏了红黑树的性质，就需要进行调整。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：

我们给出一个约定：cur为当前节点，p为父亲节点，g为祖父节点，u为叔叔节点

情况一（叔叔节点存在且为红色）——变色+向上调整：

将p和u改成黑色，将g改为红色

此时有三种情况：

1、g没有父亲节点，直接变成黑色就可以，插入结束；

2、g有父亲节点，且父亲为黑色，插入结束；

3、g有父亲节点，且父亲为红色（违反了红色节点不能连续的性质），需要向上调整。

情况二（叔叔节点不存在或为黑色）——旋转+变色：

2.1叔叔节点不存在

如果cur在parent的左边——右旋：

cur在parent的右边——先左旋再右旋：

2.2叔叔节点为黑色

如果cur在parent的左边——右旋：

cur在parent的右边——先左旋再右旋：

以上插入操作是p在g节点左边的情况，p在g节点右边的情况与以上插入过程类似，仅仅是镜像翻转一下。

插入的代码实现：

左旋代码：

void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;cur->_left = parent;if (curleft)curleft->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

右旋代码：

void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;cur->_right = parent;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

插入代码：

    bool insert(const pair<K, V>& kv){//如果root为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//插入Node* cur = _root;Node* parent = cur;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 (grandfather->_left == parent){Node* uncle = grandfather->_right;//叔叔存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在或者为黑色——旋转+变色else{//右单旋即可if (parent->_left == cur){RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//先左单旋，后右单旋else{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}//叔叔在左else{Node* uncle = grandfather->_left;//uncle存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//uncle不存在或为黑色——旋转+变色else{//左单旋即可if (parent->_right == cur){RotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}//先右单旋，再左单旋else{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

五、红黑树的验证

    bool isBalance(){return _isBalance(_root);}bool checkcolour(Node* root, int benckmark, int blackcount){if (root == nullptr){if (blackcount != benckmark)return false;return true;}if (root->_col == RED && root->_parent && root->_parent->_col == RED)return false;if (root->_col == BLACK)++benckmark;return checkcolour(root->_left, benckmark, blackcount)&& checkcolour(root->_right, benckmark, blackcount);}bool _isBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;Node* cur = root;//求树中最左路径黑色节点的个数while (cur){if (cur->_col == BLACK)++blackcount;cur = cur->_left;}return checkcolour(_root, 0, blackcount);}

六、红黑树完整代码

#pragma once#include <iostream>
#include <vector>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_kv(kv),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响{}pair<K, V> _kv;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _parent;Colour _col;
};
/*
* 红黑树插入思路——关键在于uncle节点：
* 分为两大类：
* 一、如果uncle存在且为红色——仅仅变色即可
* 
*	       g(黑)                            g(红)     
*     p(红)     u(红)    ------->       p(黑)      u(黑) ------->继续向上更新
*  c(红)                            c(红)
* 
* 
* 二、如果uncle不存在或为黑色——旋转加变色
* 
* 情况一：       g(黑)                              p(红)
*            p(红)    NULL/黑  ------->       c(红)       g(黑)
*         c(红)
* 
*        仅仅右旋即可，g变成红色; p变成黑色;  break;
* 
* 情况二：       g(黑)                                  g(黑)                c(红)
*			 p(红)    NULL/黑  ------->   先左旋     c(红)    ------->   p(红)    g(黑) 
*               c(红)                             p(红)
* 
*        c变成黑色，g变成红色，break;
* 
* 情况三：情况一的对称图形
* 情况四：情况二的对称图形
* 
*/
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}void InOrder(){cout << "InOrder: ";_InOrder(_root);cout << endl;}bool insert(const pair<K, V>& kv){//如果root为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//插入Node* cur = _root;Node* parent = cur;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 (grandfather->_left == parent){Node* uncle = grandfather->_right;//叔叔存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//叔叔不存在或者为黑色——旋转+变色else{//右单旋即可if (parent->_left == cur){RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//先左单旋，后右单旋else{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}//叔叔在左else{Node* uncle = grandfather->_left;//uncle存在且为红色——变色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}//uncle不存在或为黑色——旋转+变色else{//左单旋即可if (parent->_right == cur){RotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}//先右单旋，再左单旋else{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}bool isBalance(){return _isBalance(_root);}private:bool checkcolour(Node* root, int benckmark, int blackcount){if (root == nullptr){if (blackcount != benckmark)return false;return true;}if (root->_col == RED && root->_parent && root->_parent->_col == RED)return false;if (root->_col == BLACK)++benckmark;return checkcolour(root->_left, benckmark, blackcount)&& checkcolour(root->_right, benckmark, blackcount);}bool _isBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;Node* cur = root;while (cur){if (cur->_col == BLACK)++blackcount;cur = cur->_left;}return checkcolour(_root, 0, blackcount);}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;cur->_left = parent;if (curleft)curleft->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;cur->_right = parent;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}
private:Node* _root;int blackcount = 0;
};

测试：

运行结果：

之后更新红黑树的应用，用红黑树封装map和set。

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

相关文章：

  • 做可以上传文件的网站单页网站排名
  • 什么是自建站长春城市设施建设集团股份公司
  • 高端网站设计有哪些app界面设计总结
  • 荆州网站建设荆州网站发产品ps怎么做产品图
  • 塑胶制品塘厦东莞网站建设把自己做的网站进行app封包
  • 铁盒 东莞网站建设官方网站建设公司排名
  • 网站搭建维护淄博怎么和客户推广说网站建设语
  • 移动建站是什么意思企业做网站需要多少钱
  • 企业网站关站外贸人才网
  • 新开传奇网站发布网孞谷歌seo是什么意思
  • wordpress套cf速度怎么样新站整站排名优化火速公司
  • 上传网站上海微网站设计
  • 北京网站制作费用美团网站开发
  • 网站的修改灌南住房建设局网站
  • 织梦做的网站怎么加弹窗许昌小学网站建设
  • 百度怎么做开锁网站江苏建设厅网站
  • 响应式购物网站设计怎么做网站可以注册的
  • 建设行业个人信息网站西安中风险地区
  • 游戏平台网站的建设规划全国最大的网站建设公司排名
  • 网站开发摊销期多少年wordpress主题仪表盘
  • 建设银行网站 无法访问网站建设 服饰鞋帽
  • 教育类集群网站建设北京网站开发建设
  • thinkphp 网站模版成都网页制作培训
  • 科技设计网站有哪些内容阿里云买了域名怎么建网站
  • 深圳推广公司网站建设书模板合肥响应式网站设计
  • 网站建设优惠一个做炉石视频的网站
  • 网站搜索功能设计centos安装wordpress
  • 上海网站建设网络公司无锡装修公司做网站
  • 论坛网站开发成本vps搭建网站教程
  • 网站数据库 权限设计网页设计 做网站的代码