实现红黑树

目录

红黑树的概念

红黑树的节点结构定义

红黑树的插入

红黑树的验证

实现红黑树完整代码

红黑树的概念

红黑树 ，是一种 二叉搜索树 ，但 在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或
Black 。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍 ，因而是 接近平衡 的。
注意：可以认为AVL树是严格平衡的，而红黑树是近似平衡的
而上述所说的 对任何一条从根到叶子的路径上各个结点着色方式的限制具体如下:
1. 每个结点不是红色就是黑色
2. 根节点是黑色的 
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的(不存在连续的红色节点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 
5. 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点 )

有了上述限制，最短路径就是只包含黑色节点的路径，而最长路径就是黑红交替，所以所有路径长度范围都在[最短路径，最短路径的2倍]这个区间之间， 保证了红黑树近似平衡

红黑树的节点结构定义

//颜色定义成枚举类型
enum Color
{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;//颜色变量Color _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

红黑树的插入

插入新节点我们选择插入红色节点，理由如下:

1.插入黑色节点，一定破坏性质4，所有路径的黑色节点个数都要变化

2.插入红色节点，可能破坏性质3，插入红色节点的父亲是黑色节点，没有破坏性质3, 不需要调整；插入红色节点的父亲是红色节点，破坏了性质3， 需要进行调整

综合考虑，插入红色节点的代价相比插入黑色节点小很多，因此我们选择插入红色节点

插入情况的分类:

上面已经提到，插入红色节点的父亲是黑色节点，没有破坏性质3，因此无需调整，因此下面只讨论插入红色节点的父亲是红色节点的情况

处理方法总体分两类

1.插入节点的叔叔节点存在且为红色 --- 变色即可

字母含义: cur --- 插入节点， p --- cur的父亲节点,  g --- cur的爷爷节点, u --- cur的叔叔节点

ps: g一定存在，因为p是红色节点, 不可能为根节点, 而g也一定是黑色节点，因为如果是红色节点，说明在cur插入之前红黑树就已经出问题了！

插入之后cur和p都是红色，因为不能出现连续红色节点，我们选择把p变黑，而p变黑之后，g-p-cur的这条路径多了一个黑色节点，因此我们又把g变红，g变红之后，g-u的这条路径又少了一个黑色节点，由于叔叔节点存在且为红色，因此我们又把u变黑即可

ps:变色完之后，发现g变成了红色，而上图的树可能只是一颗子树，因此g变红之后，接着:

1.如果g是根，把g变黑，因为红黑树要求根节点是黑色

2.如果g不是根，g必然有父亲，继续判断g的父亲节点的颜色，如果g的父节点是黑色，停止处理（因为没有再违反红黑树规则了）；如果g的父节点是红色，此时又出现了连续的红节点，需要继续处理, 把cur更新到g的位置，继续循环处理!

2.插入节点的叔叔节不存在 或者 存在且为黑色 --- 旋转 + 变色

这种情况下，单纯的变色已经解决不了问题了！需要 旋转+变色 来处理

具体采用哪种旋转方法，在前面的博客 实现AVL树-CSDN博客 已经讲解过了

注意:无论是哪种旋转+变色方式，发现最终当前子树的根节点都变成了黑色，此时无论cur的父节点是黑色还是红色都不违反红黑树的规则，因此旋转+变色完成之后，直接break跳出循环即可！

右单旋 + 变色 (p是g的左，cur是p的左)

左右双旋 + 变色 (p是g的左，cur是p的右)

 左单旋 + 变色 (p是g的右，cur是p的右)

右左双旋 + 变色 (p是g的右，cur是p的左)

红黑树旋转代码(除了不需要调平衡因子，其他代码与AVL树一样)：

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}//左右双旋void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}//右左双旋void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}

红黑树插入代码：

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);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED) //父亲不存在或者父亲为黑色就不需要继续调整了!{Node* grandfather = parent->_parent;if (grandfather->_left == parent) //父亲是爷爷的左孩子{Node* uncle = grandfather->_right;//1.插入节点的叔叔存在且为红色 --- 父亲和叔叔变黑，爷爷变红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//调整完之后，更新cur, 判断是否还需要调整cur = grandfather;parent = cur->_parent;}//2.uncle不存在 / uncle为黑色 --- 旋转 + 变色else{if (cur == parent->_left) //单纯左边高{RotateR(grandfather); //右单旋//变色parent->_col = BLACK;grandfather->_col = RED;}else //cur是parent的右边{RotateLR(grandfather); //左右双旋//变色cur->_col = BLACK;grandfather->_col = RED;}break; //旋转+变色完之后, 该子树的根变成了黑色，无需继续调整}}else //父亲是爷爷的右孩子{Node* uncle = grandfather->_left;//1.插入节点的叔叔存在且为红色 --- 父亲和叔叔变黑，爷爷变红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//调整完之后，更新cur, 判断是否还需要调整cur = grandfather;parent = cur->_parent;}//2.uncle不存在 / uncle为黑色 --- 旋转 + 变色else{if (cur == parent->_left) //cur是parent的左边，进行右单旋{RotateRL(grandfather); //右左单旋//变色cur->_col = BLACK;grandfather->_col = RED;}else //cur是parent的右边{RotateL(grandfather); //左单旋//变色grandfather->_col = RED;parent->_col = BLACK;}break; //旋转+变色完之后, 该子树的根变成了黑色，无需继续调整}}}_root->_col = BLACK;return true;
}

红黑树的验证

判断是否是红黑树

	bool IsRBTree(){if (_root == nullptr) return true;if (_root->_col == RED){cout << "根节点为红色" << endl;return false;}//以最左路径的黑节点的个数作为参考值Node* cur = _root;int BlackCount = 0;while (cur){if (cur->_col == BLACK)BlackCount++;cur = cur->_left;}//调用子函数判断红黑树int count = 0;return _IsRBTree(_root, count, BlackCount);}
private:bool _IsRBTree(Node* root, int count, int BlackCount){if (root == nullptr){if (count != BlackCount) {cout << "黑色节点的个数不相等" << endl;return false;}return true;}//判断节点的孩子节点颜色不好判断, 转化成判断父亲节点颜色if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红节点" << endl;return false;}if (root->_col == BLACK)count++;//递归子问题return _IsRBTree(root->_left, count, BlackCount)&& _IsRBTree(root->_right, count, BlackCount);}

验证红黑树 

#include "RBTree.h"#include <vector>
void test1()
{int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.IsRBTree();cout << t.IsRBTree() << endl;
}void test2()
{const int N = 30;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());cout << v.back() << endl;}RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));cout << "Insert:" << e << "->" << t.IsRBTree() << endl;}cout << t.IsRBTree() << endl;
}int main()
{//test1();test2();return 0;
}

实现红黑树完整代码

#pragma once#include <iostream>
using namespace std;//颜色定义成枚举类型
enum Color
{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;//颜色变量Color _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);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED) //父亲不存在或者父亲为黑色就不需要继续调整了!{Node* grandfather = parent->_parent;if (grandfather->_left == parent) //父亲是爷爷的左孩子{Node* uncle = grandfather->_right;//1.插入节点的叔叔存在且为红色 --- 父亲和叔叔变黑，爷爷变红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//调整完之后，更新cur, 判断是否还需要调整cur = grandfather;parent = cur->_parent;}//2.uncle不存在 / uncle为黑色 --- 旋转 + 变色else{if (cur == parent->_left) //单纯左边高{RotateR(grandfather); //右单旋//变色parent->_col = BLACK;grandfather->_col = RED;}else //cur是parent的右边{RotateLR(grandfather); //左右双旋//变色cur->_col = BLACK;grandfather->_col = RED;}break; //旋转+变色完之后, 该子树的根变成了黑色，无需继续调整}}else //父亲是爷爷的右孩子{Node* uncle = grandfather->_left;//1.插入节点的叔叔存在且为红色 --- 父亲和叔叔变黑，爷爷变红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//调整完之后，更新cur, 判断是否还需要调整cur = grandfather;parent = cur->_parent;}//2.uncle不存在 / uncle为黑色 --- 旋转 + 变色else{if (cur == parent->_left) //cur是parent的左边，进行右单旋{RotateRL(grandfather); //右左单旋//变色cur->_col = BLACK;grandfather->_col = RED;}else //cur是parent的右边{RotateL(grandfather); //左单旋//变色grandfather->_col = RED;parent->_col = BLACK;}break; //旋转+变色完之后, 该子树的根变成了黑色，无需继续调整}}}_root->_col = BLACK;return true;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}//左右双旋void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}//右左双旋void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}//判断是否是红黑树bool IsRBTree(){if (_root == nullptr) return true;if (_root->_col == RED){cout << "根节点为红色" << endl;return false;}//以最左路径的黑节点的个数作为参考值Node* cur = _root;int BlackCount = 0;while (cur){if (cur->_col == BLACK)BlackCount++;cur = cur->_left;}//调用子函数判断红黑树int count = 0;return _IsRBTree(_root, count, BlackCount);}
private:bool _IsRBTree(Node* root, int count, int BlackCount){if (root == nullptr){if (count != BlackCount) {cout << "黑色节点的个数不相等" << endl;return false;}return true;}//判断节点的孩子节点颜色不好判断, 转化成判断父亲节点颜色if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红节点" << endl;return false;}if (root->_col == BLACK)count++;//递归子问题return _IsRBTree(root->_left, count, BlackCount)&& _IsRBTree(root->_right, count, BlackCount);}private:Node* _root = nullptr;
};

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

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

相关文章

Leetcode39.组合总和

Leetcode39.组合总和

文章目录 题目描述解题思路重复子集剪枝 代码 题目 参考题解 题目描述 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返…
阅读更多...
【JavaSE】/*初识Java*/

【JavaSE】/*初识Java*/

目录 一、了解 Java 语言 二、Java 语言的重要性 2.1 使用程度 2.2 工作领域 三、Java 语言的特性 四、Java 的基础语法 五、可能遇到的错误 六、第一个 java 程序代码解析 七、Java 注释 八、Java 标识符 九、Java 关键字 一、了解 Java 语言 Java 是由 Sun Micr…
阅读更多...
图论（洛谷刷题）

图论（洛谷刷题）

目录 前言&#xff1a; 题单&#xff1a; P3386 【模板】二分图最大匹配 P1525 [NOIP2010 提高组] 关押罪犯 P3385 【模板】负环 P3371 【模板】单源最短路径&#xff08;弱化版&#xff09; SPFA写法 Dij写法&#xff1a; P3385 【模板】负环 P5960 【模板】差分约束…
阅读更多...
【iOS开发】—— 初识锁

【iOS开发】—— 初识锁

【iOS开发】—— 初识锁 线程安全锁的种类自旋锁定义原理自旋锁缺点OSSpinLock&#xff08;自旋锁&#xff09; 互斥锁os_unfair_lockpthread_mutexNSLockNSRecusiveLockSemaphore信号量synchronized 总结两种之间的区别和联系&#xff1a; 线程安全 当一个线程访问数据的时候…
阅读更多...
双向冒泡法，可以只求最大最小值

双向冒泡法，可以只求最大最小值

int BiBubbleSort(int Arr[],int n,int maxnum){int left0,rightn-1;int i;bool notDone true;int temp;if(n<2)return -1;while(left<right&&notDone){ notDone false; //设置未发生交换标志 for(ileft;i<right;i){if(Arr[i]>Arr[i1]){//swap(Arr[…
阅读更多...
Python-VBA函数之旅-staticmethod函数

Python-VBA函数之旅-staticmethod函数

目录 一、staticmethod函数的常见应用场景 二、staticmethod函数使用注意事项 三、如何用好staticmethod函数&#xff1f; 1、staticmethod函数&#xff1a; 1-1、Python&#xff1a; 1-2、VBA&#xff1a; 2、推荐阅读&#xff1a; 个人主页&#xff1a; https://blog…
阅读更多...
HackMyVM-VivifyTech

HackMyVM-VivifyTech

目录 信息收集 arp nmap nikto whatweb WEB web信息收集 wpscan feroxbuster hydra 提权 系统信息收集 横向渗透 git提权 get root 信息收集 arp ┌──(root㉿0x00)-[~/HackMyVM] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 08:00:27:9d:6d:7b, …
阅读更多...
【密评】 | 商用密码应用安全性评估从业人员考核题库（9/58）

【密评】 | 商用密码应用安全性评估从业人员考核题库（9/58）

Hill密码是重要古典密码之一&#xff0c;其加密的核心思想的是&#xff08;&#xff09;。 A.线性变换 B.非线性变换 C.循环移位 D.移位 著名的Kerckhoff原则是指&#xff08;&#xff09;。 A.系统的保密性不但依赖于对加密体制或算法的保密&#xff0c;而且依赖于密钥 B.系统…
阅读更多...
即插即用篇 | YOLOv8 引入 Strip Pooling | 重新思考场景解析的空间池化

即插即用篇 | YOLOv8 引入 Strip Pooling | 重新思考场景解析的空间池化

本改进已集成到 YOLOv8-Magic 框架。 空间池化已被证明在捕获像素级预测任务的长距离上下文信息方面非常有效，如场景解析。在本文中，我们超越了通常具有N N规则形状的常规空间池化，重新思考空间池化的构成，引入了一种新的池化策略，称为条带池化，它考虑了一个长而窄的核，…
阅读更多...
C++ 中的 lambda 表达式

C++ 中的 lambda 表达式

1.概念 lambda表达式实际上是一个匿名类的成员函数&#xff0c;该类由编译器为lambda创建&#xff0c;该函数被隐式地定义为内联。因此&#xff0c;调用lambda表达式相当于直接调用匿名类的operator()函数&#xff0c;这个函数可以被编译器内联优化&#xff08;建议&#xff0…
阅读更多...
C++的数据结构(二）

C++的数据结构(二）

一、链表的基本概念 链表&#xff08;Linked List&#xff09;是一种物理存储单元上非连续的、非顺序的线性数据结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点&#xff08;链表中每一个元素称为节点&#xff09;组成&#xff0c;节点…
阅读更多...
py黑帽子学习笔记_网络编程工具

py黑帽子学习笔记_网络编程工具

tcp客户端 socket.AF_INET表示使用标准IPV4地址和主机名 SOCK_STREAM表示这是一个TCP客户端 udp客户端 udp无需连接&#xff0c;因此不需要client.connect这种代码 socket.SOCK_DGRAM是udp的 tcp服务端 server.listen(5)表示设置最大连接数为5 发现kill server后端口仍占用…
阅读更多...
牛客NC404 最接近的K个元素【中等 二分查找+双指针 Java/Go/PHP】

牛客NC404 最接近的K个元素【中等 二分查找+双指针 Java/Go/PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/b4d7edc45759453e9bc8ab71f0888e0f 知识点 二分查找&#xff1b;找到第一个大于等于x的数的位置idx;然后从idx开始往两边扩展Java代码 import java.util.*;public class Solution {/*** 代码中的类名、方法名、…
阅读更多...
Shell编程规范与变量

Shell编程规范与变量

Shell 什么是Shell&#xff1f; 就是与内核沟通的界面、应用程序等等。比如你要播放音乐&#xff0c;你的计算机通过你在Shell输入的打开音乐的命令&#xff0c;Shell在告诉操作系统的内核用户希望打开音乐&#xff0c;内核在通过cpu调度、内存管理、磁盘输入输出等工作&#…
阅读更多...
JAVA课程设计

JAVA课程设计

一&#xff1a;Java连接mysql数据库 1.1点击进入mysql jar包下载官网 MySQL :: MySQL Community Downloads 将下载好的压缩包进行解压 解压之后下图就是连接数据库所用到的jar包&#xff1a; 将jar包复制到IDEA所用的项目下&#xff0c;放置jar包的目录为lib&#xff0c;需要…
阅读更多...
NSS刷题

NSS刷题

[SWPUCTF 2021 新生赛]jicao 类型&#xff1a;PHP、代码审计、RCE 主要知识点&#xff1a;json_decode()函数 json_decode()&#xff1a;对JSON字符串解码&#xff0c;转换为php变量 用法&#xff1a; <?php $json {"ctf":"web","question"…
阅读更多...
安装Nox夜神模拟器关闭了HyperV后Docker运行不了怎么办？

安装Nox夜神模拟器关闭了HyperV后Docker运行不了怎么办？

1.背景 为了模拟真机&#xff0c;尝试安装了Nox夜神模拟器&#xff0c; 安装过程要求关闭Hyper-V。当时只是在程序安装卸载中关闭了系统服务。以为到时勾选上就好了。操作路径&#xff1a;控制面板\所有控制面板项\程序和功能\启用或关闭Windows功能\Hyper-V。 后来卸载掉了夜神…
阅读更多...
FreeRTOS的列表和列表项 list.c文件详解

FreeRTOS的列表和列表项 list.c文件详解

列表、列表项的定义以及初始化 列表相当于链表&#xff0c;列表项相当于节点&#xff0c;FreeRTOS中的列表相当于一个双向环形链表。 列表使用指针指向列表项。一个列表&#xff08;list&#xff09;下面可能有很多个列表项&#xff08;list item&#xff09;&#xff0c;每个…
阅读更多...
vivado仿真readmemb函数相对路径

vivado仿真readmemb函数相对路径

目前常用的vivado工程的结构如下所示 prj-name|-xxx|-prj.sim|-sim_1|-behav|-modelsim|-tb_prj.do|-xsim|-prj.srcs|-sim_1|-new|-tb_prj.v|-tb_prj_mem.txt一般来说我们创建的testbench文件和新建的txt文件都会放在srcs->sim_1->new这个路径下面&#xff0c;但是我们在…
阅读更多...
【PHP【实战版】系统性学习】——登录注册页面的教程，让编写PHP注册变成一个简单的事情

【PHP【实战版】系统性学习】——登录注册页面的教程，让编写PHP注册变成一个简单的事情

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023