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

做网站要怎么备案友情链接查询结果

news 2025/7/7 5:12:22
做网站要怎么备案,友情链接查询结果,网站建设的服务和质量,呼伦贝尔哪里做网站前言：本篇文章我们继续来分享C中的另一个复杂数据结构——红黑树。 目录 一.红黑树概念 二.红黑树性质 三.红黑树实现 1.基本框架 2.插入 3.判断平衡 四.完整代码 总结 一.红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个…

前言：本篇文章我们继续来分享C++中的另一个复杂数据结构——红黑树。

目录

一.红黑树概念

二.红黑树性质

三.红黑树实现

1.基本框架

2.插入

3.判断平衡

 四.完整代码

总结

一.红黑树概念

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

二.红黑树性质

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

  2. 根节点是黑色的

  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（不存在连续的红色节点） 

  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路径都存在相同数量的黑色节点） 

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

如何理解红黑树最长路径不超过最短路径的二倍呢？？？

  1.  从性质能够看出，红黑树每一条路径上，都有相同数量的黑色节点。
  2. 红黑树每条路径上可以存在连续的黑色节点，但不能存在连续的红色节点。
  3. 所以最短路径即为全是黑色节点的路径。
  4. 最长路径则为一黑一红相间的路径。

三.红黑树实现

1.基本框架

红黑树与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){}
};
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;size_t _size = 0;
};

同时我们多创建一个_size成员变量，用于记录节点数量。 

2.插入

红黑树插入的基本步骤与二叉搜索树和AVL树一样，都是按照左子节点比根节点小，右子节点比根节点大的规则，唯一不同的是，红黑树的插入要考虑其性质。其中最值得注意的性质为：

  1. 不存在连续的红节点
  2. 每条路径上的黑节点数相等

 其中能够看出，第二条才是最关键的，因此我们每次新插入节点时，必须插入红节点。

此时我们会面临两种情况：

  1. 父节点为黑色，插入即结束，无需调整。
  2. 父节点为红色，不满足上述性质1，需要调整。

下面我们来看特殊情况：

父亲为红节点，那么只有将父节点变为黑色节点，才能够满足性质。

但是如果父亲变为黑节点，就说明该路径上同样多出一个黑节点，而唯一的处理手段，就是让父亲的父亲，也就是爷爷节点，变为红色节点。

此时又存在问题，那就是关于父亲的兄弟节点，也就是叔叔节点，那么叔叔节点存在三种情况：

  1. 叔叔节点同样为红色。
  2. 叔叔节点不存在。
  3. 叔叔节点为黑色。

如果叔叔节点为红色，为了满足各路径黑节点数量相同，叔叔节点则需要和父节点一起变为黑色。

如果叔叔节点不存在，为了满足性质，需要将该子树从爷爷节点的位置进行旋转。

如果叔叔节点为黑色，而父节点为红色，如果还要满足性质，说明子节点原本应为黑色，是因为经过了上述的调整而作为爷爷节点变成了红色。此时我们仍需从爷爷节点的位置进行旋转。

分析完上述完整情况之后，还有关于新插入节点的两种情况：

  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);cur->_col = RED;//新增节点给红色if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = 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 = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;//继续往上处理cur = Grandfather;parent = Grandfather->_parent;}else//叔叔不存在或叔叔存在但为黑{if (cur == parent->_left)//左边直接右旋{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;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = Grandfather->_parent;}else{if (cur == parent->_right){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;}

 需要考虑的情况确实很多，但如果自己画图认真分析，理解起来还是易如反掌的。

3.判断平衡

判断红黑树的平衡，我们自然要从其性质入手：

  1. 首先就是判断根节点是否为黑色。
  2. 其次容易判断的是是否有两个相邻的红色节点，注意这里我们不去判断一个节点与其子节点，反而去判断一个节点与其父节点。因为如果判断子节点，则可能需要判断两次，而父节点则只需判断一次。
  3. 最后就是判断所有路径上的黑节点数量是否相同。

其中前两种都比较容易想到代码方式，最重要的是如何比较黑节点的数量。

我们可以通过增加参数的方式。来记录到达每个节点位置时，该路径上出现过的黑节点的数量。而如何进行比较，因为每条路径上黑节点的数量都必须相同，所以我们直接记录一下最左边的一条路径上黑节点的数量，然后求出一条路径上的黑节点数之后，就进行比较即可。

	//判断平衡bool IsBalance(){if (_root->_col == RED)return false;int refnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refnum++;cur = cur->_left;}return Check(_root, 0, refnum);}bool Check(Node* root, int BlackNum,const int refnum){if (root == nullptr){if (refnum != BlackNum){cout << "存在黑色节点个数不相等" << endl;return false;}cout << BlackNum << endl;return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "->存在连续的红色节点" << endl;return false;}if (root->_col == BLACK)BlackNum++;return Check(root->_left, BlackNum,refnum)&& Check(root->_right, BlackNum,refnum);}

 四.完整代码

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);cur->_col = RED;//新增节点给红色if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = 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 = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;//继续往上处理cur = Grandfather;parent = Grandfather->_parent;}else//叔叔不存在或叔叔存在但为黑{if (cur == parent->_left)//左边直接右旋{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;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = Grandfather->_parent;}else{if (cur == parent->_right){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;}//右单旋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;_root->_parent = nullptr;}else//不是根节点，调整父节点指向{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}//左单旋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;_root->_parent = nullptr;}else//不是根节点，调整父节点指向{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}}//遍历void InOrder(){inOrder(_root);cout << endl;}void inOrder(const Node* root){if (root == nullptr){return;}inOrder(root->_left);cout << root->_kv.first << ':' << root->_kv.second << endl;inOrder(root->_right);}//判断平衡bool IsBalance(){if (_root->_col == RED)return false;int refnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refnum++;cur = cur->_left;}return Check(_root, 0, refnum);}bool Check(Node* root, int BlackNum,const int refnum){if (root == nullptr){if (refnum != BlackNum){cout << "存在黑色节点个数不相等" << endl;return false;}cout << BlackNum << endl;return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "->存在连续的红色节点" << endl;return false;}if (root->_col == BLACK)BlackNum++;return Check(root->_left, BlackNum,refnum)&& Check(root->_right, BlackNum,refnum);}
private:Node* _root = nullptr;//size_t _size = 0;
};

总结

关于红黑树的知识就分享这么多，喜欢本篇文章记得一键三连，我们下期再见！

http://www.khdw.cn/news/15348.html

相关文章：

  • 展示型的网站开发价格站长之家点击进入
  • 招聘网站可以同时做两份简历吗网络营销策划创意案例点评
  • 旅游电子商务网站的建设网上怎么发布广告
  • 自家房子做民宿的网站seo发帖软件
  • 网站上资源截图怎么做关键词优化如何
  • 网站使用了seo优化工具怎么检测厦门seo推广
  • 中国做网站的公司排名手机系统优化工具
  • 石家庄网站建设wsjzseo营销是什么
  • wordpress编辑网站注册域名费用一般多少钱
  • 厦门网站建设百度网盘下载安装
  • 营销型网站建设是什么意思杭州seo教程
  • wordpress 怎么安装ssl海南seo代理加盟供应商
  • 软件工程师英文今日头条搜索优化怎么做
  • 网站做优化的必要性腾讯广告投放平台官网
  • 太原建站模板网站seo的工作内容主要包括
  • 有哪些企业会找人做网站建设谷歌搜索引擎seo
  • 网页建站分为几个类型长沙seo技术培训
  • 外网网站电脑培训班零基础网课
  • 自动建站网站系统域名百度关键词代做排名
  • 程序员用的编程软件网页优化方法
  • 旅行网站开发背景推广一般收多少钱
  • 东莞莞城网站建设凌哥seo
  • 短租网站那家做的好处百度商家怎么入驻
  • 找做废薄膜网站全网热搜榜
  • 江西企业网站建设价格中国企业培训网
  • 新做的网站怎样让百度收录百度推广关键词怎么设置好
  • 西安注册公司流程长沙 建站优化
  • 环保类网站建设搜索引擎优化简称
  • 系统下载网站源码seo刷排名公司
  • 邯郸网站建设在哪里软文代写文案