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

江苏省教育网站官网东莞网站制作外包

news 2025/7/29 6:07:44
江苏省教育网站官网,东莞网站制作外包,邢台营销型网站制作,wordpress 主题logo目录 一、概念 二、红黑树的性质 三、红黑树的定义 四、红黑树的插入操作 情况一（叔叔节点存在且为红色）——变色向上调整： 情况二（叔叔节点不存在或为黑色）——旋转变色： 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.dinnco.com/news/77110.html

相关文章：

  • 公司网站要怎么做上海网站制作推广
  • 有美元进账去外管局网站做啥营销培训课程视频
  • 邯郸网站设计价格免费网站建设哪个好
  • 宿州公司做网站湖北seo服务
  • 如何做影视网站的标题招代理最好的推广方式
  • 傻瓜式网站制作搜索引擎优化的主要手段
  • 成功案例 网站广州搜发网络科技有限公司
  • 重庆网站建设重庆网站制作国家免费培训学校
  • 南宁西乡塘区网站建设现在推广用什么平台
  • 8080端口做网站销售平台排名
  • 网站制作关键字排名优化系统软件
  • 设计软件ai长沙seo智优营家
  • dreamweaver网站建设和维护上海网站seo诊断
  • 龙岗网站设计讯息网站排名优化工具
  • 南通做网站的公司seo云优化如何
  • 国内做性视频网站有哪些优化设计答案六年级上册语文
  • 灌南网站建设淘宝关键词排名
  • 可以做哪些网站有哪些软文写作公司
  • 网站建设加盟合作bt磁力搜索器
  • 企业内部网站如何建设一键注册所有网站
  • html5做网站心得体会湖南平台网站建设设计
  • 中山市做网站公司站内优化包括哪些
  • 做网站什么主题比较好软件推广平台有哪些?哪个比较好
  • 网站内容的实现方式推广运营是什么工作
  • 市场部职能中的网站建设拼多多seo搜索优化
  • 鹰潭做网站公司济南百度seo
  • wordpress能导出网站吗线上推广网络公司
  • 做logo图标的网站怎么做电商生意
  • 怎么通过贷款网站找做贷款客户昆明seo网站建设
  • 长春市建设厅网站代发关键词排名包收录