深入探索：C++红黑树原理与实现

ops/2024/11/26 19:55:23/

在这里插入图片描述

文章目录

  • 一、红黑树的概念
  • 二、红黑树的规则
  • 三、红黑树与AVL树性能对比
  • 四、红黑树框架的搭建
  • 五、红黑树的插入逻辑
    • 1. 大体框架
    • 2. 初始颜色的设置
    • 3. 颜色的调整
      • 1）通过具体的情况对颜色调整进行框架认识
      • 2）通过抽象图对颜色调整加深理解
        • 情况一：uncle存在且uncle为红色
        • 情况二：uncle不存在或uncle存在且uncle为黑色
  • 六、红黑树是否构建正确的检查
  • 七、红黑树总体代码总结
  • 结语

一、红黑树的概念

红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色，通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

二、红黑树的规则

在这里插入图片描述

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点):

规则解释：

  • 什么是路径？对于上图来说，一共有11条路径，根到空节点算一条路径。

  • 红色结点的孩子必须是黑色结点，也就是说任何路径没有连续的红色节点。

  • 每条路径上黑色节点的数量相等

  • 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点说明:《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道一下这个概念即可。

  • 为什么说只要满足了上述所有规则，就能保证红黑树其最长路径中节点个数不会超过最短路径节点个数的两倍？

只要满足了上述规则，最短的路径将会是全是黑色，最长的路径将是一红一黑红黑相间：
由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就就是全是黑色结点的路径，假设最短路径长度为bh(black height)。
由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是黑一红间隔组成，那么最长路径的长度为2*bh。

综合红黑树的4点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x，那么bh<=h<=2*bh。

在这里插入图片描述

三、红黑树与AVL树性能对比

性能差异总结：

  1. AVL树:

    • 严格平衡（高度差不超过1）。
    • 高度较低，查找效率更高。
    • 插入和删除操作由于需要频繁调整平衡，开销较大。

  2. 红黑树:

    • 平衡条件较宽松（最长路径不超过最短路径的2倍）。
    • 高度比AVL树稍高，查找效率略低。
    • 插入和删除操作调整较少，性能更优。

表格总结：

树种类平衡条件高度（1000个值）高度（10亿个值）查找效率插入/删除效率
AVL树高度差不超过1(log N = 10)(log N = 30)更高较低
红黑树最长路径 ≤ 最短路径的2倍(2log N = 20)(2log N = 60)略低更高

四、红黑树框架的搭建

#pragma once
#include<iostream>using namespace std;enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};template<class K, class V> 
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

五、红黑树的插入逻辑

1. 大体框架

首先，插入逻辑的答题思路是和前面我们所学的AVL树的插入主体框架是大体相同的，代码如下：

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 (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first)   // 大于往右走{parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);// 链接if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;return true;
}

2. 初始颜色的设置

首先迎来我们第一个问题，新插入结点初始的颜色要设置成什么呢?

如果是根节点，答案很明确，根节点的颜色是黑色！

// 树为空，直接插入然后返回
if (_root == nullptr)
{_root = new Node(kv);// 根节点必须是黑色_root->_col = BLACK;return true;
}

那么对于其他结点呢？
是插入红色，还是插入黑色？

这里面就涉及到两个相冲的规则：
在这里插入图片描述

如果我们选择插入黑色，那么就会违背规则4，那么画出的图是这样的：
在这里插入图片描述
就会造成所有路径黑色结点出现问题，就要更改所有路径的风险，因此我们不选择这种方案。

如果选择插入红色结点，就会违背规则3，画出的图是这样的：
在这里插入图片描述

在这里插入图片描述

如果插入到红色节点后，则只牵扯到当前路径，很容易进行调整。因此我们新插入的结点默认为红色！！！

所以对于其他颜色，我们调节的代码为：

cur = new Node(kv);
// 其他结点初始颜色为红色
cur->_col = RED;

3. 颜色的调整

1）通过具体的情况对颜色调整进行框架认识

对于颜色的调整，我们可以总结为三种情况：

情况一：uncle存在，且为红色：
解决方式：parent与uncle变黑，grandfather变红，继续向上调整。

在这里插入图片描述

情况二：uncle不存在
解决方式：旋转 + 变色

在这里插入图片描述

情况三：uncle存在且为黑色
解决方式：旋转 + 变色

我们上一种情况继续插入，就会变成这种情况：

在这里插入图片描述

在这里插入图片描述

2）通过抽象图对颜色调整加深理解

情况一：uncle存在且uncle为红色

在这里插入图片描述

代码解析：

// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定
// 用while循环是因为我们要不断的向上调整
while (parent && parent->_col == RED)
{// 首先我们要找到grandfatherNode* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif (parent == grandfather->_left){// 说明uncle在右边Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else    // uncle不存在 或 uncle存在且为黑色{ // ...}}// 这里保证根为黑色
_root->_col = BLACK;
情况二：uncle不存在或uncle存在且uncle为黑色

在这里插入图片描述
因为这里牵扯到旋转，所以我们需要知道旋转的逻辑，这个J桑之前做过专题讲解过，不会的小伙伴可以戳这里~🥰🥰🥰

C++：探索AVL树旋转的奥秘

下面我们在这里再放以下旋转的代码~
唯一的区别就是，这里不需要平衡因子。

// 左单旋
void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}
}// 右单旋
void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}
}

代码解析：

else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋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;}

六、红黑树是否构建正确的检查

以下的这段代码的核心目标是检查红黑树是否构建正确，主要基于红黑树的规则进行验证。代码的设计分为两个关键部分：计算基准值和递归验证规则。

代码解析

// 检查是否构建正确
bool CheckColour(Node* root, int blacknum, int benchmark)
{if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);
}bool IsBalance()
{return IsBalance(_root);
}bool IsBalance(Node* root)
{if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);
}

  1. 基准值的计算
    在红黑树中，所有从根节点到叶节点的路径上，必须经过相同数量的黑色节点。为此，代码首先沿着树的左侧路径计算路径上黑色节点的数量，作为基准值 benchmark。这是验证红黑树平衡性的关键步骤。

  2. 递归验证红黑树规则
    接下来通过递归函数 CheckColour，对红黑树的所有节点进行逐一验证，确保其符合以下规则：

  3. 每个节点是红色或黑色。

  4. 红色节点的子节点必须是黑色（即不能出现连续的红色节点）。

  5. 从任一节点到其所有后代的每条路径包含相同数量的黑色节点。

整体逻辑描述

  • 首先调用 IsBalance()，对整棵树进行平衡性检查。

    • 先判断根节点是否为黑色，这是红黑树的基本要求。
    • 沿着左侧路径，计算从根节点到最左叶节点的黑色节点总数，作为基准值。

  • 然后进入递归检查函数 CheckColour()：

    • 如果当前节点为空（即到达叶节点），检查该路径累计的黑色节点数量是否与基准值一致。
    • 对每个非空节点，检查其颜色是否满足规则：红色节点不能有红色父节点。
    • 累计当前路径上的黑色节点数，并递归检查左右子树。

  • 最终通过递归结果判断整棵树是否满足红黑树性质。

  • 如果发现不符合的地方（如连续红色节点或黑色节点数不一致），会提前返回 false 并结束验证。

我们运行的时候给10000000个随机值，看看会不会调用成功。

#include"RBTree_1.h"#include<vector>int main()
{const int N = 10000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(i);}RBTree<int, int> rbt;for (auto e : v){rbt.Insert(make_pair(e, e));}cout << rbt.IsBalance() << endl;return 0;
}

运行结果如下：
在这里插入图片描述

说明我们的红黑树构建成功啦~

七、红黑树总体代码总结

#pragma once
#include<iostream>using namespace std;enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _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* cur = _root;Node* parent = nullptr;while (cur){// 小于往左走if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first)   // 大于往右走{parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);// 其他结点初始颜色为红色cur->_col = RED;// 链接if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while (parent && parent->_col == RED){// 首先我们要找到grandfatherNode* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif (parent == grandfather->_left){// 说明uncle在右边Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋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 //(parent == grandfather->_right)  // 如果parent是grandfather->_right{// 说明uncle在左边Node* uncle = grandfather->_left;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 右左双旋{// g//	  p// cRotateR(parent);RotateL(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 这里保证根为黑色_root->_col = BLACK;return true;}// 左单旋void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 右单旋void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 检查是否构建正确bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}private:Node* _root = nullptr;
};

结语

那么到这里就结束啦，创作不易，如果对各位大佬有帮助的话，麻烦给一个一键三连吧~谢谢各位大佬🥰🥰🥰

在这里插入图片描述


http://www.ppmy.cn/ops/136910.html

相关文章

网络安全公司150强

网络安全公司150强

本清单主要列出专门或主要专注于网络安全的公司。 公司名称 业务描述 1Password 企业密码安全管理 A10 Networks 安全云应用服务 Abnormal Security 云原生邮件安全 Absolute 终端防护平台 Agari 电子邮件和网络钓鱼威胁防护 Aqua Security 云原生应用保护 Arcse…
阅读更多...
TCP快速重传机制为啥出现重复ACK？

TCP快速重传机制为啥出现重复ACK？

TCP快速重传机制为啥出现重复ACK 简单来说&#xff0c;丢失数据包后发送方至少发了三个请求&#xff0c;每个请求返回接收方下一次期待的序列号ACK&#xff0c;也就是丢失数据包之前的一个正常请求的确认ACK值 在 TCP&#xff08;Transmission Control Protocol&#xff0c;传…
阅读更多...
Flutter：启动屏逻辑处理02：启动页

Flutter：启动屏逻辑处理02：启动页

启动屏启动之后&#xff0c;制作一个启动页面 新建splash&#xff1a;view 视图中只有一张图片sliding.png就是我们的启动图 import package:flutter/material.dart; import package:get/get.dart; import index.dart; class SplashPage extends GetView<SplashController…
阅读更多...
#Java-常用API-BigInteger、BigDecima、正则表达式

#Java-常用API-BigInteger、BigDecima、正则表达式

1.BigInteger BigInteger可以表示非常大范围的整数&#xff0c;理论上来说无限大 a.构造方法 构造方法说明public BigInteger(int num, Random rnd)获取随机大整数,范围 : [0 ~ 2的num次方 - 1]public BigInteger(String val)获取指定的大整数public BigInteger(String val,…
阅读更多...
机器学习3

机器学习3

KNN算法分类 K-近邻算法&#xff08;K-Nearest Neighbors&#xff0c;简称KNN&#xff09;,根据K个邻居样本的类别来判断当前样本的类别;如果一个样本在特征空间中的k个最相似(最邻近)样本中的大多数属于某个类别&#xff0c;则该类本也属于这个类别 欧氏距离和曼哈顿距离&am…
阅读更多...
微信小程序组件详解：text 和 rich-text 组件的基本用法

微信小程序组件详解：text 和 rich-text 组件的基本用法

微信小程序组件详解：text 和 rich-text 组件的基本用法 引言 在微信小程序的开发中，文本展示是用户界面设计中不可或缺的一部分。无论是简单的文本信息，还是复杂的富文本内容，text 和 rich-text 组件都能够帮助我们实现这些需求。本文将详细介绍这两个组件的基本用法，包…
阅读更多...
《探索 C++：一门强大且多功能的编程语言》

《探索 C++：一门强大且多功能的编程语言》

《探索 C&#xff1a;一门强大且多功能的编程语言》 在编程的广阔世界里&#xff0c;C 无疑是一颗璀璨的明星&#xff0c;它以其高性能、丰富的特性和广泛的应用领域&#xff0c;吸引着无数开发者投身其中。今天&#xff0c;就让我们一同深入探索一下这门令人着迷的编程语言吧。…
阅读更多...
AI Prompt Engineering

AI Prompt Engineering

AI Prompt Engineering 简介 Prompt Engineering, 提示工程&#xff0c;是人工智能领域的一项技术&#xff0c;它旨在通过设计高效的提示词&#xff08;prompts&#xff09;来优化生成式 AI&#xff08;如 GPT、DALLE 等&#xff09;的输出。提示词是用户与生成式 AI 交互的核…
阅读更多...
最新文章

Copyright @ 2022~2023