红黑树

devtools/2024/11/16 5:49:29/

  

目录

  红黑树

红黑树的概念

红黑树的性质

红黑树节点的定义

插入的代码实现

情况一

情况二

uncle不存在

uncle存在且为黑单旋

情况三

uncle存在且为黑的双旋情况

情况二和情况三的总代码 

以上是父亲在爷爷左边的情况,右边的情况也类似

左旋代码

右旋代码

红黑树的验证

总代码

红黑树

红黑树的概念

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

红黑树的性质

(路径是从根到空节点,上图是11个节点)                 不是红黑树

(最长路径：一黑一红相间的路径  最短：全黑路径)

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

2. 根节点是黑色的 

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的(任何路径没有连续的红色节点)

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

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

红黑树节点的定义

//枚举
//节点颜色
enum Colour
{RED,BLACK
};
//红黑树节点的定义
template<class K,class  V>
struct RBTreeNode
{RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;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){}
};

插入的代码实现

检测新节点插入后，红黑树的性质是否造到破坏

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

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

情况一

cur为红，p为红，g为黑，u存在且为红

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。 

举个例子：

 

//第一种情况父亲在爷爷的左边
if (parent == grandfather->_left)
{//定义叔叔节点，父亲在左，叔叔节点则在右Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色，父亲和叔叔都变黑，爷爷变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理，因为有可能爷爷是子树节点，爷爷的父亲节点可能也是红色cur = grandfather;parent = cur->_parent;}
}

情况二

cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，

p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

举个例子

uncle不存在

	//uncle不存在，且插入的在父亲的左边if (cur == parent->_left){//     g//   p// c//右旋RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//cur在父亲右边时，需要双旋else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;
}

还有可能父亲在爷爷的右边

uncle存在且为黑单旋

(变色后，parent不能直接变黑，因为变黑后每个路径的黑节点不同了)

图上情况，插入后先变色，uncle为红色，然后再向上处理，发现uncle为黑色就需要旋转了，旋转后就不用调整了

情况三

uncle存在且为黑的双旋情况

cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，

p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

则转换成了情况2

//这种情况也是uncle为黑时，且需要旋转的，上面的是单旋的情况，这个是双旋的情况

情况二和情况三的总代码 

else // u不存在 或 存在且为黑
{//uncle不存在，且插入的在父亲的左边if (cur == parent->_left){//     g//   p// c//右旋RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//cur在父亲右边时，需要双旋else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;
}

以上是父亲在爷爷左边的情况,右边的情况也类似

	//父亲在爷爷右边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;}}
}

左旋代码

void RotateL(Node* parent)
{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)
{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;}
}

红黑树的验证

红黑树的检测分为两步：

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

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

红黑树的删除

红黑树 - _Never_ - 博客园

红黑树与AVL树的比较

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

总代码

RBTree.h
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
//枚举
//节点颜色
enum Colour
{RED,BLACK
};
//红黑树节点的定义
template<class K,class  V>
struct RBTreeNode
{RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;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 (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//连接上父子关系cur->_parent = parent;//parent存在且为红色时需要进行变色旋转，因为黑色的时候就不用做处理了while (parent && parent->_col == RED){//定义一下爷爷节点Node* grandfather = parent->_parent;//第一种情况父亲在爷爷的左边if (parent == grandfather->_left){//定义叔叔节点，父亲在左，叔叔节点则在右Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色，父亲和叔叔都变黑，爷爷变红parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理，因为有可能爷爷是子树节点，爷爷的父亲节点可能也是红色cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{//uncle不存在，且插入的在父亲的左边if (cur == parent->_left){//     g//   p// c//右旋RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}//cur在父亲右边时，需要双旋else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//父亲在爷爷右边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.ppmy.cn/devtools/134355.html

相关文章

探索 HTML 和 CSS 实现的模拟时钟

探索 HTML 和 CSS 实现的模拟时钟

效果演示 这段代码是一个模拟时钟的 HTML 和 CSS 代码。它创建了一个简单的数字时钟界面&#xff0c;包括时针、分针和秒针。 HTML <div class"face"><p class"v-index">II</p><p class"h-index">II</p><d…
阅读更多...
Linux手动安装nginx

Linux手动安装nginx

本次以安装nginx-1.12.2为例 1、首先说明一下&#xff0c;安装nginx之前需要安装如下素材&#xff1a; 2、开始安装 第一步&#xff0c;安装依赖 yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel第二步&#xff0c;下载并安装nginx安装包&#xff08;n…
阅读更多...
将大型语言模型（如GPT-4）微调用于文本续写任务

将大型语言模型（如GPT-4）微调用于文本续写任务

要将大型语言模型&#xff08;如GPT-4&#xff09;微调用于文本续写任务&#xff0c;构造高质量的训练数据至关重要。以下是如何构造训练数据的详细步骤&#xff1a; 1. 数据收集&#xff1a; 多样性&#xff1a; 收集多种类型的文本&#xff0c;包括小说、新闻、论文、博客等…
阅读更多...
移动应用开发：实现简易调查问卷

移动应用开发：实现简易调查问卷

文章目录 前言一&#xff0c;创建SurveyActivity活动二&#xff0c;设计UI三&#xff0c;创建字符串资源文件四&#xff0c;编写活动代码五&#xff0c;更新 AndroidManifest.xml六&#xff0c;运行测试 前言 在Android Studio中开发一个调查问卷界面思路解析&#xff1a; 创建…
阅读更多...
C#中break和continue的区别？

C#中break和continue的区别？

在C#编程语言中&#xff0c;break和continue是两个用于控制循环流程的关键字&#xff0c;但它们的作用和用途有所不同。 break关键字 break关键字用于立即终止它所在的最内层循环或switch语句&#xff0c;并跳出该循环或switch块。程序执行将继续进行循环或switch语句之后的下一…
阅读更多...
深入理解ElasticSearch分词器：详解各种分词器的原理与应用

深入理解ElasticSearch分词器：详解各种分词器的原理与应用

目录 什么是分词器ElasticSearch中的分词器种类标准分词器&#xff08;Standard Analyzer&#xff09;简单分词器&#xff08;Simple Analyzer&#xff09;空格分词器&#xff08;Whitespace Analyzer&#xff09;语言分词器&#xff08;Language Analyzers&#xff09;拼音分…
阅读更多...
wordcloud库基本介绍

wordcloud库基本介绍

文章目录 wordcloud库概述wordcloud库的安装 wordcloud库使用说明配置对象参数 wordcloud应用实例实例: 政府工作报告词云 wordcloud库概述 wordcloud是优秀的词云展示第三方库 词云以词语为基本单位,更加直观和艺术地展示文本 wordcloud库的安装 (cmd命令行) pip install …
阅读更多...
使用Git工具在GitHub的仓库中上传文件夹(超详细）

使用Git工具在GitHub的仓库中上传文件夹(超详细）

如何使用Git工具在GitHub的仓库中上传文件夹&#xff1f; 如果觉得博主写的还可以&#xff0c;点赞收藏关注噢~ 第一步&#xff1a;拥有一个本地的仓库 可以fork别人的仓库或者自己新创建 fork别人的仓库 或者自己创建一个仓库 按照要求填写完成后&#xff0c;点击按钮创建…
阅读更多...
最新文章

Copyright @ 2022~2023