【C++进阶】红黑树

目录

  • 什么是红黑树？
    • 红黑树
    • 红黑树的性质
  • 定义红黑树
  • 红黑树的操作
    • insert
    • inorder
    • find
    • height
    • size
    • 构造函数
    • 析构函数
    • 赋值拷贝
    • 判断红黑树
  • 全部代码
  • 总结

在这里插入图片描述

什么是红黑树？

红黑树

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，用于保持树的平衡，以确保在最坏情况下基本操作（如插入、删除和查找）的时间复杂度仍为 O(log n)。红黑树的每个节点都包含一个额外的颜色位，即红色或黑色。红黑树通过严格的平衡条件来维持树的平衡。

红黑树的性质

  1. 节点是红色或黑色的：每个节点都有颜色属性，红色或黑色。
  2. 根是黑色的：红黑树的根节点必须是黑色的。
  3. 叶节点（NIL 节点）是黑色的：红黑树中的所有叶节点（这里的叶节点是指为空的 NIL 节点，而不是实际的元素节点）都是黑色的。
  4. 红色节点的子节点必须是黑色的（即红色节点不能有红色子节点，也叫“红黑相间”）：红色节点不能连续连接在一起。
  5. 从任何节点到其每个叶子的所有简单路径都必须包含相同数量的黑色节点：这确保了树的平衡性。

定义红黑树

enum Color
{RED,BLACK,
};
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
template<class K,class V> 
class RBTree
{
public:typedef RBTreeNode<K, V> Node;
private:Node* _root = nullptr;
};

红黑树的操作

insert

红黑树的逻辑是在普通的二叉搜索树上进行实现的，在普通的二叉搜索树中，我们不需要调节平衡，但是在红黑树当中我们需要根据红黑树的性质来调整数的颜色和高度，首先我们来看看第一种情况：
在这里插入图片描述
cur是插入节点，由于红色节点不能连续，所以这里已经破坏了平衡，所以我们应该进行调整颜色，我们不可能插入cur是黑色节点，因为如果插入黑色节点的话代价很大，每条路上都会多出来一个黑色节点，这样很不好维护，所以插入红色节点是代价最小的，插入红色节点之后，破坏了规则，所以p应该变成黑色，由于p这条路多了一个黑色节点，所以u应该也变成黑色节点，由于这棵树有可能是某个子树，这两条路多出来一个黑色节点为了保证黑色节点不多，所以g节点应该也变成红色，这样做完之后继续往上调整，将cur赋值到g节点，继续往上调整颜色。

在这里插入图片描述
这样就算调整完毕了。
第二种情况：当u节点不存在时
在这里插入图片描述
对于这种情况我们先准备调色，首先我们先将p改为黑色节点，然后将g改为红色节点之后，我们会发现，左边这条路多出来一个黑色节点，这样是不行的。
在这里插入图片描述
上面这个是不行的，左边已经多出来了一个黑色节点了，但是右边没有黑色节点，所以这种情况我们应该进行旋转。
对g节点进行右旋：
在这里插入图片描述
进行右旋之后将p改为黑色节点，将g改为红色节点，这样两边都保持平衡了。
在这里插入图片描述
还有一种情况：u存在但是为黑色
在这里插入图片描述

最下面的那个红色节点是插入节点：
这种情况我们先向上调整：
在这里插入图片描述
调整成这样之后，我们就发现，u是黑色节点，不管我们怎么调整，左边都会多出一个黑色节点，所以这里我们应该旋转：
绕着g节点进行旋转之后我们可以发现调整颜色就会平衡：
在这里插入图片描述
还有双旋的情况，双旋的情况，我们只说一种：
在这里插入图片描述
左旋将p和cur的位置交换，然后再对g进行右旋，就可以达到平衡的效果。

左旋接口：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left)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;subL->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subL;else parentParent->_right = subL;subL->_parent = parentParent;}
}

insert的代码：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;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不为空并且parent指向的颜色是红色才进行调整while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;//uncle存在且是红色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树：//右单旋if (cur == parent->_left){RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else{Node* uncle = grandparent->_left;//uncle存在且是红色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树：//右单旋if (cur == parent->_right){RotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

inorder

void InOrder()
{_InOrder(_root);
}
void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ':' << root->_kv.second << endl;_InOrder(root->_right);
}

find

bool Find(const K& k)
{Node* cur = _root;while (cur){if (cur->_kv.first < k) cur = cur->_right;else if (cur->_kv.first > k) cur = cur->_left;else return true;}return false;
}

height

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 max(leftheight, rightheight) + 1;
}

size

int size()
{return _size(_root);
}
int _size(Node* root)
{if (root == nullptr)return 0;int left = _size(root->_left);int right = _size(root->_right);return left + right + 1;
}

构造函数

//默认构造
RBTree() = default;
//拷贝构造
RBTree(const RBTree<K, V>& t)
{_root = Copy(t._root);
}
Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newnode = new Node(root->_kv);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;
}

析构函数

~RBTree()
{Destroy(_root);_root = nullptr;
}
void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}

赋值拷贝

RBTree<K, V>& operator=(RBTree<K, V> t)
{swap(_root, t._root);return *this;
}

判断红黑树

bool IsBalance()
{//空树也是搜索树if (_root == nullptr) return true;//根节点不能为红色if (_root->_col == RED) return false;//参考值int refNum = 0;Node* cur = _root;while (cur){//遇到黑色++if (cur->_col == BLACK) refNum++;cur = cur->_left;}return Check(_root, 0, refNum);
}
bool Check(Node* root, int blackNum, const int refNum)
{//走到空之后就算出一条路径的数量了if (root == nullptr){if (blackNum != refNum){cout << "存在黑色节点不相等的路径" << endl;return false;}return true;}//存在连续的红色节点if (root->_col == RED && root->_parent->_col == RED)return false;if (root->_col == BLACK)blackNum++;return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

全部代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Color
{RED,BLACK,
};
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
template<class K,class V> 
class RBTree
{
public:typedef RBTreeNode<K, V> Node;//默认构造RBTree() = default;//拷贝构造RBTree(const RBTree<K, V>& t){_root = Copy(t._root);}//赋值拷贝RBTree<K, V>& operator=(RBTree<K, V> t){swap(_root, t._root);return *this;}//析构函数~RBTree(){Destroy(_root);_root = nullptr;}//查找bool Find(const K& k){Node* cur = _root;while (cur){if (cur->_kv.first < k) cur = cur->_right;else if (cur->_kv.first > k) cur = cur->_left;else return true;}return false;}//中序遍历void InOrder(){_InOrder(_root);}//插入bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;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不为空并且parent指向的颜色是红色才进行调整while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;//uncle存在且是红色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树：//右单旋if (cur == parent->_left){RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else{Node* uncle = grandparent->_left;//uncle存在且是红色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树：//右单旋if (cur == parent->_right){RotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;}//大小int size(){return _size(_root);}//树的高度int height(){return _height(_root);}
private:int _height(Node* root){if (root == nullptr)return 0;int leftheight = _height(root->_left);int rightheight = _height(root->_right);return max(leftheight, rightheight) + 1;}int _size(Node* root){if (root == nullptr)return 0;int left = _size(root->_left);int right = _size(root->_right);return left + right + 1;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left)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;subL->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subL;else parentParent->_right = subL;subL->_parent = parentParent;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ':' << root->_kv.second << endl;_InOrder(root->_right);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_kv);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;}Node* _root = nullptr;
};

总结

红黑树作为一种自平衡二叉搜索树，通过严格的颜色和旋转规则，保证了在最坏情况下仍能提供高效的查找、插入和删除操作。其特有的平衡机制使得红黑树在实际应用中被广泛采用，尤其在需要频繁增删节点的数据结构中表现出色。掌握红黑树的原理和操作，不仅有助于理解复杂数据结构的实现，也为开发高效算法奠定了坚实基础。希望通过本篇博客，大家能够对红黑树有更加深入的认识，并在实际编程中灵活应用。

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

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

相关文章

lora通信模块工作模式（半双工）

lora通信模块工作模式（半双工）

一&#xff0c;工作模式 1&#xff0c;透明模式 2&#xff0c;定点模式 3&#xff0c;广播模式 测试结果 1&#xff0c;定点模式下两个必须都是定点模式才能通信 2&#xff0c;广播模式可以发送到透明模式 3&#xff0c;定点模式发送不了透明模式
阅读更多...
【Python第三方库】Requests全面解析

【Python第三方库】Requests全面解析

文章目录 安装基本用法测试网站发送GET请求发送POST请求更多请求请求参数请求头其他常用请求属性处理响应响应状态码响应内容 处理超时处理异常 requests 是一个非常流行的 Python HTTP 库&#xff0c;用于发送所有类型的 HTTP 请求。它简洁易用&#xff0c;能够处理复杂的请求…
阅读更多...
数据结构——栈的讲解（超详细）

数据结构——栈的讲解（超详细）

前言&#xff1a; 小编已经在前面讲完了链表和顺序表的内容&#xff0c;下面我们继续乘胜追击&#xff0c;开始另一个数据结构&#xff1a;栈的详解&#xff0c;下面跟上小编的脚步&#xff0c;开启今天的学习之路&#xff01; 目录 1.栈的概念和结构 1.1.栈的概念 1.2.栈的结构…
阅读更多...
Vatee万腾平台：数据智能的创新引擎，引领企业数字化转型新纪元

Vatee万腾平台：数据智能的创新引擎，引领企业数字化转型新纪元

在数字化转型的浪潮中&#xff0c;企业正以前所未有的速度重构着自身的运营模式与核心竞争力。作为这一变革的领航者&#xff0c;Vatee万腾平台凭借其卓越的数据智能能力&#xff0c;正逐步揭开企业数字化转型的新篇章。本文将深入探讨Vatee万腾平台如何以数据为核心&#xff0…
阅读更多...
【多线程基础】进程和线程的区别和联系（重要）

【多线程基础】进程和线程的区别和联系（重要）

Hi~&#xff01;这里是奋斗的明志&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f331;&#x1f331;个人主页&#xff1a;奋斗的明志 &#x1f331;&#x1f331;所属专栏&#xff1a;Java多线程 &#x1f4da;本系列文章为个人…
阅读更多...
【JavaEE】CAS原理

【JavaEE】CAS原理

目录 ​前言 什么是CAS&#xff1f; 如何使用CAS&#xff1f; CAS实现自旋锁 CAS的ABA问题 面试题 1.讲解下你自己理解的CAS机制 2.ABA问题怎么解决&#xff1f; 前言 在多线程中&#xff0c;多个线程同时对一个共享变量进行读写操作&#xff0c;那么就会出现线程安全问…
阅读更多...
01 NoSQL之Redis配置与优化

01 NoSQL之Redis配置与优化

目录 1.1 Redis介绍 1.1.1关系数据库与非关系型数据库 1 . 关系型数据库 2. 非关系型数据库 3.非关系型数据库产生背景 (1) High performance--对数据库高并发读写需求 &#xff08;2) Huge Storage--对海量数据高效存储与访问需求 &#xff08;3) High Scalability …
阅读更多...
gitlab cicd快速入门有哪些方法 gitlabcicd和Jenkins哪个更好用

gitlab cicd快速入门有哪些方法 gitlabcicd和Jenkins哪个更好用

在现代软件开发中&#xff0c;持续集成和持续交付&#xff08;CI/CD&#xff09;已成为必不可少的流程。它们不仅能提高开发效率&#xff0c;还能保证代码的质量和稳定性。在众多CI/CD工具中&#xff0c;GitLab和Jenkins是最为常用的两种。本文将围绕“gitlab ci/cd快速入门有哪…
阅读更多...
vuex properties of undefined (reading ‘getters‘)

vuex properties of undefined (reading ‘getters‘)

前言&#xff1a; 最近打算用vue 写个音乐播放器&#xff0c;在搞 vuex 的时候遇到一个很神奇报错&#xff1b;vuex 姿势练了千百次了&#xff0c;刚开始的时候我一直以为是代码问题&#xff0c;反复检查了带了&#xff0c;依旧报错。 Error in mounted hook: "TypeError:…
阅读更多...
[Android] [解决]Bottom Navigation Views Activity工程带来的fragment顶部空白间距问题

[Android] [解决]Bottom Navigation Views Activity工程带来的fragment顶部空白间距问题

用Android Stuio创建一个Bottom Navigation Views Activity工程&#xff0c; 我们刻意设置一下fragment背景为黑色&#xff0c;会发现&#xff0c;这个fragment离顶部还有一段不小空白距离&#xff0c; 怎么解决呢&#xff1f; 在activity_main.xml里面&#xff0c;删掉这句&a…
阅读更多...
极狐GitLab安全版本：16.10.1、16.9.3、16.8.5

极狐GitLab安全版本：16.10.1、16.9.3、16.8.5

极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门面向中国程序员和企业提供企业级一体化 DevOps 平台&#xff0c;用来帮助用户实现需求管理、源代码托管、CI/CD、安全合规&#xff0c;而且所有的操作都是在一个平台上进行&#xff0c;省事省心省钱。可以一键安装极狐GitL…
阅读更多...
数据结构之线性表（单链表的实现）

数据结构之线性表（单链表的实现）

目录 一、单链表的原理 二、单链表的实现 1.单链表的定义 2.单链表的初始化 3.清空单链表 4.单链表是否为空 5.单链表的长度 6.获取指定位置 i 的元素 7.获取指定元素 e 的位置 8.向链表中插入指定位置的元素 9.向链表中删除指定位置的元素 10.遍历链表中的元素 …
阅读更多...
告别手动操作！KeyMouseGo实现自动化工作流

告别手动操作！KeyMouseGo实现自动化工作流

前言 在这个快节奏的时代&#xff0c;我们每天都在与电脑打交道&#xff0c;重复着那些繁琐而单调的操作&#xff1b;你是否曾想过&#xff0c;能让电脑自己完成这些任务&#xff0c;而你则悠闲地喝着咖啡&#xff0c;享受着生活&#xff1f;今天&#xff0c;就让我们一起揭开一…
阅读更多...
【sdk】- 对接阿里云抠图

【sdk】- 对接阿里云抠图

文档地址&#xff1a;https://help.aliyun.com/zh/viapi/use-cases/general-image-segmentation?spma2c4g.11186623.0.0.3814173cenldIs java对接阿里云的通用分割&#xff0c;将代码原封不动复制进来&#xff0c;执行结果失败&#xff0c;咨询阿里云的人员之后&#xff0c;由…
阅读更多...
优盘数据救援：应对文件与目录损坏的全方位指南

优盘数据救援：应对文件与目录损坏的全方位指南

一、问题剖析&#xff1a;优盘文件或目录损坏的困境 在数字化时代&#xff0c;优盘&#xff08;USB闪存驱动器&#xff09;作为便携、高效的数据存储工具&#xff0c;广泛应用于数据传输、备份与分享。然而&#xff0c;面对频繁的使用与不当操作&#xff0c;优盘中的文件或目录…
阅读更多...
FPGA常见型号

FPGA常见型号

FPGA&#xff08;现场可编程门阵列&#xff09;开发板种类繁多&#xff0c;涵盖了从入门级教育用途到高性能工业应用的广泛领域。以下是一些常见的 FPGA 开发板型号及其特点&#xff1a; 1. Xilinx&#xff08;赛灵思&#xff09;系列 Xilinx 是 FPGA 领域的领导者之一&#…
阅读更多...
Ubuntu22.04安装Docker教程

Ubuntu22.04安装Docker教程

简介 ​ Docker 是一个开源的平台&#xff0c;旨在简化应用开发、交付和运行的过程。通过使用容器技术&#xff0c;Docker 能够让开发人员将应用及其依赖环境一同打包&#xff0c;从而实现快速部署、一致的开发环境和优秀的可移植性。 系统版本 ​ 本文以Ubuntu 22.04.4 LTS…
阅读更多...
【探索Linux】P.46（高级IO —— 五种IO模型简介 | IO重要概念）

【探索Linux】P.46（高级IO —— 五种IO模型简介 | IO重要概念）

阅读导航 引言一、五种IO模型1. 阻塞IO&#xff08;1&#xff09;定义&#xff08;2&#xff09;特点 2. 非阻塞IO&#xff08;1&#xff09;定义&#xff08;2&#xff09;特点 3. IO多路复用&#xff08;1&#xff09;定义&#xff08;2&#xff09;特点 4. 信号驱动IO&#…
阅读更多...
深入探索：【人工智能】、【机器学习】与【深度学习】的全景视觉之旅

深入探索：【人工智能】、【机器学习】与【深度学习】的全景视觉之旅

目录 第一部分&#xff1a;人工智能、机器学习与深度学习概述 1.1 人工智能的概念与发展 代码示例&#xff1a;简单的AI决策系统 1.2 机器学习的定义与分类 代码示例&#xff1a;简单的线性回归模型 1.3 深度学习的基础与应用 代码示例&#xff1a;构建简单的神经网络 …
阅读更多...
【TwinCAT】TwinCAT3 PLC HMI在WIN10系统中的全屏显示及用户管理

【TwinCAT】TwinCAT3 PLC HMI在WIN10系统中的全屏显示及用户管理

在工业自动化领域，TwinCAT3 PLC HMI 是一款强大的可视化工具，它支持多种操作系统，并且能够满足不同控制器的需求。在本文中，我们将详细介绍如何在WIN10系统中进行全屏显示设置以及如何进行用户管理配置。 一、TwinCAT3 PLC HMI 全屏显示方法 1. 创建Visualization和配置Vi…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023