数据结构-----红黑树的插入

目录

前言

红黑树的储存结构

 一、节点旋转操作

左旋（Left Rotation）

右旋（Right Rotation） 

二、插入节点

1.插入的是空树

2.插入节点的key重新重复

3.插入节点的父节点是黑色

4.插入节点的父节点是红色

4.1父节点是祖父节点的左子节点

4.1.1叔叔节点是红色 

 4.1.2叔叔节点是黑色

4.1.2-1 插入节点是作左子节点

4.1.2-2插入节点是作右子节点

 4.2父节点是祖父节点的右子节点

4.2.1叔叔节点是红色

4.2.2 叔叔节点是黑色

4.2.1-1 插入节点是作左子节点

4.2.1-2 插入节点是作右子节点

三、完整代码展示

前言

        上一期我们初步学习了红黑树的基本概念和特性（上一期链接：数据结构-----红黑树简介_Gretel Tade的博客-CSDN博客 如果不了解红黑树相关性质的话建议看看这个），那么从这一期开始，我们就进入到了红黑树的深入学习，首先我通过这一期来详细介绍红黑树的插入操作实现，下面就看看怎么去把数据插入到红黑树吧！

红黑树的储存结构

 根据红黑树的要求，我们可以去定义红黑树节点和树的结构体，如下所示：

//宏定义颜色
#define red 0
#define black 1//数据类型Datatype
typedef char Datatype;
//红黑树节点存储结构
typedef struct node {Datatype data;int color;int key;//排序键值，根据key大小排序struct node* par;//父节点指针struct node* left, * right;//左右子节点指针
}Node;//红黑树的定义rbtree
typedef struct tree {Node* root;//指向根节点指针Node* nil;//叶子节点（哨兵）
}rbtree;

 一、节点旋转操作

在数据结构当中，旋转操作是一种很常见的操作，可能去实现数据结构平衡或者其他相关特性的要求，同样的的AVL树和红黑树里边也是要进行旋转操作的，通过旋转来满足平衡的特性。旋转分两种：左旋（Left Rotation）和右旋（Right Rotation）

左旋（Left Rotation）

左旋是一种将某个节点的右子节点旋转上来的操作。也就是说当前节点的右子节点顶替了自己，然后自己变为右子节点的左子节点，以保持树的平衡。

操作如下：

  1. 将当前节点的右子节点设为新的父节点。
  2. 将新的父节点的左子节点设为当前节点的右子节点。
  3. 如果当前节点有父节点，将新的父节点替代当前节点的位置。
  4. 将当前节点设为新的父节点的左子节点。

 代码实现：

//左旋（以x为旋转点，向左旋转）
void left_rotate(rbtree* T, Node* x) {Node* y = x->right;//标记到右子节点x->right = y->left;//y的左子节点代替x的右子节点if (x->right != T->nil)x->right->par = x;//如果不为空（nil）其父节点指向xy->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了if (x->par == T->nil) {//判断x的父节点是否为根结点T->root = y;//如果是的话，y就变为根结点}else {//y顶替x的位置if (x == x->par->left)x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点elsex->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点}//y的左子节点指向x，x的父节点指向yy->left = x;x->par = y;
}

右旋（Right Rotation） 

同样的右旋也是将左子节点顶替自己成为父节点， 然后自己成为左子节点的右子节点。

操作如下：

  1. 将当前节点的左子节点设为新的父节点
  2. 将新的父节点的右子节点设为当前节点的左子节点
  3. 如果当前节点有父节点，将新的父节点替代当前节点的位置
  4. 将当前节点设为新的父节点的右子节点

 代码实现：

//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {Node* y = x->left;//标记到左子节点yx->left = y->right;//y的右子节点代替x的左子节点if (x->left != T->nil)x->left->par = x;y->par = x->par;//y的父节点指向x的父节点if (x->par == T->nil)T->root = y;//如果x是根结点的话，那么y代替x成为根结点else {if (x == x->par->left)x->par->left = y;elsex->par->right = y;}//y的右子节点指向x，x的父节点为yy->right = x;x->par = y;
}

二、插入节点

再讲之前，我分享一个网址给大家（链接：Red/Black Tree Visualization），这个是一个红黑树模拟器的网址，你们可以去进行红黑树插入删除遍历等操作，可以自己试试看。如下图所示：

 废话不多说了，上正文！

红黑树的插入操作分两步走：

  • 找到插入位置
  • 进行自平衡调整

 注意：插入节点初始为红色

原因分析：因为红黑树中任意一个节点到叶子节点路径所含黑色节点数量相同，也就是说如果我插入的节点为黑色的话，那么就会破坏红黑树的要求，所以插入的节点必须是红色节点，才能保证红黑树的性质。

下面就开始讨论红黑树的几种插入情况：

1.插入的是空树

这是最简单的插入情况，当插入第一个节点的时候，红黑树为空我们只需要让根节点指向这个节点即可。操作如下：

  1. 根节点指向此节点
  2. 把根节点染黑

2.插入节点的key重新重复

这种情况的话我们可以根据自己喜好去处理，如果出现了重复的key，那么就把这个key里面的值进行更新；或者我们不进行插入操作，因为key不可以重复，直接退出插入操作。

3.插入节点的父节点是黑色

这很好处理，直接插入就行了，因为父节点为黑色，插入节点为红色，所以不会影响红黑树的平衡性。

  1. 直接插入即可

4.插入节点的父节点是红色

这种情况是最为复杂的，由于父节点颜色是红色，所以要进行平衡调整，所以要去进一步的讨论才行。那具体根据什么去调整呢？是看叔叔节点的颜色来调整（父节点的兄弟节点），具体分以下几种情况：

 大的有两种情况，要看父节点是祖父节点的左边还是右边，下面我就以父节点为左子节点为例子：

 下文图标说明：

t 表示插入的节点

P表示父节点

B表示叔叔节点

PP表示祖父节点

4.1父节点是祖父节点的左子节点
4.1.1叔叔节点是红色 

如果叔叔节点的颜色是红色的话，这里不需要进行旋转操作，只需要让父节点和叔叔节点颜色变为黑色，祖父节点颜色变为红色即可。流程如下：

  • 把P 和B 节点染黑
  • 把PP节点染红

 4.1.2叔叔节点是黑色

这里的话又要去分两种情况：

  1. 插入节点是父节点的左子节点
  2. 插入节点是父节点的右子节点
4.1.2-1 插入节点是作左子节点

 如果插入的节点是父节点的左子节点的话，那么要进行以下操作：

  • 把P染黑
  • 把PP染红
  • 对PP进行右旋

4.1.2-2插入节点是作右子节点

 如果插入节点是作为父节点的右子节点的话，要进行以下操作：

  • 对P进行左旋
  • 把t 染黑
  • 把PP染红
  • 对PP进行右旋

 4.2父节点是祖父节点的右子节点

这里的操作跟4.1基本上是一模一样的，只是对称过去是了，但是我还是想详细列出来吧，下面接着看。

4.2.1叔叔节点是红色

操作步骤如下：

  • 把B（叔叔节点）和P（父节点）然黑
  • 把PP（祖父节点）染红

4.2.2 叔叔节点是黑色

同样的也是分以下两种情况讨论： 

4.2.1-1 插入节点是作左子节点
  •  对P 进行右旋
  • 将t 染黑
  • 将PP 然红
  • 对PP 进行左旋

4.2.1-2 插入节点是作右子节点
  •  将P 染黑
  • 将PP 然红
  • 对PP进行左旋

 以上这些就是红黑树的插入全部可能了，是不是很多啊，其实还好啦！只要我们把这些情况一个一个分类，然后思路捋一捋很容易弄明白的，后面讲到红黑树的删除还有更多种情况呢！还有就是，这些图片是我自己画的，呃画得不太好，不好意思哈。

三、完整代码展示

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>//宏定义颜色
#define red 0
#define black 1//数据类型Datatype
typedef char Datatype;
//红黑树节点存储结构
typedef struct node {Datatype data;int color;int key;struct node* par;//父节点指针struct node* left, * right;//左右子节点指针
}Node;//红黑树的定义rbtree
typedef struct tree {Node* root;//指向根节点指针Node* nil;//叶子节点（哨兵）
}rbtree;//创建初始化红黑树
rbtree* Create_inittree() {rbtree* T = (rbtree*)malloc(sizeof(rbtree));assert(T);T->nil = (Node*)malloc(sizeof(Node));assert(T->nil);//T->nil是不储存数据的节点，作为空节点代替NULL，也就是哨兵节点（表示空）T->nil->color = black;T->nil->par = NULL;T->nil->left = T->nil->right = NULL;T->root = T->nil;return T;
}//创建一个节点
Node* Create_node(rbtree*T ,Datatype data, int key) {Node* new_node = (Node*)malloc(sizeof(Node));assert(new_node);new_node->data = data;new_node->color = red;//初始化颜色红色//左右父节点为nil哨兵节点new_node->left=new_node->right = T->nil;new_node->par = T->nil;new_node->key = key;return new_node;
}//左旋（以x为旋转点，向左旋转）
void left_rotate(rbtree* T, Node* x) {Node* y = x->right;//标记到右子节点x->right = y->left;//y的左子节点代替x的右子节点if (x->right != T->nil)x->right->par = x;//如果不为空（nil）其父节点指向xy->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了if (x->par == T->nil) {//判断x的父节点是否为根结点T->root = y;//如果是的话，y就变为根结点}else {//y顶替x的位置if (x == x->par->left)x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点elsex->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点}//y的左子节点指向x，x的父节点指向yy->left = x;x->par = y;
}
//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {Node* y = x->left;//标记到左子节点yx->left = y->right;//y的右子节点代替x的左子节点if (x->left != T->nil)x->left->par = x;y->par = x->par;//y的父节点指向x的父节点if (x->par == T->nil)T->root = y;//如果x是根结点的话，那么y代替x成为根结点else {if (x == x->par->left)x->par->left = y;elsex->par->right = y;}//y的右子节点指向x，x的父节点为yy->right = x;x->par = y;
}//插入后平衡调整
void Insert_adjust(rbtree* T, Node* t) {//如果父节点的颜色是红色那就进行调整操作了if (t->par->color == red) {Node* p = t->par;Node* pp = p->par;//01 p节点是pp左子节点if (p == pp->left) {Node* uncle = pp->right;//01-1 叔叔节点颜色是红色if (uncle->color == red) {p->color = black;uncle->color = black;pp->color = red;t = pp;}//01-2 叔叔节点颜色是黑色else {//01-2-1 插入节点t是p的左子节点if (t == p->left) {p->color = black;pp->color = red;right_rotate(T, pp);t = p;}//01-2-2 插入节点t是p的右子节点else if(t==p->right){left_rotate(T, p);t->color = black;pp->color = red;right_rotate(T, pp);}}}//02 p节点是pp的右子节点else {		Node* uncle = pp->left;//02-1 叔叔节点颜色是红色if (uncle->color == red) {pp->color = red;p->color = black;uncle->color = black;t = pp;}//02-2 叔叔节点颜色是黑色else {//02-2-1 插入节点t是p的右子节点if (t == p->right) {p->color = black;pp->color = red;left_rotate(T,pp);t = p;}//02-2-2 插入节点t是p的左子节点else {right_rotate(T, p);t->color = black;pp->color = red;left_rotate(T, pp);}}}}//根节点标记黑色T->root->color = black;
}//插入节点
void Insert_node(rbtree* T, Datatype data,int key) {assert(T);Node* t = Create_node(T ,data, key);Node* root = T->root;//快指针Node* cur=T->nil;//慢指针//1.如果根节点为空if (T->root==T->nil) {T->root = t;//根结点指向新创建的节点}else {while (root != T->nil) {cur = root;//cur标记为root的上一个节点（父节点）if (t->key > root->key)root = root->right;else if (t->key < root->key)root = root->left;//如果出现插入重复的key值，就退出，不进行插入操作else {printf("Don't insert the same key!\n");free(t);t = NULL;return;}}}//判断插入的位置if (key < cur->key)cur->left = t;//小的话就插入左边elsecur->right = t;//大的话就插入右边t->par = cur;//新插入的父节点指针指向curInsert_adjust(T, t);//平衡调整
}

 单单值考虑插入操作就有两百多行代码，后面还有删除操作，查找操作，总共的话大概400行代码，这里就先发今天所讲的插入操作内容的代码，注释很详细，慢慢看哈，我相信你一点看得懂的！

以上就是本期的全部内容了，我们下一期讲红黑树的删除操作，下次见！

分享一张壁纸： 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/160559.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

软考-网络安全体系与网络安全模型

软考-网络安全体系与网络安全模型

本文为作者学习文章&#xff0c;按作者习惯写成&#xff0c;如有错误或需要追加内容请留言&#xff08;不喜勿喷&#xff09; 本文为追加文章&#xff0c;后期慢慢追加 by 2023年10月 网络安全体系相关安全模型 BLP机密性模型 BLP&#xff08;Biba-格雷泽-麦克拉伦&#x…
阅读更多...
嵌入式平台的电源总结

嵌入式平台的电源总结

本文引注: https://mp.weixin.qq.com/s/PuSxHDFbJjjHEReukLSvyg 1.AC的定义 Alternating Current&#xff08;交流&#xff09;的首字母缩写。AC是大小和极性&#xff08;方向&#xff09;随时间呈周期性变化的电流。电流极性在1秒内的变化次数被称为频率&#xff0c;以Hz为单位…
阅读更多...
Sql Server 数据库中的所有已定义的唯一约束 （列名称 合并过了）

Sql Server 数据库中的所有已定义的唯一约束 （列名称 合并过了）

查询Sql Server Database中的唯一约束 with UniqueBasic as (SELECTtab.name AS TableName, -- 表名称idx.name AS UniqueName, -- 唯一约束的名称col.name AS UniqueFieldName -- 唯一约束的表字段FROMsys.indexes idxJOIN sys.index_columns idxColON (idx.object_id idxCo…
阅读更多...
【分享Python代码】图片转化为素描画

【分享Python代码】图片转化为素描画

哈喽&#xff0c;大家好&#xff0c;我是木易巷~ 代码生成效果图 原图&#xff1a; 生成图&#xff1a; 原图&#xff1a; 生成图&#xff1a; 准备工作 Python编程首先需要安装环境&#xff0c;下面是详细步骤&#xff1a; 会的小伙伴可自行跳过&#xff0c;代码在最后 1…
阅读更多...
spring boot RabbitMq基础教程

spring boot RabbitMq基础教程

RabbitMq 由于RabbitMQ采用了AMQP协议&#xff0c;因此它具备跨语言的特性。任何语言只要遵循AMQP协议收发消息&#xff0c;都可以与RabbitMQ交互。并且RabbitMQ官方也提供了各种不同语言的客户端。 但是&#xff0c;RabbitMQ官方提供的Java客户端编码相对复杂&#xff0c;一般…
阅读更多...
idea使用Spring Initializer创建springboot项目的坑【保姆级教学】

idea使用Spring Initializer创建springboot项目的坑【保姆级教学】

项目场景&#xff1a; 提示&#xff1a;这里先简述项目创建后遇到的问题和解决方案&#xff1a; idea 使用 Spring Initializer 创建springboot项目后&#xff0c; 有以下问题&#xff1a; ① 右键没有Run ② 右键New新建文件发现无Java Class选项 然后解决掉 ①② 问题后出…
阅读更多...
总结：JavaEE的Servlet中HttpServletRequest请求对象调用各种API方法结果示例

总结：JavaEE的Servlet中HttpServletRequest请求对象调用各种API方法结果示例

总结&#xff1a;JavaEE的Servlet中HttpServletRequest请求对象调用各种API方法结果示例 一方法调用顺序是按照英文字母顺序从A-Z二该示例可以用作servlet中request的API参考&#xff0c;从而知道该如何获取哪些路径参数等等三Servlet的API版本5.0.0、JSP的API版本&#xff1a;…
阅读更多...
WordPress 常规设置页面调用媒体中心上传图片插入URL（新版可用）

WordPress 常规设置页面调用媒体中心上传图片插入URL（新版可用）

首先&#xff0c;我们需要在主题或插件文件夹中创建一个 JavaScript 文件&#xff08;如&#xff1a;media-uploader.js&#xff09;&#xff0c;该文件中包含如下代码。 /*** 媒体中心上传 js **/ jQuery(document).ready(function($){var mediaUploader;$(#upload_image_but…
阅读更多...
软件工程与计算总结（十七）软件构造

软件工程与计算总结（十七）软件构造

一.概述 1.定义 软件构造是以编程为主的活动&#xff0c;类似于软件实现。但软件构造又不止编程这么简单&#xff0c;除了核心的编程任务之外&#xff0c;还设计详细设计&#xff08;数据结构与算法设计&#xff09;、单元测试、集成与集成测试以及其他活动~ 2.软件构造是设计…
阅读更多...
多维时序 | MATLAB实现SSA-CNN-LSTM-Attention多变量时间序列预测（SE注意力机制）

多维时序 | MATLAB实现SSA-CNN-LSTM-Attention多变量时间序列预测（SE注意力机制）

多维时序 | MATLAB实现SSA-CNN-LSTM-Attention多变量时间序列预测&#xff08;SE注意力机制&#xff09; 目录 多维时序 | MATLAB实现SSA-CNN-LSTM-Attention多变量时间序列预测&#xff08;SE注意力机制&#xff09;预测效果基本描述模型描述程序设计参考资料 预测效果 基本描…
阅读更多...
【vim 学习系列文章 10 -- vim 将代码中空格高亮显示方法】

【vim 学习系列文章 10 -- vim 将代码中空格高亮显示方法】

文章目录 vim 高亮空格使用背景如何配置vim 可以自动显示空格呢&#xff1f;vim highlight 命令使用介绍vim 空白行的处理vim match 命令详细介绍 vim 高亮空格使用背景 开发人员在编写代码之后&#xff0c;在review通过之后会将代码推到服务器然后merge&#xff0c;但是有些代…
阅读更多...
uni-app--》基于小程序开发的电商平台项目实战（五）

uni-app--》基于小程序开发的电商平台项目实战（五）

&#x1f3cd;️作者简介&#xff1a;大家好&#xff0c;我是亦世凡华、渴望知识储备自己的一名在校大学生 &#x1f6f5;个人主页&#xff1a;亦世凡华、 &#x1f6fa;系列专栏&#xff1a;uni-app &#x1f6b2;座右铭&#xff1a;人生亦可燃烧&#xff0c;亦可腐败&#xf…
阅读更多...
【C语言进阶】自定义类型：结构体，枚举，联合

【C语言进阶】自定义类型：结构体，枚举，联合

自定义类型&#xff1a;结构体&#xff0c;枚举&#xff0c;联合 1.结构体1.1结构体类的基础知识1.2结构的声明1.3特殊的声明1.4结构的自引用1.5结构体变量的定义和初始化1.6结构体内存对齐1.7修改默认对齐1.8结构体传参 2.段位2.1什么是段位2.2段位的内存分配2.3位段的跨平台问…
阅读更多...
【Spring Boot】RabbitMQ消息队列 — RabbitMQ入门

【Spring Boot】RabbitMQ消息队列 — RabbitMQ入门

💠一名热衷于分享知识的程序员 💠乐于在CSDN上与广大开发者交流学习。 💠希望通过每一次学习，让更多读者了解我 💠也希望能结识更多志同道合的朋友。 💠将继续努力，不断提升自己的专业技能，创造更多价值。🌿欢迎来到@"衍生星球"的CSDN博文🌿 🍁本…
阅读更多...
Chrome使用本地修改过的js替换原js内容

Chrome使用本地修改过的js替换原js内容

步骤 1.进入开发人员工具&#xff1a;按F12 或 按ctrlshitfi 或 菜单“更多工具”->“开发人员工具” 2.在“源代码/来源”页面找到需要更改的js文件&#xff0c;“右键”->“替换内容” 3.在弹出的标签点击“选择文件夹”来选择一个存放内容的本地文件夹 4.弹出的询问标…
阅读更多...
Excel——对其他工作表和工作簿的引用

Excel——对其他工作表和工作簿的引用

一、引用其他sheet页表区域 若希望在公式中引用其他工作表的单元格区域&#xff0c;可以在公式编辑状态下&#xff0c;通过鼠标单击相应的工作表标签&#xff0c;然后选择相应的单元格区域。 例1 跨sheet页引用其他工作表区域 如图1所示的工作表Sheet2为工资表。 在Sheet1表…
阅读更多...
【Golang】grpc环境踩的坑

【Golang】grpc环境踩的坑

关于’protoc-gen-go’ 不是内部或外部命令 这个问题的出现是因为没有这个文件导致的 这个文件要通过我们下载的google.golang.org这个文件编译生成的 这里建议下载google提供的grpc包 protobuf的源码&#xff1a; git clone https://github.com/golang/protobuf 下载好之后进…
阅读更多...
如何把视频压缩变小？

如何把视频压缩变小？

如何把视频压缩变小&#xff1f;大家都知道&#xff0c;视频一般都伴随着很大的文件体积&#xff0c;&#xff1a;尤其是现在的视频大多是高清晰度的&#xff0c;因此视频文件的体积就更加的大&#xff0c;视频体积太大会给我们带来很多的不便&#xff0c;主要是以下这几点&…
阅读更多...
诚迈科技董事长王继平出席中国（太原）人工智能大会并发表演讲

诚迈科技董事长王继平出席中国（太原）人工智能大会并发表演讲

10月14日—15日&#xff0c;2023中国&#xff08;太原&#xff09;人工智能大会在山西省太原市举办。诚迈科技在大会上全面展示了其在人工智能领域的一系列创新技术与解决方案&#xff0c;诚迈科技董事长、统信软件董事长王继平受邀出席产业数字化转型论坛并发表主题演讲&#…
阅读更多...
【特纳斯电子】基于单片机的火灾监测报警系统-实物设计

【特纳斯电子】基于单片机的火灾监测报警系统-实物设计

视频及资料链接&#xff1a;基于单片机的火灾监测报警系统-实物设计 - 电子校园网 (mcude.com) 编号&#xff1a; T0152203M-SW 设计简介&#xff1a; 本设计是基于单片机的火灾监测报警系统&#xff0c;主要实现以下功能&#xff1a; 1.通过OLED显示温度、烟雾、是否有火…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023