【C++】：红黑树深度剖析 --- 手撕红黑树！

目录

  • 前言
  • 一，红黑树的概念
  • 二，红黑树的性质
  • 三，红黑树节点的定义
  • 四，红黑树的插入操作
    • 4.1 第一步
    • 4.2 第二步
    • 4.3 插入操作的完整代码
  • 五，红黑树的验证
  • 六，实现红黑树的完整代码
  • 五，红黑树与AVL树的比较

点击跳转至上一篇文章： 【C++】：AVL树的深度解析及其实现

点击跳转至文章：【C++】：二叉树进阶 — 搜索二叉树

前言

上一篇文章介绍了什么是AVL树和AVL树的实现，AVL树也有它的缺点：就是太过追求绝对平衡，比如在插入时要维护其绝对平衡，旋转次数太多，在删除时甚至有可能要一直旋转到根位置，使之性能低下。

本篇文章介绍的红黑树也是一种平衡树，是通过改变节点颜色以及旋转操作，使之接近平衡。

红黑树比AVL树的用途更加广泛，在一些方面效率甚至要优于AVL树，并且 map/set 的底层封装用的也是红黑树。

一，红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

在这里插入图片描述

二，红黑树的性质

(1) 每个结点不是红色就是黑色 ；
(2) 根节点是黑色的 ；
(3) 如果一个节点是红色的，则它的两个孩子结点是黑色的（重点）；
(4) 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（重点） ；
(5) 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，这条性质可有可无，平时不关注)。

三，红黑树节点的定义

红黑树的节点结构与AVL树的大致相同，只是AVL树中有节点的颜色，没有平衡因子。

//枚举颜色
enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(BLACK){}
};

四，红黑树的插入操作

首先我们要思考一个问题，插入节点时，到底是插入红色节点还是黑色节点？为什么？

答案：插入红色节点。

因为我们知道红黑树最重要的两条性质是第(3)(4)条，通过维护这两条规则使之成为红黑树，而当新插入一个节点时，必定会破坏两条规则之一。

假设插入节点为黑色节点，则所有路径的黑色节点数量均不相同，如何让它们相同将是一个巨大的难题，而插入红色节点(此时一定是作为孩子节点)，就破坏规则(3)，但是只要根据其父亲和叔叔节点进行适当的变色就可以继续恢复规则(3)。

显而易见，规则(3)(4)就好比"慈父严母"，非要选择得罪其中一人，那当然是"慈父"了。

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

4.1 第一步

按照二叉搜索的树规则插入新节点：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);//新增节点，颜色为红色cur->_col = RED;//链接时要判断链接在parent的左还是右if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//检测新节点插入后，红黑树的性质是否造到破坏//……}

4.2 第二步

检测新节点插入后，红黑树的性质是否造到破坏：

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定：
(1) cur 为当前节点，p为父节点，g为祖父节点，u为叔叔节点

(2) 下面的抽象图中，a/b/c/d/e 表示具有 n 个节点的红黑树，n >=0。

(一) 情况一: cur为红，p为红，g为黑，u存在且为红：

在这里插入图片描述

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

(二) 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

在这里插入图片描述

下面我们根据 u 的情况用具象图分别解释单旋与双旋操作：

(1) u 不存在，a/b/c/d/e都是空，cur 是新增：

p为g的左孩子，cur为p的左孩子，则进行右单旋转，再 p 变黑，g 变红：

在这里插入图片描述

相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转，再 p 变黑，g 变红：

在这里插入图片描述

p为g的左孩子，cur为p的右孩子，先针对p做左单旋转，再针对 g 做右单旋，cur 变黑，g 变红：

在这里插入图片描述

(2) u 存在且为黑

单旋情况：

在这里插入图片描述
双旋情况：
在这里插入图片描述

4.3 插入操作的完整代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);//新增节点，颜色为红色cur->_col = RED;//链接时要判断链接在parent的左还是右if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//    g// p     uif (parent == grandfather->_left){//找到u的位置Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//u存在且为红,把p/u变黑，g变红,继续向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_left){//     g//  p     u    //c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//  p     u    //	   c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//    g// u     pNode* uncle = grandfather->_left;//u存在且为红,把p/u变黑，g变红,继续向上调整if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_right){//    g// u      p//            c//单旋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 true;
}

五，红黑树的验证

红黑树的检测分为两步：

(1) 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
(2) 检测其是否满足红黑树的性质

这里重点检测的是性质(3)与性质(4)。

检测性质(3)：只要判断当前节点与其父亲节点是否为连续的红色节点；

检测性质(4)：先计算出任意一条路径上的黑色节点作为参考值，再用这个参考值与其他路径上的黑色节点数量比较。

private://中序遍历void InOrder(){_Inorder(_root);cout << endl;}//判断是否平衡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);}private:bool Check(Node* root, int blackNum, const int refNum){//每条路径走到空后与参考值进行比较if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}//检查是否存在连续的红色节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}//blackNum表示：根节点到当前节点的路径上黑色节点的数量if (root->_col == BLACK)blackNum++;return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}

六，实现红黑树的完整代码

RBTree.h

#pragma once#include <iostream>
#include <assert.h>
using namespace std;//枚举颜色
enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(BLACK){}
};template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:Node* Find(const pair<K, V>& kv){Node* cur = _root;while (cur){if (cur->_kv.first > kv.first)cur = cur->_left;else if (cur->_kv.first < kv.first)cur = cur->_right;elsereturn cur;}return nullptr;}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);//新增节点，颜色为红色cur->_col = RED;//链接时要判断链接在parent的左还是右if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//    g// p     uif (parent == grandfather->_left){//找到u的位置Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//u存在且为红,把p/u变黑，g变红,继续向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_left){//     g//  p     u    //c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//  p     u    //	   c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//    g// u     pNode* uncle = grandfather->_left;//u存在且为红,把p/u变黑，g变红,继续向上调整if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_right){//    g// u      p//            c//单旋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 true;}//中序遍历void InOrder(){_Inorder(_root);cout << endl;}//判断是否平衡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);}private://每个节点的位置记录一个值blackNum//blackNum表示：根节点到当前节点的路径上黑色节点的数量bool Check(Node* root, int blackNum, const int refNum){//每条路径走到空后与参考值进行比较if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}//检查是否存在连续的红色节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK)blackNum++;return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;if (subLR)subLR->_parent = parent;parent->_left = subLR;subL->_right = parent;//改变之前记录Node* ppNode = parent->_parent;parent->_parent = subL;//parent为根if (parent == _root){_root = subL;_root->_parent = nullptr;}else{//parent为一颗子树if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;if (subRL)subRL->_parent = parent;parent->_right = subRL;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;//parent为根if (parent == _root){_root = subR;_root->_parent = nullptr;}else{//parent为一颗子树if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}
private:Node* _root = nullptr;
};//测试代码
void Test1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 16,3,7,11,9,26,18,14,15 };RBTree<int, int> t;for (auto e : a)t.Insert({ e ,e });t.InOrder();cout << t.IsBalance() << endl;
}

Test.cpp

#include "RBTree.h"int main()
{Test1();return 0;
}

运行结果如下：

中序遍历是有序的，说明是搜索二叉树，返回1，说明满足红黑树的性质，是平衡树。

在这里插入图片描述

五，红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

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

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

相关文章

【接口自动化_08课_Pytest+Yaml+Allure框架】

【接口自动化_08课_Pytest+Yaml+Allure框架】

上节课一些内容 的补充 1、openxl这个方法&#xff0c;第一个元素是从1开始的&#xff0c;不是从0开始 回写的列在程序里写的是11&#xff0c;是因为是固定值 一、1. Yaml入门及应用 1、什么是yaml YAML&#xff08;/ˈjməl/&#xff0c;尾音类似camel骆驼&#xff09;是一…
阅读更多...
单向链表

单向链表

目录 思维导图&#xff1a; 学习内容&#xff1a; 1. 链表的引入 1.1 顺序表的优缺点 1.1.1 优点 1.1.2 不足 1.1.3 缺点 1.2 链表的概念 1.2.1 链式存储的线性表叫做链表 1.2.2 链表的基础概念 1.3 链表的分类 2. 单向链表 2.1 节点结构体类型 2.2 创建链表 2.…
阅读更多...
EXCEL 排名(RANK,COUNTIFS)

EXCEL 排名(RANK,COUNTIFS)

1.单列排序 需求描述&#xff1a;如有下面表格&#xff0c;需要按笔试成绩整体排名。 解决步骤&#xff1a; 我们使用RANK函数即可实现单列整体排名。 Number 选择第一列。 Ref 选择这一整列&#xff08;CtrlShift向下箭头、再按F4&#xff09;。 "确定"即可计算…
阅读更多...
图像分类算法概述：深度学习方法

图像分类算法概述：深度学习方法

图像分类算法概述&#xff1a;深度学习方法 图像分类是计算机视觉中的一个基本任务&#xff0c;近年来随着深度学习的发展&#xff0c;图像分类算法取得了巨大的进步。本文将概述主要的深度学习图像分类算法。 #mermaid-svg-fkTtkPLl9ahuVT6w {font-family:"trebuchet ms…
阅读更多...
BGP选路之Preferred value

BGP选路之Preferred value

原理概述 当一台BGP路由器中存在多条去往同一目标网络的BGP路由时&#xff0c;BGP协议会对这些BGP路由的属性进行比较&#xff0c;以确定去往该目标网络的最优BGP路由&#xff0c;然后将该最优BGP路由与去往同一目标网络的其他协议路由进行比较&#xff0c;从而决定是否将该最优…
阅读更多...
元组(tuple)

元组(tuple)

目录 一、基本介绍 1、元组(tuple)可以存放多个不同数据类型&#xff0c;元组是不可变序列 2、元组也是一种数据类型 二、元组的定义 1、元组的定义 2、代码说明 三、元组的使用 1、元组使用语法 2、举例说明 3、代码演示&#xff0c;访问/获取第三个数据/元素 四、…
阅读更多...
SpringBoot集成Kaptcha验证码

SpringBoot集成Kaptcha验证码

Hi &#x1f44b;, Im shy 有人见尘埃&#xff0c;有人见星辰 1. 什么是Kaptcha验证码? Kaptcha是一个强大的开源Java验证码生成库,由Google开发。它能够生成高度可配置的图片验证码,主要用于防止自动化程序滥用web应用,提高应用的安全性。 2. Kaptcha的主要特性 Kaptch…
阅读更多...
AMEsim液压阀伯德图绘制方法

AMEsim液压阀伯德图绘制方法

之前也在液压圈论坛里面发过类似的贴子&#xff0c;具体可以看这个网址&#x1f6aa;&#x1f449;&#xff1a;如何得出说明书里面的伯德图曲线&#xff1f;&#xff0c;回复的人还是比较少&#xff0c;这个方法重要信息是参考百度文库这篇文章&#x1f6aa;&#x1f449;&…
阅读更多...
相机的内参与外参

相机的内参与外参

目录 一、相机的内参二、相机的外参 一、相机的内参 如下图所示是相机的针孔模型示意图&#xff1a; 光心O所处平面是相机坐标系(O&#xff0c;P)&#xff0c;像素平面所在坐标系为像素坐标系(O’&#xff0c;P’)。 焦距f&#xff1a;O到O’的距离 相机的内参表示的是相机坐标…
阅读更多...
文本编辑三巨头（grep）

文本编辑三巨头（grep）

目录 正则表达式 元字符 grep 案例 我在编写脚本的时候发现&#xff0c;三个文本编辑的命令&#xff08;grep、sed、awk&#xff0c;被称为文本编辑三剑客&#xff0c;我习惯叫它三巨头&#xff09;用的还挺多的&#xff0c;说实话我一开始学的时候也有些懵&#xff0c;主要…
阅读更多...
【实现100个unity特效之8】使用ShaderGraph实现2d贴图中指定部分局部发光效果

【实现100个unity特效之8】使用ShaderGraph实现2d贴图中指定部分局部发光效果

最终效果 寒冰法师 火焰法师 文章目录 最终效果寒冰法师火焰法师 素材一、功能分析实现方法基本思路Unity的Bloom后处理为什么关键部位白色&#xff1f;最终结果 二、 新建URP项目三、合并图片四、使用PS制作黑白图片方法一 手动涂鸦方法二 魔棒工具1. 拖入图片进PS&#xff0…
阅读更多...
环信+亚马逊云科技服务：助力出海AI社交应用扬帆起航

环信+亚马逊云科技服务：助力出海AI社交应用扬帆起航

随着大模型技术的飞速发展&#xff0c;AI智能体的社交体验得到了显著提升&#xff0c;AI社交类应用在全球范围内持续火热。尤其是年轻一代对新技术和新体验的热情&#xff0c;使得AI社交产品在海外市场迅速崛起。作为领先的即时通讯解决方案提供商&#xff0c;环信与亚马逊云科…
阅读更多...
# Redis 入门到精通（九）-- 主从复制（2）

# Redis 入门到精通（九）-- 主从复制（2）

Redis 入门到精通&#xff08;九&#xff09;-- 主从复制&#xff08;2&#xff09; 一、redis 主从复制–数据同步阶段注意事项 1、数据同步阶段 master 说明 1&#xff09;如果 master 数据量巨大&#xff0c;数据同步阶段应避开流量高峰期&#xff0c;避免造成 master 阻…
阅读更多...
掌握Rust：函数、闭包与迭代器的综合运用

掌握Rust：函数、闭包与迭代器的综合运用

掌握Rust&#xff1a;函数、闭包与迭代器的综合运用 引言&#xff1a;解锁 Rust 高效编程的钥匙函数定义与模式匹配&#xff1a;构建逻辑的基石高阶函数与闭包&#xff1a;代码复用的艺术迭代器与 for 循环&#xff1a;高效数据处理的引擎综合应用案例&#xff1a;构建一个简易…
阅读更多...
JavaSE--基础语法--继承和多态(第三期)

JavaSE--基础语法--继承和多态(第三期)

一.继承 1.1我们为什么需要继承? 首先&#xff0c;Java中使用类对现实世界中实体来进行描述&#xff0c;类经过实例化之后的产物对象&#xff0c;则可以用来表示现实中的实体&#xff0c;但是 现实世界错综复杂&#xff0c;事物之间可能会存在一些关联&#xff0c;那在设计程…
阅读更多...
Redis的应用场景及类型

Redis的应用场景及类型

目录 一、Redis的应用场景 1、限流 2、分布式锁 3、点赞 4、消息队列 二、Redis类型的命令及用法 1、String类型 2、Hash类型 3、List类型 4、Set类型 5、Zset类型 6、Redis工具类 Redis使用缓存的目的就是提升读写性能 实际业务场景下&#xff0c;我们就可以把 Mys…
阅读更多...
Mysql数据库第四次作业

Mysql数据库第四次作业

mysql> create table student(sno int primary key auto_increment,sname varchar(30) not null unique,Ssex varchar(2) check (Ssex男 or Ssex女) not null,Sage int not null,Sdept varchar(10) default计算机 not null); mysql> create table Course(Con int primar…
阅读更多...
pytest的安装和介绍和 Exit Code 含义

pytest的安装和介绍和 Exit Code 含义

pytest 准备工作&#xff08;在cmd里&#xff09;&#xff1a; 1安装 pip install -U pytest2验证安装 pytest --version # 会展示当前已安装版本3其他的 显示可用的内置函数参数 pytest --fixtures通过命令行查看帮助信息及配置文件选项 pytest --help一、pytets框架中的…
阅读更多...
Air780EP-AT开发-HTTP应用指南

Air780EP-AT开发-HTTP应用指南

简介 关联文档和使用工具&#xff1a; AT固件获取AT指令手册 概述 4G模块支持HTTP和HTTPS协议&#xff0c; HTTP应用的基本流程如下&#xff1a; 1、激活PDP&#xff08;参考&#xff1a;http://oldask.openluat.com/article/937&#xff09;2、初始化HTTP服务3、设置HTTP会话…
阅读更多...
从0到1使用Docker部署java项目详解

从0到1使用Docker部署java项目详解

Docker部署Java项目相比传统部署方式&#xff0c;在环境一致性、配置管理、可扩展性和安全性等方面具有显著优势。然而&#xff0c;它也带来了学习成本、资源消耗和复杂度增加等挑战。 云服务器 白嫖阿里云服务 通过免费试用方式获取自己的阿里云服务器。当然&#xff0c;如…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023