【C++笔记】红黑树

embedded/2025/1/20 2:08:43/

前言

各位读者朋友们大家好！上期我们讲了二叉搜索树之一——AVL树，这一期我们继续讲解另一种二叉搜索树——红黑树。

目录

  • 前言
  • 一. 红黑树的概念
    • 1.1 红黑树的规则
    • 1.2 红黑树如何确保最长路径不超过最短路径的两倍
    • 1.3 红黑树的效率
  • 二. 红黑树的实现
    • 2.1 红黑树的结构
    • 2.2 红黑树的插入
      • 2.2.1 红黑树插入的大致过程
      • 2.2.2 情况一：只变色
      • 2.2.3 情况二：单旋+变色
      • 2.2.4 情况三：双旋+变色
      • 2.2.5 插入的代码实现
    • 2.3 红黑树的验证
  • 三. 红黑树和AVL树对比
  • 结语

一. 红黑树的概念

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

1.1 红黑树的规则

  1. 每个节点不是黑色就是红色
  2. 根节点一定是黑色
  3. 如果一个节点是红色，则她的两个孩子一定是黑色，也就是说，任意一条连续的路径不允许连续出现两个红色节点
  4. 对于任意一个节点，从该节点到其所有NULL节点的所有简单路径上的黑色节点个数相同
    在这里插入图片描述
    如上就是一棵红黑树，根节点是黑色的，任意一条路径上没有连续的两个红色节点，从根节点到NULL节点一共有9条路径，每一条路径上都有相等个数的黑色节点。

1.2 红黑树如何确保最长路径不超过最短路径的两倍

在这里插入图片描述
综合红黑树的规则来看，理论上全黑最短路径和一黑一红节点的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL节点的路径长度为x,那么bh(black height) <= h <= 2*bh。

1.3 红黑树的效率

假设N是红黑树节点的个数，h为最短路径的长度，那么2h-1 <= N <= 22h-1,由此推出，h接近于logN，也就是意味着红黑树的增删改查的最坏情况就是走最长路径2 * logN，时间复杂度还是O(logN)。
总体来说，红黑树比AVL树要抽象一点，AVL树通过高度差更加直观的控制了平衡，红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们的效率都是logN级别的，但是相对而言，插入相同个数的节点，红黑树旋转的次数更少，因此它的平衡的控制没有AVL树那么严格。

二. 红黑树的实现

2.1 红黑树的结构

// 枚举值表示颜色
enum Colour
{RED,BLACK
};
// 这里我们默认按key/value结构实现 
template<class K, class V>
struct RBTreeNode
{// 这里更新控制平衡也要加入parent指针 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){}
};
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

2.2 红黑树的插入

2.2.1 红黑树插入的大致过程

  1. 插入一个值按照二叉搜索树的规则进行插入，插入后我们只需检查是否符合红黑树的4条规则。
  2. 如果是空树插入，则插入的新节点是黑节点；如果是非空树插入，新增节点一定是红色节点，因为非空树插入，新增黑色节点就违反了规则4，规则4是很难维护的。
  3. 非空树插入后，新增节点一定是红色节点，如果父亲节点是黑色节点，没有违反任何规则，插入结束。
  4. 非空树插入后，新增节点一定是红色节点，如果父亲节点是红色节点，就违反了规则3 在这里插入图片描述

因此根据uncle的颜色和是否存在分以下情况处理：

2.2.2 情况一：只变色

p为红色节点，g为黑色节点，叔叔节点存在且为红色节点
在这里插入图片描述
在这里插入图片描述
在这种情况下，无论c是p的左还是右，p是g的左还是右，都是采取变色的处理方式
更新完一次后，需要继续向上更新处理。
g是红色，如果g的父亲还是红色，那么就还需要继续处理；如果g的父亲是黑色，则处理结束；如果g就是整棵树的根，再把g变回黑色。
我们切到抽象图来看一下：
在这里插入图片描述
代码实现：

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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}// 链接父亲cur->_parent = parent;while (parent && parent->_col == RED)// 确保parent存在，如果cur是根节点，parent就是空指针{Node* grandfather = parent->_parent;if (parent == grandfather->_left){//   g // p    uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)// 叔叔存在且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上更新cur = grandfather;parent = cur->_parent;}}else{//   g // u    pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上更新cur = grandfather;parent = cur->_parent;}}}_root->_col = BLACK;// 保证根节点始终为黑色return true;
}

2.2.3 情况二：单旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c一定是新增节点（如果c是变色变上来的，那么路径上至少有两个黑节点（g和变色的节点），但是u不存在，路径上黑色节点个数不相等，所以c一定是新增节点）；u存在且为黑，则c一定不是新增的，c之前是黑色的，是在c的子树中插入

  • 右单旋（c是p的左，p是g的左）
    在这里插入图片描述
  • 左单旋（c是p的右，p是g的右）
    在这里插入图片描述
    以上两种情况，是变色之后继续向上调整产生的，旋转变色之后就不需要继续向上调整，因为新的根节点是黑色，不可能出现连续两个红色节点了。
    代码实现：
if (cur == parent->_left)//右单旋
{RotateR(grandfather);parent->_col =BLACK;grandfather->_col = RED;
}
if (cur == parent->_right)//左单旋
{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;
}

2.2.4 情况三：双旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c一定是新增节点，u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况一，变色将c从黑色变为红色，更新上来的。

  • 左右双旋
    在这里插入图片描述
    从结果来看，整个旋转和变色的过程是p为旋转点左单旋，g为旋转点右单旋，c变成子树的根，a变成p的右子树，b变成g的左子树，p和g分别变成c的左右子树，c变黑，g变红。
    以上这种情况是左右双旋，即c是p的右，p是g的左，另一种情况是c是p的左，p是g的右，要先以p为旋转点右单旋，再以g为旋转左单旋。
  • 右左双旋
    在这里插入图片描述

这样处理完之后不需要继续向上更新，因为根变成黑色节点了。

2.2.5 插入的代码实现

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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}// 链接父亲cur->_parent = parent;while (parent && parent->_col == RED)// 确保parent存在，如果cur是根节点，parent就是空指针{Node* grandfather = parent->_parent;if (parent == grandfather->_left){//   g // p    uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)// 叔叔存在且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上更新cur = grandfather;parent = cur->_parent;}else// 叔叔不存在或者叔叔为黑{//    g //  p     u// cif (cur == parent->_left)//右单旋{RotateR(grandfather);parent->_col =BLACK;grandfather->_col = RED;}else{//    g //  p     u//     cRotateL(parent);RotateR(grandfather);// 变色cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//   g // u    pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上更新cur = grandfather;parent = cur->_parent;}else{//    g //  u     p//           cif (cur == parent->_right)//左单旋{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g //  u     p//      cRotateR(parent);RotateL(grandfather);// 变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;// 保证根节点始终为黑色return true;
}void RotateR(Node* parent)
{// subL当根节点，parent当subL的右子树，subLR当parent的右子树，注意所有的parent的处理Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;// 从下往上链接父节点if (subLR)// subL可能为空，为空就不需要处理父亲节点subLR->_parent = parent;Node* pParent = parent->_parent;// 父节点的父亲，便于后续链接parent->_parent = subL;if (parent == _root)// 如果调整的是整棵树的根{_root = subL;subL->_parent = nullptr;}else// 局部树，链接祖先{if (parent == pParent->_left)pParent->_left = subL;elsepParent->_right = subL;subL->_parent = pParent;}
}//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;// 从下往上链接父节点if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;parent->_parent = subR;if (parent == _root)// 调整的是整棵树的根{_root = subR;subR->_parent = nullptr;}else{if (parent == pParent->_left)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}
}

2.3 红黑树的验证

验证红黑树前两条规则很容易处理，3、4条规则处理起来有些麻烦
在这里插入图片描述
对于第三条规则，如果通过前序遍历找孩子验证起来会有些麻烦，要区分左孩子和右孩子，我们可以通过红色节点，看其父亲节点是不是红色节点来验证；对于第四条规则，我们可以通过一个形参记录从根节点到该节点的黑色节点的数量，通过递归处理，递归传形参，在递归建立的新的栈帧里，传递的形参不会被改变，再通过一个标准值，来比对每条路径黑色节点的个数是否相等。
在这里插入图片描述
每层栈帧中存储从根节点到当前节点的路径上黑色节点的个数

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)// 调用Check函数之前已经确保了根节点不是红色节点{cout << "出现两个连续的红色节点" << endl;return false;}if (root->_col == BLACK)++BLACKNum;return Check(root->_left, BLACKNum, refNum) && Check(root->_right, BLACKNum, refNum);
}

三. 红黑树和AVL树对比

AVL树是一颗绝对平衡的二叉搜索树，红黑树对比AVL树就没有那么平衡了。
在这里插入图片描述
在Debug模式下，二者插入同样的随机数，时间相差不大，由于AVL树绝对平衡，因此AVL树的高度要低于红黑树的高度，但是红黑树在插入过程中旋转的次数要少于AVL树，二者在Debug模式下搜索的效率也相差不大。
在这里插入图片描述
换到Release模式，搜索偶的效率得到了提升。

红黑树代码实现

结语

以上我们就讲完了红黑树的内容，感谢大家的阅读，希望对大家有所帮助，欢迎大家批评指正！


http://www.ppmy.cn/embedded/155352.html

相关文章

Linux的常用命令(一)

Linux的常用命令(一)

目录 一、文件处理命令 1.文件处理命令ls 2.文件处理命令cd 3.文件处理命令pwd 4.文件处理命令touch 5.文件处理命令mkdir 6.文件处理命令cp 7.文件处理命令mv 8.文件处理命令rm 9.文件处理命令cat 10.文件处理命令more 11.文件处理命令head 12.文件处理命令tail …
阅读更多...
大模型微调介绍-Prompt-Tuning

大模型微调介绍-Prompt-Tuning

提示微调入门 NLP四范式 第一范式 基于「传统机器学习模型」的范式&#xff0c;如TF-IDF特征朴素贝叶斯等机器算法. 第二范式 基于「深度学习模型」的范式&#xff0c;如word2vec特征LSTM等深度学习算法&#xff0c;相比于第一范式&#xff0c;模型准确有所提高&#xff0c…
阅读更多...
芝麻http/品易http/太阳http/极光http退市后，还有哪家好用推荐？

芝麻http/品易http/太阳http/极光http退市后，还有哪家好用推荐？

相信&#xff0c;已经有不少程序员朋友在讨论芝麻HTTP、品易HTTP、太阳HTTP和极光HTTP退市的消息。说实话&#xff0c;芝麻系HTTP代理服务商在代理IP圈子里可以说是有举足轻重的位置&#xff0c;曾经也是吸引了不少用户的青睐。2个月前它们的退市可以说让代理IP整个市场无论是用…
阅读更多...
.NET 学习：从基础到进阶的全面指南

.NET 学习：从基础到进阶的全面指南

.NET学习资料 .NET学习资料 .NET学习资料 在当今软件开发的广阔领域中&#xff0c;.NET 是一个备受瞩目的开发平台&#xff0c;以其强大的功能、跨平台的特性以及丰富的生态系统&#xff0c;吸引着众多开发者投身其中。无论是构建企业级应用、Web 应用还是移动应用&#xff0…
阅读更多...
【大数据2025】MapReduce

【大数据2025】MapReduce

MapReduce 基础介绍 起源与发展&#xff1a;是 2004 年 10 月谷歌发表的 MAPREDUCE 论文的开源实现&#xff0c;最初用于大规模网页数据并行处理&#xff0c;现成为 Hadoop 核心子项目之一&#xff0c;是面向批处理的分布式计算框架。基本原理&#xff1a;分为 map 和 reduce …
阅读更多...
构建安全防线：基于视频AI的煤矿管理系统架构创新成果展示

构建安全防线：基于视频AI的煤矿管理系统架构创新成果展示

前言 本文我将介绍一款AI产品的成果展示——“基于视频AI识别技术的煤矿安全生产管理系统”。这款产品是目前我在创业阶段和几位矿业大学的博士共同从架构设计、开发到交付的全过程中首次在博客频道发布, 我之前一直想写但没有机会来整理这套系统的架构, 因此我也特别感谢CSDN平…
阅读更多...
源码编译安装httpd 2.4，提供系统服务管理脚本并测试

源码编译安装httpd 2.4，提供系统服务管理脚本并测试

1.安装httpd wget https://downloads.apache.org/httpd/httpd-2.4.62.tar.gzbmcv tar -zxvf httpd-2.4.62.tar.gz cd httpd-2.4.62 2.安装依赖包 sudo yum install -y gcc make apr-devel apr-util-devel pcre-devel sudo yum groupinstall "Development Tools"…
阅读更多...
Redis 部署模式

Redis 部署模式

Redis 提供了三种部署模式&#xff1a;单兵模式、哨兵模式、和 集群模式&#xff0c;每种模式有不同的特点和适用场景。下面分别介绍这三种模式。 1. 单兵模式&#xff08;Standalone&#xff09; 单兵模式是最简单的 Redis 部署模式&#xff0c;适合对高可用性要求不高的场景…
阅读更多...
最新文章

Copyright @ 2022~2023