【数据结构进阶】手撕红黑树

🕗 发布于 2024-08-02 02:03 数据结构 学习 c++

在这里插入图片描述

🔥个人主页： Forcible Bug Maker
🔥专栏： C++ || 数据结构

🌈前言

本篇博客主要内容：红黑树的介绍，以及底层代码逻辑和实现。

刚刚接触编程的时候就听说有的大厂HR会让手撕红黑树。心中一直对这个数据结构保持着敬畏和向往，今天在将其撕出来后，用本篇博客加以记录，望周知。

🔥红黑树的概念

红黑树，也是一种二叉搜索树，但再每个结点上增加一个存储位置表示结点的颜色，可以是RED（红）或BLACK（黑）。通过对任何一条根到叶子的路径上各个结点的着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
在这里插入图片描述
一颗红黑树，是具有如下性质的二叉搜索树：

每个结点不是红色就是黑色
根结点是黑色的
如果一个结点是红色，则它的两个孩子结点是黑色（即不会有连续的红结点）
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的（此处的叶子结点指的是空结点NIL）

其中，3和4是最重要的两点。

🔥手撕红黑树

红黑树结点的定义

红黑树的结点包含四个成员变量，模板类型T：可以存储K或者pair<K,V>类型，便于后期封装；三个指针：分别为指向左孩子结点的指针，指向右孩子结点的指针，指向父结点的指针；最后变量_col：枚举类型，可以存RED和BLACK。

enum Color
{
RED,
BLACK
};

template<class T>
struct RBTreeNode
{
RBTreeNode<T>(const T& t)
: _data(t)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
};

红黑树主体需要实现的成员函数

// T: 可能是键值对<key,value>
//    可能是一个key
// 不论节点中存储的是<key, value> || key, 都是按照key来进行比较的
// KeyOfValue: 提取data中的Key
template<class K, class T, class KeyOfValue>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;
public:
RBTree() = default;

RBTree(const RBTree<K, T, KeyOfValue>& t);

// 插入值为data的节点
// 返回值含义：iterator代表新插入节点   bool：代表释放插入成功
std::pair<iterator, bool> Insert(const T& data);

// Begin和End迭代器
iterator Begin();
iterator End();

// 红黑树是否为空，是返回true，否则返回false
bool Empty()const;

// 返回红黑树中有效节点的个数
size_t Size()const;

// 将红黑树中的有效节点删除
void Clear();

// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
bool IsValidRBTRee()

// 在红黑树中查找data，存在赶回该节点对应的迭代器，否则返回End()
iterator Find(const T& data);

~RBTree();
private:
Node* _root;
};

红黑树的插入

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

首先是按照二叉搜索树的方式插入结点
检测插入结点后，红黑树的性质是否遭到破坏
因为新结点的默认颜色是红色，因此：如果父结点的颜色是黑色，就没有违反性质，不需调整；担当插入结点的父节点也是红色时，就违反了性质3（不能有连在一起的红结点），此时需要对红黑树分情况讨论调整：

约定：cur为当前结点，p为父节点，g为祖父结点，u为叔叔结点。

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

在这里插入图片描述
解决方式：将p，u变成黑色，g变成红色，然后把g改成cur，继续向上调整。

情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑（这里需要做的其实就和AVL树中的单旋很像了，我们需要把u结点旋转下来，以维持平衡）

在这里插入图片描述

p为g的左孩子，cur为p的左孩子，进行右单旋；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋。p变黑色，g变红色。

情况三（情况二的变体）：cur为红，p为红，g为黑，u不存在/u存在且为黑（其实就是双旋，除了不用调整平衡因子，其他的和AVL树的双旋并无差别）

在这里插入图片描述

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转。然后就转换成了情况2。

针对每种情况进行相应的处理即可：

// 插入值为data的节点
// 返回值含义：iterator代表新插入节点   bool：代表释放插入成功
std::pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr) {
_root = new Node(data);
_root->_col = BLACK;
return std::make_pair(iterator(_root, _root), true);
}

KeyOfValue kov;

Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (kov(cur->_data) < kov(data)) {
parent = cur;
cur = cur->_right;
}
else if (kov(cur->_data) > kov(data)) {
parent = cur;
cur = cur->_left;
}
else return std::make_pair(iterator(cur, _root), false);
}

cur = new Node(data);
Node* InsertNode = cur;
if (kov(parent->_data) < kov(data)) {
parent->_right = cur;
cur->_parent = parent;
}
else {
parent->_left = cur;
cur->_parent = parent;
}

while (parent && parent->_col == RED && cur->_col == RED) {
Node* grandParent = parent->_parent;
Node* uncle = nullptr;
//   g
// p   u
if (grandParent->_left == parent) {
uncle = grandParent->_right;
if (uncle == nullptr || uncle->_col == BLACK) {
if (parent->_left == cur) {
RotateR(grandParent);
parent->_col = BLACK;
grandParent->_col = RED;
}
else {
RotateL(parent);
RotateR(grandParent);
cur->_col = BLACK;
grandParent->_col = RED;
}
break;
}
else {
parent->_col = BLACK;
grandParent->_col = RED;
uncle->_col = BLACK;
cur = grandParent;
parent = grandParent->_parent;
}
}
//   g
// u   p
else {
uncle = grandParent->_left;
if (uncle == nullptr || uncle->_col == BLACK) {
if (parent->_right == cur) {
RotateL(grandParent);
parent->_col = BLACK;
grandParent->_col = RED;
}
else {
RotateR(parent);
RotateL(grandParent);
cur->_col = BLACK;
grandParent->_col = RED;
}
break;
}
else {
parent->_col = BLACK;
grandParent->_col = RED;
uncle->_col = BLACK;
cur = grandParent;
parent = grandParent->_parent;
}
}
}
_root->_col = BLACK;
return std::make_pair(iterator(InsertNode, _root), true);
}

在红黑树中，由于不用调节平衡因子，双旋的复杂度大大降低，直接使用单旋并在插入过程中调整结点颜色即可。
旋转的具体内容在AVL树中（【数据结构进阶】AVL树）讲解过，这里就不赘述了。

// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;

if (subRL)
subRL->_parent = parent;
subR->_left = parent;
subR->_parent = parentParent;
parent->_right = subRL;
parent->_parent = subR;

if (parentParent == nullptr) {
_root = subR;
}
else {
if (parentParent->_left == parent) {
parentParent->_left = subR;
}
else
parentParent->_right = subR;
}
}

// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;

if (subLR)
subLR->_parent = parent;
subL->_right = parent;
subL->_parent = parentParent;
parent->_left = subLR;
parent->_parent = subL;

if (parentParent == nullptr) {
_root = subL;
}
else {
if (parentParent->_left == parent) {
parentParent->_left = subL;
}
else
parentParent->_right = subL;
}
}

find

和二叉搜索树的查找规则相同。

// 在红黑树中查找data，存在赶回该节点对应的迭代器，否则返回End()
iterator Find(const T& data)
{
KeyOfValue kov;
Node* cur = _root;
while (cur) {
if (kov(cur->_data) < kov(data))
cur = cur->_right;
else if (kov(cur->_data) > kov(data))
cur = cur->_left;
else return iterator(cur, _root);
}
return iterator(nullptr, _root);
}

Empty和Size

Empty接口函数用来判断树是否为空；Size用来计算返回树结点的个数。

// 红黑树是否为空，是返回true，否则返回false
bool Empty()const
{
return _root == nullptr;
}
// 返回红黑树中有效节点的个数
size_t Size()const
{
return _Size(_root);
}

size_t _Size(Node* root)
{
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}

拷贝构造

RBTree(const RBTree<K, T, KeyOfValue>& t)
{
_root = _Copy(t._root);
}

Node* _Copy(Node* root)
{
if (root == nullptr)return nullptr;
Node* newRoot = new Node(root->_data);
newRoot->_left = _Copy(root->_left);
newRoot->_right = _Copy(root->_right);
return newRoot;
}

析构函数和clear

// 将红黑树中的有效节点删除
void Clear()
{
_Destroy(_root);
_root = nullptr;
}

~RBTree()
{
_Destroy(_root);
_root = nullptr;
}

void _Destroy(Node* root)
{
if (root == nullptr)return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}

检测是否为合法红黑树

在IsValidRBTRee中，首先算出一条路径上的黑结点个数digit_black，然后在每条路径递归到空结点时判断黑结点个数是否相等，即可验证性质4（所有路径上黑结点个数相等）；递归的过程中，判断当前结点和父节点的颜色是否同时为红，即可验证性质3（没有连续的红结点）

// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
bool IsValidRBTRee()
{
if (_root == nullptr)
return true;
Node* cur = _root;
size_t digit_black = 0;
while (cur) {
if (cur->_col == BLACK)
++digit_black;
cur = cur->_left;
}
return _IsValidRBTRee(_root, digit_black, 0);
}

bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
{
if (pRoot == nullptr) {
if (blackCount == pathBlack)
return true;
else return false;
}
if (pRoot->_col == RED && pRoot->_parent->_col == RED) {
return false;
}
if (pRoot->_col == BLACK) {
return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack + 1)
&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack + 1);
}
else {
return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)
&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
}
}

Begin和End

这两个函数用于获取红黑树的头对象和尾迭代器。

// Begin和End迭代器
iterator Begin() 
{
return iterator(_LeftMost(), _root);
}
iterator End()
{
return iterator(nullptr, _root);
}

// 获取红黑树最左侧节点
Node* _LeftMost()
{
if (_root == nullptr)
return nullptr;
Node* parent = _root;
Node* cur = parent->_left;
while (cur) {
parent = cur;
cur = cur->_left;
}
return parent;
}

红黑树的迭代器接口

迭代器的好处是可以方便遍历，使数据结构的底层实现变的透明，从而降低代码编写的复杂程度。

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;

RBTreeIterator(Node* pNode,Node* root)
: _pNode(pNode)
,_root(root)
{}

// 让迭代器具有类似指针的行为
Ref operator*();
Ptr operator->();

// 然迭代器可以移动：前置/后置++  
Self& operator++();
Self operator++(int);

// 然迭代器可以移动：前置/后置-- 
Self& operator--();
Self operator--(int);

// 让迭代器可以比较
bool operator!=(const Self& s)const;
bool operator==(const Self& s)const;

private:
Node* _pNode;
Node* _root;
};

* 解引用和 -> 访问

// 让迭代器具有类似指针的行为
Ref operator*()
{
return _pNode->_data;
}
Ptr operator->()
{
return &(_pNode->_data);
}

operator++()

二叉树的中序遍历并不难实现，但是要实现从任意一个结点按中序遍历跑到下一个结点，这就有相当难度了。
具体逻辑为：

右子树不为空，访问右子树的最左结点。
右子树为空（代表当前结点所在子树访问完了），沿着到根节点的路线，孩子是父亲左的那个祖先结点，就是下一个要访问的结点。

// 迭代器可以移动：前置/后置++  
Self& operator++()
{
if (_pNode->_right) {
_pNode = _pNode->_right;
while (_pNode->_left) 
_pNode = _pNode->_left;
}
else {
Node* cur = _pNode;
Node* parent = cur->_parent;
while (parent && cur == parent->_right) {
cur = parent;
parent = parent->_parent;
}
_pNode = parent;
}
return *this;
}

Self operator++(int)
{
Node* rem = _pNode;
if (_pNode->_right) {
_pNode = _pNode->_right;
while (_pNode->_left)
_pNode = _pNode->_left;
}
else {
Node* cur = _pNode;
Node* parent = cur->_parent;
while (parent && cur == parent->_right) {
cur = parent;
parent = parent->_parent;
}
_pNode = parent;
}
return Self(rem);
}

operator- - ()

这时候要判断当前迭代器是否指向尾End()，同时判断树是否为空，这就要用到传入迭代器对象中的_root了。在找到End()的前一个结点之后，按照和operator++()相反的逻辑即可实现operator--()。
具体逻辑为：

左子树不为空，访问左子树的最右结点。
左子树为空（代表当前结点所在子树访问完了），沿着到根结点的路线，孩子是父亲右的那个祖先结点，就是下一个要访问的结点。

// 迭代器可以移动：前置/后置-- 
Self& operator--()
{
if (_pNode == nullptr) {
if (_root == nullptr)
assert(false);
Node* parent = _root;
Node* cur = parent->_right;
while (cur) {
parent = cur;
cur = cur->_right;
}
_pNode = parent;
return *this;
}
if (_pNode->_left) {
_pNode = _pNode->_left;
while (_pNode->_right)
_pNode = _pNode->_right;
}
else {
Node* cur = _pNode;
Node* parent = cur->_parent;
while (parent && cur == parent->_left) {
cur = parent;
parent->_parent;
}
_pNode = parent;
}
return *this;
}

Self operator--(int)
{
if (_pNode == nullptr) {
if (_root == nullptr)
assert(false);
Node* parent = _root;
Node* cur = parent->_right;
while (cur) {
parent = cur;
cur = cur->_right;
}
_pNode = parent;
return Self(nullptr);
}
Node* rem = _pNode;
if (_pNode->_left) {
_pNode = _pNode->_left;
while (_pNode->_right)
_pNode = _pNode->_right;
}
else {
Node* cur = _pNode;
Node* parent = cur->_parent;
while (parent && cur == parent->_left) {
cur = parent;
parent->_parent;
}
_pNode = parent;
}
return Self(rem);
}

迭代器比较相等

底层就是用指针作比较。

// 让迭代器可以比较
bool operator!=(const Self& s)const
{
return _pNode != s._pNode;
}

bool operator==(const Self& s)const
{
return _pNode == s._pNode;
}

🌈结语

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( $log_2 N$ )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
红黑树的底层实现到这里就要结束了，本篇的数据结构较为复杂，模板的使用也有很多容易出错的点，需要多加体会。感谢大家的支持♥

原文地址：https://blog.csdn.net/2303_79329831/article/details/140778581

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

上一篇：深入解析 LabelImage：图像标注工具的全面指南
下一篇：Redis的优缺点

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

【数据结构进阶】手撕红黑树

目录

🌈前言

🔥红黑树的概念

🔥手撕红黑树

红黑树结点的定义

红黑树主体需要实现的成员函数

红黑树的插入

find

Empty和Size

拷贝构造

析构函数和clear

检测是否为合法红黑树

Begin和End

红黑树的迭代器接口

* 解引用和 -> 访问

operator++()

operator- - ()

迭代器比较相等

🌈结语

相关文章