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

🕗 发布于 2024-07-25 23:03 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;
}
else
return false;
}
cur = new Node(kv);

//新增节点，颜色为红色
cur->_col = RED;

//链接时要判断链接在parent的左还是右
if (parent->_kv.first > kv.first)
parent->_left = cur;
else
parent->_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;
}
else
return false;
}
cur = new Node(kv);

//新增节点，颜色为红色
cur->_col = RED;

//链接时要判断链接在parent的左还是右
if (parent->_kv.first > kv.first)
parent->_left = cur;
else
parent->_right = cur;

cur->_parent = parent;

while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//    g
// p     u
if (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     p
Node* 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;
else
return 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;
}
else
return false;
}
cur = new Node(kv);

//新增节点，颜色为红色
cur->_col = RED;

//链接时要判断链接在parent的左还是右
if (parent->_kv.first > kv.first)
parent->_left = cur;
else
parent->_right = cur;

cur->_parent = parent;

while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//    g
// p     u
if (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     p
Node* 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;
else
ppNode->_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;
else
ppNode->_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( $log_2 N$ )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

原文地址：https://blog.csdn.net/2301_77900444/article/details/140680877

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：SpringBoot自动配置（面试重点）
下一篇：Layui---输入事件

excel如何快速选中某个数字或者某串数字
鼠标光标放在某个数字或者某串数字的末尾，进行双击鼠标左键即可（就会选中当前鼠标光标前相邻的所有数字）：
阅读更多2024-09-17
面试官问：请描述一次你成功解决问题的经历？
面试官为什么要这么问？面试官问你描述一次成功解决问题的经历，主要是为了评估你的几个关键方面：问题解决能力：了解你在面对挑战时的思维方式和应对策略。决策能力：考察你在压力下做出明智决定的能力。沟通技巧：
阅读更多2024-09-17
VLMEvalKit 评测实践:InternVL2 VS Qwen2VL
多模态技术的突破，正在改变我们理解和交互世界的方式。无论是强大的感知能力、复杂的推理分析，还是图文融合的创新应用，InternVL2 与 Qwen2-VL 展现了大模型的无限可能。
阅读更多2024-09-17
mybatis开启日志
步骤很详细，直接上教程……
阅读更多2024-09-17
MySQL——数据库的高级操作（一）数据备份与还原（1）数据的备份
MySQL——数据库的高级操作（一）数据备份与还原（1）数据的备份
阅读更多2024-09-17
Blender渲染太慢怎么办？blender云渲染已开启
此次，渲染101云渲染农场正式加入了对Blender的全面支持，涵盖Blender的所有版本，不论是较新的Blender 4.0还是早期版本，都可轻松对接渲染101平台服务。不论是小型独立项目还是大型
阅读更多2024-09-17
ubuntu安装mysql 8.0忘记root初始密码，如何重新修改密码
修改my.cnf文件，在文件新增 skip-grant-tables，在启动mysql时不启动grant-tables，授权表。5.注释掉skip-grant-tables后重启mysql。2、修改m
阅读更多2024-09-17
JVM面试真题总结（十一）
总的来说，Java内存模型主要解决了多线程环境下共享数据的一致性、可见性等问题，是Java并发编程的基础。这种模型的好处是，由于启动类加载器是最顶部的加载器，因此它加载的都是最可信任的类库（Java的
阅读更多2024-09-17
Ubuntu 软件仓库镜像使用帮助
选择镜像。
阅读更多2024-09-17
用于稀疏自适应深度细化的掩码空间传播网络 CVPR2024
图像引导的深度补全是一项通过利用稀疏深度测量和RGB图像来估计密集深度图的任务；它通过估算深度来填充未测量的区域。由于许多深度传感器（如LiDAR和飞行时间相机（ToF））只能提供稀疏的深度图，这项任
阅读更多2024-09-17

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

目录

前言

一，红黑树的概念

二，红黑树的性质

三，红黑树节点的定义

四，红黑树的插入操作

4.1 第一步

4.2 第二步

4.3 插入操作的完整代码

五，红黑树的验证

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

五，红黑树与AVL树的比较

相关文章