C++手撕红黑树

文章目录

    • 红黑树
      • 概念
      • 性质（条件限制）
      • 节点的定义
      • 红黑树的结构
      • 红黑树的插入
        • cur为红，p为红，g为黑，u存在且为红
        • cur为红，p为红，g为黑，u不存在或u为黑，插入到p对应的一边
        • cur为红，p为红，g为黑，u不存在或u存在且为黑，插入到与p相反的一边
        • 示例代码
      • 红黑树的验证
      • 红黑树与AVL树的比较
    • 完整代码

红黑树

概念

和AVL树一样，红黑树也是一种二叉搜索树，是解决二叉搜索树不平衡的另一种方案，他在每个节点上增加一个存储位，用于表示节点的颜色，是Red或者Black

红黑树的核心思想是通过一些着色的条件限制，达到一种最长路径不超过最短路径的两倍的状态

所以说红黑树并不是严格平衡的树，而是一种近似平衡

例如

2024-04-08 134510.png

性质（条件限制）

红黑树一共有五条性质，由此来保证最长路径不超过最短路径的两倍

  1. 每个节点都有颜色，不是黑色就是红色
  2. 根节点是黑色的
  3. 如果一共节点是红色，那么他的子节点一定是黑色（不会出现两个红色节点连接的情况）
  4. 对于每个节点，以这个节点到所有后代的任意路径上，均包含相同数目的黑色节点
  5. 每个叶子节点（空节点）是黑色的（为了满足第四条性质，某些情况下如果没有第五条第四条会失效）

节点的定义

// 颜色
enum Color {RED,BLACK
};template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _col;RBTreeNode(const T& data) :_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};

我们定义颜色时，使用枚举类型，可以方便且明了的看到颜色

除此之外我们默认插入节点是红色的，因为一旦插入节点是黑色，就会违反第四条规则，如果要满足的话，就要走到每一条路径上插入对应的黑色节点，代价巨大

当插入节点是红色时，有可能会违反第三条规则，但是我们可以通过变色，旋转等操作在局部进行改变，这样就能使之仍然满足条件

红黑树的结构

为了后续利用红黑树封装map和set，我们对红黑树增加一个头节点，为了和根节点进行区分，我们将头节点赋为黑色，并且让头节点的parent指向根节点，left指向红黑树的最小节点，right指向最大节点，如图

image.png

红黑树的插入

红黑树插入时也是按照二叉搜索树的规则进行插入，并在此基础上加上平衡条件，因此插入也就分为两步

  1. 按照二叉搜索树的规则插入新节点
  2. 插入节点后检测规则是否被破坏

因为插入红节点时只有可能破坏第三条规则，因此我们只需要判断父节点是否为红色即可

然后我们分情况讨论

为了方便叙述，我们约定cur为插入节点，p为父节点，g为祖父节点，u为叔叔节点

cur为红，p为红，g为黑，u存在且为红

画出来是这样的

image.png

这时我们需要将g改为红色，p和u改为黑色即可，这样既能保证红色不连续，黑色数量一致，如图

image.png

但是如果g是是子树，那么g一定有父节点，当g的父节点也是红色时，也就同样需要向上调整了

cur为红，p为红，g为黑，u不存在或u为黑，插入到p对应的一边

画出来是这样的

image.png

u的情况有两种

  1. u节点不存在，说明cur一定是新插入的节点，因为要保证左右两个路径的黑色节点的数量相同
  2. u节点存在，说明cur节点是由下至上调整的红色，原因也是左右路径的黑色节点要相同

对于这两种情况的调整方法是相同的，如果p是g的左节点，cur为p的左节点，则右单旋，如果p是g的右节点，cur为p的右节点，则左单旋

同时p要变成黑色，g要变成红色

变成如下状态

image.png

那么因为最上面的根节点颜色没有变化，也就不需要继续向上调整了

cur为红，p为红，g为黑，u不存在或u存在且为黑，插入到与p相反的一边

如图

image.png

这种情况需要针对p进行单旋，如果p为g的左节点，cur为p的右节点，则对p左单旋，反之则为右单旋，此时就会变成第二种情况，再继续处理即可

第一次处理的结果如下

image.png

示例代码
template<class K, class T, class KeyOfT>
class RBTree {typedef RBTreeNode<T> Node;
public:pair<Node*, bool> Insert(const T& data) {// 插入根节点直接返回if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;// 平衡二叉树找到插入位置while (cur) {if (kot(cur->_data) < kot(data)) {parent = cur;cur = cur->_right;} else if (kot(cur->_data) > kot(data)) {parent = cur;cur = cur->_left;} else {return make_pair(cur, false);}}// 新建节点cur = new Node(data);Node* newnode = cur;cur->_col = RED;// 连接父节点if (kot(parent->_data) < kot(data)) {parent->_right = cur;cur->_parent = parent;} else {parent->_left = cur;cur->_parent = parent;}// 如果父节点存在且父节点为红色则需要调整while (parent && parent->_col == RED) {Node* grandfather = parent->_parent;if (parent == grandfather->_left) {//     g//   p   u// c // 判断u是否存在和他的颜色Node* uncle = grandfather->_right;// 如果存在且为红色if (uncle && uncle->_col == RED) {// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;} else {// 如果不存在或u为黑色，需要判断同侧还是异侧// 如果是同侧if (cur == parent->_left) {//     g//   p// cRotateR(grandfather); // 右旋// 调整颜色parent->_col = BLACK;grandfather->_col = RED;} else {//    g//  p//    cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}} else { // p = g->rNode* uncle = grandfather->_left;//     g//   u   p//         c// 判断u是否存在和他的颜色// 如果存在且为红色if (uncle && uncle->_col == RED) {// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;} else {if (cur == parent->_right) {RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;} else {//     g//   u   p //     c//RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, 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;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 (_root == parent) {_root = subL;subL->_parent = nullptr;} else {if (parentParent->_left == parent) {parentParent->_left = subL;} else {parentParent->_right = subL;}subL->_parent = parentParent;}}
private:Node* _root = nullptr;
};

红黑树的验证

红黑树要验证需要验证两个部分

  1. 检测是否中序遍历是有序序列
  2. 检测是否满足红黑树的性质

这里我们就不讲红黑树的删除了，完成红黑树的验证之后就算作已经完成了任务，接下来会使用红黑树模拟实现map和set

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，但是红黑树不追求绝对的平衡，降低了插入和旋转的次数，因此性能比AVL更优，而且红黑树比AVL树的实现更加简单，所以实际中运用红黑树更多

完整代码

#pragma once
#include<utility>
#include<iostream>
using namespace std;
// 颜色
enum Color {RED,BLACK
};template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) {}
};template<class K, class T, class KeyOfT>
class RBTree {typedef RBTreeNode<T> Node;
public:pair<Node*, bool> Insert(const T& data) {if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;// 平衡二叉树找到插入位置while (cur) {if (kot(cur->_data) < kot(data)) {parent = cur;cur = cur->_right;} else if (kot(cur->_data) > kot(data)) {parent = cur;cur = cur->_left;} else {return make_pair(cur, false);}}// 新建节点cur = new Node(data);Node* newnode = cur;cur->_col = RED;// 连接父节点if (kot(parent->_data) < kot(data)) {parent->_right = cur;cur->_parent = parent;} else {parent->_left = cur;cur->_parent = parent;}// 如果父节点存在且父节点为红色则需要调整while (parent && parent->_col == RED) {Node* grandfather = parent->_parent;if (parent == grandfather->_left) {//     g//   p   u// c // 判断u是否存在和他的颜色Node* uncle = grandfather->_right;// 如果存在且为红色if (uncle && uncle->_col == RED) {// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;} else {// 如果不存在或u为黑色，需要判断同侧还是异侧// 如果是同侧if (cur == parent->_left) {//     g//   p// cRotateR(grandfather); // 右旋// 调整颜色parent->_col = BLACK;grandfather->_col = RED;} else {//    g//  p//    cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}} else { // p = g->rNode* uncle = grandfather->_left;//     g//   u   p//         c// 判断u是否存在和他的颜色// 如果存在且为红色if (uncle && uncle->_col == RED) {// 变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;} else {if (cur == parent->_right) {RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;} else {//     g//   u   p //     c//RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, 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;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 (_root == parent) {_root = subL;subL->_parent = nullptr;} else {if (parentParent->_left == parent) {parentParent->_left = subL;} else {parentParent->_right = subL;}subL->_parent = parentParent;}}void InOrder() {_InOrder(_root);cout << endl;}void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << ' ';_InOrder(root->_right);}bool Check(Node* root, int blacknum, const int refVal) {if (root == nullptr) {if (blacknum != refVal) {cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED) {cout << "存在连续的红节点" << endl;return false;}if (root->_col == BLACK) {++blacknum;}return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);}bool IsBalance() {if (_root == nullptr)return true;if (_root->_col == RED)return false;int refVal = 0; // 参考值Node* cur = _root;while (cur) {if (cur->_col == BLACK) {++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}int Height() {return _Height(_root);}int _Height(Node* root) {if (root == nullptr)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH + rightH;}size_t Size() {return _Size(_root);}size_t _Size(Node* root) {if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}Node* Find(const K& key) {Node* cur = _root;while (cur) {if (cur->_data < key) {cur = cur->_right;}else if (cur->_data > key) {cur = cur->_left;}else {return cur;}}return nullptr;}private:Node* _root = nullptr;
};

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

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

相关文章

深度评测2024年热门婴儿洗衣机，鲸立、希亦、小吉等品牌一网打尽！

深度评测2024年热门婴儿洗衣机，鲸立、希亦、小吉等品牌一网打尽！

为人父母&#xff0c;是一件非常美妙的事情&#xff0c;在养育新生命的过程中&#xff0c;细心的照顾是非常重要的&#xff0c;而最小的细节&#xff0c;就是让婴儿的衣服保持最温和、最有效的清洁。而婴儿洗衣机是当今不少家庭的福音&#xff0c;它给家长们带来了巨大的方便&a…
阅读更多...
R语言数据可视化：ggplot2绘图系统

R语言数据可视化：ggplot2绘图系统

ggpolt2绘图系统被称为R语言中最高大上的绘图系统&#xff0c;使用ggplot2绘图系统绘图就像是在使用语法创造句子一样&#xff0c;把数据映射到几何客体的美学属性上。因此使用ggplot2绘图系统的核心函数ggplot来绘图必须具备三个条件&#xff0c;数据data&#xff0c;美学属性…
阅读更多...
力扣HOT100 - 560. 和为k的子数组

力扣HOT100 - 560. 和为k的子数组

解题思路&#xff1a; 方法一&#xff1a;枚举 class Solution {public int subarraySum(int[] nums, int k) {int cnt 0;for (int start 0; start < nums.length; start) {int sum 0;//注意开始位置for (int end start; end < nums.length; end) {sum nums[end];…
阅读更多...
软件设计师知识点-1

软件设计师知识点-1

串行的计算公式为&#xff1a;(取值时间分析时间执行时间) x 指令的个数 流水线的计算公式为&#xff1a;单条指令的执行时间 (n-1) x 流水线周期 n的意思为指令的个数&#xff0c;流水线周期的意思为取值&#xff0c;分析&#xff0c;执行三条执行过程中花费时间最多的那条…
阅读更多...
VSCode配置AI自动补全插件Tabnine

VSCode配置AI自动补全插件Tabnine

面向软件开发人员的 AI 助手 使用 AI 代码完成更快地编写代码 什么是Tabnine Tabnine 是一款 AI 代码助手&#xff0c;可让您成为更好的开发人员。Tabnine 将通过所有最流行的编码语言和 IDE 的实时代码完成、聊天和代码生成来提高您的开发速度。 无论您将其称为 IntelliSens…
阅读更多...
代码随想录阅读笔记-二叉树【二叉搜索树转换为累加树】

代码随想录阅读笔记-二叉树【二叉搜索树转换为累加树】

题目 给出二叉 搜索 树的根节点&#xff0c;该树的节点值各不相同&#xff0c;请你将其转换为累加树&#xff08;Greater Sum Tree&#xff09;&#xff0c;使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下&#xff0c;二叉搜索树满足下列约束条件&…
阅读更多...
Java绘图坐标体系

Java绘图坐标体系

一、介绍 下图说明了Java坐标系。坐标原点位于左上角&#xff0c;以像素为单位。在Java坐标系中&#xff0c;第一个是x坐标&#xff0c;表示当前位置为水平方向&#xff0c;距离坐标原点x个像素&#xff1b;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐…
阅读更多...
西门子PLC(S7-200 SMART)学习笔记1：初识PLC可编程逻辑器件

西门子PLC(S7-200 SMART)学习笔记1：初识PLC可编程逻辑器件

今日开始我的西门子PLC学习之路&#xff0c;学习的型号以S7-200 SMART为主 主要认识一下PLC是什么、型号怎么看、 通信相关、编程软件、构造及工作原理 目录 西门子官方PLC手册获取&#xff1a; 1、PLC可编程逻辑器件的基本认识&#xff1a; PLC的结构及各部分的作用&#xff…
阅读更多...
threejs 基础知识点汇总

threejs 基础知识点汇总

threejs 基础知识点汇总 之前写了几篇博文&#xff0c;但是我觉得写的不好&#xff0c;我今天再补充一篇还不好的&#xff0c;把基础知识点汇总一下&#xff0c;不写运行的代码了&#xff0c;只写关键代码&#xff0c;但是看了之前我写的那几篇&#xff0c;看这篇的话问题其实不…
阅读更多...
群晖NAS使用Docker部署Potopea在线图片编辑工具并实现公网访问

群晖NAS使用Docker部署Potopea在线图片编辑工具并实现公网访问

文章目录 1. 部署Photopea2. 运行Photopea3. 群晖安装Cpolar4. 配置公网地址5. 公网访问测试6. 固定公网地址 本文主要介绍如何在群晖NAS使用Docker部署Potopea在线图片编辑工具&#xff0c;并结合cpolar内网穿透实现公网环境可以远程访问本地部署的Potopea. Photopea是一款强大…
阅读更多...
伺服电机的惯性

伺服电机的惯性

一、伺服电机的惯性 伺服电机的惯性主要指电机及其连接的负载的惯性。它是通过将物体的质量与其距离旋转轴的平方相乘得到的。对于伺服电机来说&#xff0c;惯性体现了电机和负载对速度和加速度变化的阻力程度&#xff0c;即其惯性越大&#xff0c;对速度和加速度变化的阻…
阅读更多...
人工智能_大模型023_AssistantsAPI_01_OpenAI助手的创建_API的调用_生命周期管理_对话服务创建---人工智能工作笔记0159

人工智能_大模型023_AssistantsAPI_01_OpenAI助手的创建_API的调用_生命周期管理_对话服务创建---人工智能工作笔记0159

先来说一下一些问题: 尽量不要微调,很麻烦,而且效果需要自己不断的去测试. 如果文档中有图表,大量的图片去分析就不合适了. 是否用RAG搜索,这个可以这样来弄,首先去es库去搜能直接找到答案可以就不用去RAG检索了,也可以设置一个分,如果低于60分,那么就可以去进行RAG检索 微…
阅读更多...
看不起的行业，其实比工作 赚的多

看不起的行业，其实比工作 赚的多

1、烧烤&#xff0c;只要你敢干&#xff0c;一年的利润是普通人五年的工资&#xff0c;日入2000。 2、翻新二手手机&#xff0c;深圳华强北好的时间段一天能卖出几千台&#xff0c;日入1000。 3、大学食堂开个小卖部&#xff0c;一个月就能挣个大千&#xff0c;日入1500。 4…
阅读更多...
基于Spring Boot与Vue的智能化学生心理咨询评估系统

基于Spring Boot与Vue的智能化学生心理咨询评估系统

末尾获取源码作者介绍&#xff1a;大家好&#xff0c;我是墨韵&#xff0c;本人4年开发经验&#xff0c;专注定制项目开发 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c;不进则退。学习如赶路&#xff0c;不能慢一步。 目录 一、项目简介 二、开发技术与环…
阅读更多...
计算机网络：网络层的路由选择协议

计算机网络：网络层的路由选择协议

网络层的 路由选择协议 路由表 从下图的三个简单的拓扑结构所示&#xff0c;如果其中一条链路断了&#xff0c;静态路由就通不了&#xff0c;断了。但是使用动态路由可以动态调届选择策略。 静态路由和动态路由的区别对比和特点 路由选择协议 自治系统AS 内部网关协议RI…
阅读更多...
MySQL高级（索引结构Hash，为什么InnoDB存储引擎选择使用B+tree索引结构？）

MySQL高级（索引结构Hash，为什么InnoDB存储引擎选择使用B+tree索引结构？）

目录 1、Hash索引结构 2、Hash索引特点 3、存储引擎支持 4、为什么InnoDB存储引擎选择使用Btree索引结构&#xff1f; 1、Hash索引结构 哈希索引就是采用一定的hash算法&#xff0c;将键值换算成新的hash值&#xff0c;映射到对应的槽位上&#xff0c;然后存储在hash表中。 如…
阅读更多...
SpringBoot第一个hello world项目

SpringBoot第一个hello world项目

文章目录 前言一、Spring Boot是什么&#xff1f;二、使用步骤1. 创建项目2.书写测试 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 例如&#xff1a;随着人工智能的不断发展&#xff0c;机器学习这门技术也越来越重要&#xff0c;很多人都开启了…
阅读更多...
【机器学习】深入解析机器学习基础

【机器学习】深入解析机器学习基础

在本篇深入探讨中&#xff0c;我们将揭开机器学习背后的基础原理&#xff0c;这不仅包括其数学框架&#xff0c;更涵盖了从实际应用到理论探索的全方位视角。机器学习作为数据科学的重要分支&#xff0c;其力量来源于算法的能力&#xff0c;这些算法能够从数据中学习并做出预测…
阅读更多...
【JavaWeb】Tomcat服务器

【JavaWeb】Tomcat服务器

目录 动态网站动态网站的特点 程序架构B/S与C/S的比较B/S技术的工作原理URL 什么是Web服务器 Web服务器、服务端、服务器的区别和联系什么是TomcatTomcat服务器的安装与配置解压缩版本Tomcat的配置添加系统变量&#xff0c;名称为CATALINA_HOME&#xff0c;值为Tomcat的安装目录…
阅读更多...
C/C++中局部变量static用法实例

C/C++中局部变量static用法实例

1. 普通局部变量存储于进程栈空间&#xff0c;使用完毕会立即释放&#xff0c;静态局部变量使用static修饰符定义&#xff0c;即使在声明时未赋初值&#xff0c;编译器也会把它初始化为0&#xff0c;并且静态局部变量存储于进程的全局数据区&#xff0c;即使函数返回&#xff0…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023