营销型网站建设哪家公司好,莘县网站开发,做网站的流程方法,词条有哪些网站可以做目录
前言
红黑树的储存结构 一、节点旋转操作
左旋#xff08;Left Rotation#xff09;
右旋#xff08;Right Rotation#xff09;
二、插入节点
1.插入的是空树
2.插入节点的key重新重复
3.插入节点的父节点是黑色
4.插入节点的父节点是红色
4.1父节点是祖父…目录
前言
红黑树的储存结构 一、节点旋转操作
左旋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
左旋是一种将某个节点的右子节点旋转上来的操作。也就是说当前节点的右子节点顶替了自己然后自己变为右子节点的左子节点以保持树的平衡。 操作如下 将当前节点的右子节点设为新的父节点。将新的父节点的左子节点设为当前节点的右子节点。如果当前节点有父节点将新的父节点替代当前节点的位置。将当前节点设为新的父节点的左子节点。 代码实现
//左旋以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的左子节点指向xx的父节点指向yy-left x;x-par y;
}
右旋Right Rotation
同样的右旋也是将左子节点顶替自己成为父节点 然后自己成为左子节点的右子节点。 操作如下 将当前节点的左子节点设为新的父节点将新的父节点的右子节点设为当前节点的左子节点如果当前节点有父节点将新的父节点替代当前节点的位置将当前节点设为新的父节点的右子节点 代码实现
//右旋以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的右子节点指向xx的父节点为yy-right x;x-par y;
}
二、插入节点 再讲之前我分享一个网址给大家链接Red/Black Tree Visualization这个是一个红黑树模拟器的网址你们可以去进行红黑树插入删除遍历等操作可以自己试试看。如下图所示 废话不多说了上正文
红黑树的插入操作分两步走
找到插入位置进行自平衡调整 注意插入节点初始为红色 原因分析因为红黑树中任意一个节点到叶子节点路径所含黑色节点数量相同也就是说如果我插入的节点为黑色的话那么就会破坏红黑树的要求所以插入的节点必须是红色节点才能保证红黑树的性质。 下面就开始讨论红黑树的几种插入情况
1.插入的是空树
这是最简单的插入情况当插入第一个节点的时候红黑树为空我们只需要让根节点指向这个节点即可。操作如下 根节点指向此节点把根节点染黑 2.插入节点的key重新重复
这种情况的话我们可以根据自己喜好去处理如果出现了重复的key那么就把这个key里面的值进行更新或者我们不进行插入操作因为key不可以重复直接退出插入操作。
3.插入节点的父节点是黑色
这很好处理直接插入就行了因为父节点为黑色插入节点为红色所以不会影响红黑树的平衡性。 直接插入即可 4.插入节点的父节点是红色
这种情况是最为复杂的由于父节点颜色是红色所以要进行平衡调整所以要去进一步的讨论才行。那具体根据什么去调整呢是看叔叔节点的颜色来调整父节点的兄弟节点具体分以下几种情况 大的有两种情况要看父节点是祖父节点的左边还是右边下面我就以父节点为左子节点为例子 下文图标说明 t 表示插入的节点 P表示父节点 B表示叔叔节点 PP表示祖父节点 4.1父节点是祖父节点的左子节点
4.1.1叔叔节点是红色 如果叔叔节点的颜色是红色的话这里不需要进行旋转操作只需要让父节点和叔叔节点颜色变为黑色祖父节点颜色变为红色即可。流程如下 把P 和B 节点染黑把PP节点染红 4.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进行左旋 以上这些就是红黑树的插入全部可能了是不是很多啊其实还好啦只要我们把这些情况一个一个分类然后思路捋一捋很容易弄明白的后面讲到红黑树的删除还有更多种情况呢还有就是这些图片是我自己画的呃画得不太好不好意思哈。 三、完整代码展示
#includestdio.h
#includestdlib.h
#includestring.h
#includeassert.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-leftnew_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的左子节点指向xx的父节点指向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的右子节点指向xx的父节点为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(tp-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* curT-nil;//慢指针//1.如果根节点为空if (T-rootT-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(Dont 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行代码这里就先发今天所讲的插入操作内容的代码注释很详细慢慢看哈我相信你一点看得懂的
以上就是本期的全部内容了我们下一期讲红黑树的删除操作下次见
分享一张壁纸
