红黑树(数据结构篇)

2024-06-20 14:12
文章标签 数据结构 红黑树

本文主要是介绍红黑树(数据结构篇)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构之红黑树

红黑树(RB-tree)

概念：

  • 红黑树是AVL树的变种，它是每一个节点或者着成红色，或者着成黑色的一棵二叉查找树。
  • 对红黑树的操作在最坏情形下花费O(logN)时间，它的插入操作使用的是非递归形式实现
  • 红黑树的高度最多是2log(N+1)

特性：

  • 红黑树是具有着色性质的二叉查找树，也就意味着树的节点值是有序的，且每个节点只可能是红色或者黑色
  • 红黑树的根是黑色的
  • 如果一个节点是红色的，那么它的子节点必须是黑色的
  • 从一个节点到一个空指针的每一条路径必须包含相同数目的黑色节点

自顶向下插入操作：

  1. 如果使用自底向上插入的话还需要进行逐步递归是他们保证满足红黑树特性，效率就降低了。

  2. 令X为新插入节点(在下面的第三操作中为当前节点)，P为X的父节点，G为P的父节点(也就是X的祖父节点)，GP为G的父节点(也就是P的祖父节点，X的曾祖父节点)

  3. 因为红黑树是一颗二叉查找树，因此在插入时需要查找要插入的值的正确位置，在这个查找路径中，如果遇到节点(X)为黑色而子节点全部为红色，我们就进行翻转操作，也就是将该节点(X)着成红色，子节点全部着成黑色。翻转后:

    如果翻转后发现P和X节点都是红色就需要根据树的结构进行旋转操作

    1. 如果X，P，G形成"一字形"，则对P的父节点G(也就是X的祖父节点)与P进行单旋转，并将新根也就是P着成黑色，新根的子节点都着成红色。
    2. 如果X，P，G形成"之字形"，则对G与X节点进行双旋转，并将新根着成黑色(也就是X节点)，然后将新根的子节点着成红色

  4. 如果该节点(X)是黑色则继续将X下降，直到找到红色节点继续翻转，或者找到指定插入位置，找到指定位置也就是当前节点位置X就进行插入，新节点也是红色，需要重新判断其父节点是否为红色，为红色又需要进行翻转操作来调整。

自顶向下删除操作

  1. 自顶向下删除也需要保证红黑树的性质，插入是插入一片红色的叶子节点，那么反过来我们删除一个红色叶子节点就不会破坏红黑树性质，自顶向下插入的翻转操作是将红色节点减少，并将红色节点上浮，因为删除是插入的逆过程，因此删除的翻转操作就是要将树中的红色节点增多，并将红色节点下沉，这样我们删除红色叶子节点的概率更大，并且不会破坏红黑树性质

  2. 删除操作一共有5种情况需要解决

    1. 要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色
    2. s的两个儿子都是红色，这样双旋转和单旋转都可以，这里优先选择ps单选转调整，情况1-case4
    3. s的左儿子为红色，需要ps.l双旋转调整(s.l为s的左儿子)，情况2-case1
    4. s的右儿子为红色，需要ps单旋转调整，情况3-case2
    5. s有两个黑色儿子，直接cur,p,s颜色翻转操作调整，情况4-case3
    6. p和cur为黑色，s为红色，需要交换sp节点的颜色，并且sp单旋转调整，情况5-case5
    7. cur为红色，可以继续将cur下降，也就是当前cur指向原本cur的子节点，如果为红色继续下降，如果为黑色就判断是否需要操作

  3. tomove指向要删除节点也就是目标节点，而p指向真正要删除的叶子节点，cur则while循环完后则是指向nil节点，因为将tomove标记完，就进行cur和p就查找tomove右子树的最小值节点进行删除，而while循环终止条件为cur==nil情况，因此p指向真正要删除的节点

  4. 找到tomove和p后，将tomove的data等于p的data，将p删除，因为p为叶子节点，将p的父节点指向nil。

image 情况2-case1

image 情况3-case2

image 情况4-case3

image-20240502001308851 情况1-case4

image 情况5-case5

计算红黑树层数：

  • 需要对log2(树中总共节点数+1)向上取整

代码：

int Height(const int count){return std::ceil(std::log2(count+1));
}

代码实现：

#include <iostream>
#include <queue>
#include <math.h>
#include <limits.h>
using namespace std;typedef enum {red,black} colortype;struct RBNode{int data;RBNode *left,*right,*parent;colortype color;   //颜色RBNode(const int val,RBNode* l,RBNode* r,RBNode* p,colortype c=red):data(val),left(l),right(r),parent(p),color(c){};
};class RBtree{
public:RBtree(){nil=new RBNode(INT_MAX, nullptr, nullptr, nullptr,black);root= nullptr;t=new RBNode(INT_MIN,nil,nil,nil,black);size=0;}~RBtree(){clear();delete t;delete nil;};void insert(const int val);      //插入操作void del(const int val);       //删除操作RBNode* find(const int val);   //查找操作void print();     //打印操作,层序遍历//清空操作void clear(){clear(root);root= nullptr;t->right=nil;size=0;}protected:void overturnred(const int val,RBNode* &cur);    //翻转操作,将当前节点变成红色，子节点变成黑色void overturnblack(int val,RBNode* &cur);   //翻转操作，将当前节点变成黑色，子节点变成红色RBNode* SingleRotatewithleft(RBNode* &k1);RBNode* SingleRotatewithright(RBNode* &k1);RBNode* Rotate(const int val,RBNode* &k1){if(val<k1->data){return k1->left=val<k1->left->data? SingleRotatewithleft(k1->left): SingleRotatewithright(k1->left);}else{return k1->right=val<k1->right->data? SingleRotatewithleft(k1->right): SingleRotatewithright(k1->right);}}void clear(RBNode* &rt);// 计算红黑树层数int Height(int nodeCount) {// 红黑树的层数为 log2(nodeCount+1)return (int)std::ceil(std::log2(nodeCount+1));}
private:RBNode* root;RBNode* nil;   //空节点，color为黑色RBNode* t;  //根标记，用于删除操作的便捷int size;
};RBNode* RBtree::SingleRotatewithleft(RBNode *&k1) {RBNode* k2;k2=k1->left;k1->left=k2->right;k2->right=k1;return k2;
}RBNode* RBtree::SingleRotatewithright(RBNode *&k1) {RBNode* k2;k2=k1->right;k1->right=k2->left;k2->left=k1;return k2;
}//翻转操作
void RBtree::overturnred(const int val,RBNode* &cur) {cur->color=red;cur->left->color=cur->right->color=black;RBNode* p=cur->parent;if(p->color==red){RBNode* g=p->parent;g->color=red;if((val<g->data)!=(val<p->data)){     //双旋转p= Rotate(val,g);}cur= Rotate(val,g->parent);cur->color=black;}root->color=black;
}//插入操作
void RBtree::insert(const int val) {if(root== nullptr){root=new RBNode(val,nil,nil, t,black);t->right=root;size++;return;}RBNode *cur,*p;cur=p=root;while (cur!=nil){p=cur;if(cur->left->color==red&&cur->right->color==red){overturnred(val,cur);}cur=val<p->data?p->left:p->right;}if(cur!=nil){return;}cur=new RBNode(val, nil, nil, p);if(val<p->data){p->left=cur;}else{p->right=cur;}overturnred(val,cur);size++;
}void RBtree::overturnblack(int val, RBNode *&cur) {cur->color=red;RBNode* p=cur->parent;RBNode* s=val<p->data?p->left:p->right;//case4:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的两个儿子都是红色，这样双旋转和单旋转都可以，这里优先选择ps单选转//case2:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的右儿子为红色情况，需要ps单旋转调整if(s->right->color==red){val=s->right->data;}//case1:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的左儿子为红色的情况,需要ps.l双旋转调整else if(s->left->color==red){val=s->left->data;}//case3:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s有两个黑儿子(nil节点也是黑色),直接将颜色翻转即可else{//翻转操作if(s!=nil){s->color=red;}p->color=black;return;}if((val<s->data)!=(val<p->data)){Rotate(val,p);}RBNode* g=p->parent;Rotate(val,g);//将调整完的cur的新祖父也就是s或者s的左儿子变成红色，也就是删除完cur后将颜色调整到之前cur在翻转前的情况g->color=red;g->left->color=g->right->color=black;
}void RBtree::del(const int val) {RBNode* tomove=nil;  //找到删除节点RBNode *g,*p,*s,*cur;g=p=t,s=t->left,cur=root;while (cur!=nil){//翻转颜色if(cur->left->color==black&&cur->right->color==black){overturnblack(val,cur);}else{g=p;p=cur;if(val<p->data){cur=p->left,s=p->right;}else{tomove=cur,cur=p->right,s=p->left;}//case5:此时肯定p和cur都为黑色，因为如果p为红色早就翻转了，s肯定是红色，将s变成黑色，p变为红色，sp单旋转调整if(cur->color==black){s->color=black;p->color=red;//单旋转完，cur新祖父变为s,将s重新更改g= Rotate(val,g);s=val<p->data?p->left:p->right;//调整完该情况就重新检查上述操作continue;}//else，cur一定为红色，则可以直接继续将cur继续下降}g=p;p=cur;if(val<p->data){cur=p->left,s=p->right;}else{tomove=cur,cur=p->right,s=p->left;}}root->color=black;   //保证红黑树性质2不被破坏，也就是根一定为黑色//判断是否找到真正要删除的节点，如果找不到就退出if(tomove==nil&&tomove->data!=val){cout<<"未找到要删除对应值的节点";return;}//tomove是要删除的节点，而p指向的是真正要删除的节点tomove->data=p->data;if(g->left==p) g->left=nil;else g->right=nil;delete p;size--;
}RBNode* RBtree::find(const int val) {if(root!= nullptr){RBNode* cur=root;while (cur!=nil){if(cur->data==val) return cur;cur=val<cur->data?cur->left:cur->right;}if(cur==nil){cout<<"树中没有指定值节点"<<endl;}}return root;
}void RBtree::print() {if(root== nullptr){cout<<"树为空"<<endl;return;}queue<RBNode*>q;q.push(root);int cnt=1;int ans=0;int h= Height(size);while (!q.empty()){if(ans==h+1) break;RBNode* cur=q.front();q.pop();if(cur== nullptr){cout<<"null"<<" ";continue;}q.push(cur->left);q.push(cur->right);if(cur->color==red){cout<<"\033[31m"<<cur->data<<"\033[0m"<<" ";}else if(cur==nil) cout<<"nil"<<" ";else cout<<cur->data<<" ";if(cnt==pow(2,ans)){cout<<endl;cnt=0,ans++;}cnt++;}return;
}void RBtree::clear(RBNode* &rt) {if(rt!=nil){clear(rt->left);clear(rt->right);delete rt;rt=nil;}return;
}int main() {RBtree rBtree;rBtree.insert(30);rBtree.insert(15);rBtree.insert(65);rBtree.insert(10);rBtree.insert(20);rBtree.insert(5);rBtree.insert(60);rBtree.insert(70);rBtree.insert(50);rBtree.insert(64);rBtree.insert(66);rBtree.insert(85);rBtree.insert(40);rBtree.insert(55);rBtree.insert(63);rBtree.insert(80);rBtree.insert(90);rBtree.insert(45);rBtree.del(65);rBtree.del(50);rBtree.del(30);rBtree.print();return 0;
}

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

  • 博客1： codebooks.xyz
  • 博客2：moonfordream.github.io
  • github项目地址：Data-Structure-and-Algorithms

这篇关于红黑树(数据结构篇)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1078356。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2