【数据结构】红黑树相关知识详细梳理

🕗 发布于 2024-10-04 05:47 数据结构 算法 c++

1. 红黑树的概念

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

例如：

2. 红黑树的性质

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

如何理解以上性质呢：

首先，根据红黑树的主要特点：最长路径中节点个数不会超过最短路径节点
个数的两倍。在以上性质的约束下，我们可以假设出最长路径和最短路径的差值来看看他是否符合要求。例如：

可以看到，通过几条性质的约束，的确可以使最长路径中节点个数不会超过最短路径节点个数的两倍，从而达到整棵树的相对平衡。

3. 红黑树插入

和AVL树一样，在插入节点破坏树的平衡的情况下，红黑树也要进行旋转操作来维持树的平衡。那么什么情况下红黑树会进行旋转，如何旋转呢？

3.1 插入变色/旋转

在进行旋转操作之前，我们首先要决定插入节点的颜色：

黑色可以吗？根据性质4（对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点），如果我们将插入节点设为黑色，则一定会破坏规则，由于树形结构的路径具有唯一性，插入节点一定会违反性质4。

所以我们默认设定除根节点外的（性质2）插入节点为红色。

那么就有了以下几种情况：

情况1：

情况2：

情况3：

3.2删除

和AVL树一样，红黑树的删除比较复杂，掌握插入的原理就够用了，这里不再详细说明。

4. 红黑树模拟实现

4.1 红黑树结构：

首先为了方便封装map和set，我定义了一个头节点方便后续操作。

（头节点的父节点指向红黑树的根，左节点指向红黑树的最小值，右节点指向红黑树的最大值）

enum Color
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& data = T())//构造
:_data(data)
,_color(RED)//新节点默认插入红色
,_pParent(nullptr)
,_pLeft(nullptr)
,_pRight(nullptr)
{}

T _data;//数据
Color _color;//颜色
RBTreeNode* _pParent;//父节点
RBTreeNode* _pLeft;//左节点
RBTreeNode* _pRight;//右节点
};

template<class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
//默认构造
RBTree()
{
//为了后序封装map和set，本文在实现时给红黑树多增加了一个头节点
_pHead = new Node;
//可以特别把头节点设为黑色
_pHead->_color = BLACK;
_pHead->_pLeft = _pHead;
_pHead->_pRight = _pHead;
_pHead->_pParent = _pHead;
}
//析构
~RBTree()
{
Destroy(GetRoot());
delete _pHead;
}
//插入
bool Insert(const T& data);
//查找
Node* Find(const T& data);
//获取红黑树最左侧节点
Node* LeftMost();
//获取红黑树最右侧节点
Node* RightMost();
//检测是否为有效红黑树
bool IsValidRBTree();
private:
//检测是否为有效红黑树
bool _IsValidRBTree(Node* pRoot,size_t k,size_t blackcount);
//左单旋
void RotateL(Node* pParent);
//右单旋
void RotateR(Node* pParent);
//获取根节点
Node* GetRoot();
//析构
void Destroy(Node* pRoot);
private:
Node* _pHead;
};

4.2 构造/析构

//默认构造
RBTree()
{
//为了后序封装map和set，本文在实现时给红黑树多增加了一个头节点
_pHead = new Node;
//可以特别把头节点设为黑色
_pHead->_color = BLACK;
_pHead->_pLeft = _pHead;
_pHead->_pRight = _pHead;
_pHead->_pParent = _pHead;
}

//析构
~RBTree()
{
Destroy(GetRoot());
delete _pHead;
}

//析构
template<class T>
void RBTree<T>::Destroy(Node* pRoot)
{
if (pRoot == nullptr)
return;
Destroy(pRoot->_pLeft);
Destroy(pRoot->_pRight);
delete pRoot;
}

4.3 获取元素：

//查找
template<class T>
typename RBTree<T>::Node* RBTree<T>::Find(const T& data)
{
if (_pHead->_pParent == _pHead)
return nullptr;
Node* pcur = GetRoot();
while (pcur)
{
if (data == pcur->_data)
return pcur;
if (data > pcur->_data)
pcur = pcur->_pRight;
else
pcur = pcur->_pLeft;
}
return pcur;
}

//获取红黑树最左侧节点
template<class T>
typename RBTree<T>::Node* RBTree<T>::LeftMost()
{
if (GetRoot() == nullptr)
return nullptr;
return _pHead->_pLeft;
}

//获取红黑树最右侧节点
template<class T>
typename RBTree<T>::Node* RBTree<T>::RightMost()
{
if (GetRoot() == nullptr)
return nullptr;
return _pHead->_pRight;
}

//获取红黑树根节点
template<class T>
typename RBTree<T>::Node* RBTree<T>::GetRoot()
{
if (_pHead->_pParent == _pHead)
return nullptr;
return _pHead->_pParent;
}

4.4 旋转：

//左单旋
template<class T>
void RBTree<T>::RotateL(Node* pParent)
{
Node* subR = pParent->_pRight;
Node* subRL = subR->_pLeft;
Node* grand = pParent->_pParent;
subR->_pParent = grand;
//如果祖父节点不是头节点
if (grand != _pHead)
{
if (pParent == grand->_pRight)
grand->_pRight = subR;
else
grand->_pLeft = subR;
}
//如果祖父节点是头节点
else
{
grand->_pParent = subR;
}
subR->_pLeft = pParent;
pParent->_pParent = subR;
pParent->_pRight = subRL;
//如果subRL不为空
if (subRL)
subRL->_pParent = pParent;
//变色
pParent->_color = RED;
subR->_color = BLACK;
}

//右单旋
template<class T>
void RBTree<T>::RotateR(Node* pParent)
{
Node* subL = pParent->_pLeft;
Node* subLR = subL->_pRight;
Node* grand = pParent->_pParent;
//如果祖父节点不是头节点
subL->_pParent = grand;
if (grand != _pHead)
{
if (pParent == grand->_pRight)
grand->_pRight = subL;
else
grand->_pLeft = subL;
}
//如果祖父节点是头节点
else
{
grand->_pParent = subL;
}
subL->_pRight = pParent;
pParent->_pParent = subL;
pParent->_pLeft = subLR;
//如果subLR不为空
if (subLR)
subLR->_pParent = pParent;
//变色
pParent->_color = RED;
subL->_color = BLACK;
}

4.5 插入：

template<class T>
bool RBTree<T>::Insert(const T& data)
{

Node* pcur = GetRoot();
//如果树为空，只有头节点
if (pcur == nullptr)
{
//直接插入节点
Node* newnode = new Node(data);
_pHead->_pParent = newnode;
_pHead->_pLeft = newnode;
_pHead->_pRight = newnode;
newnode->_pParent = _pHead;
newnode->_color = BLACK;
//插入成功，返回true
return true;
}
//树不为空，按照搜索树规律找到插入位置
Node* parent = nullptr;
while (pcur)
{
//如果树中存在该元素，插入失败
if (data == pcur->_data)
return false;
parent = pcur;
if (data > pcur->_data)
pcur = pcur->_pRight;
else
pcur = pcur->_pLeft;
}
//在正确的位置插入节点
Node* newnode = new Node(data);
if (data > parent->_data)
parent->_pRight = newnode;
else
parent->_pLeft = newnode;
newnode->_pParent = parent;

//插入后检查红黑树结构是否需要调整
pcur = newnode;
Node* grand = nullptr;
Node* uncle = nullptr;
//以pcur为基准，循环向上调整
while (pcur!=GetRoot())
{
//更新父，叔节点
parent = pcur->_pParent;
grand = parent->_pParent;
uncle = nullptr;
//如果父节点颜色为黑，则不需要调整,跳出循环
if (parent->_color == BLACK)
{
break;
}
//父节点颜色为红，违反规则，需要调整
else
{
//此时祖父节点一定存在
if (grand->_pRight == parent)
uncle = grand->_pLeft;
else
uncle = grand->_pRight;

//如果叔节点存在
if (uncle)
{
//如果叔节点为红色
if (uncle->_color == RED)
{
//父，叔节点都变黑，祖父节点变红
parent->_color = BLACK;
uncle->_color = BLACK;
grand->_color = RED;
//如果祖父节点为根节点，把祖父节点变黑
if (grand == GetRoot())
grand->_color = BLACK;
//更新pcur
pcur = grand;
}
//如果叔节点为黑色
else
{
//如果叔节点为祖父节点的右节点
if (uncle == grand->_pRight)
{
//如果pcur为parent的右节点
if (pcur == parent->_pRight)
{
//对parent左单旋
RotateL(parent);
pcur->_color = RED;
}
//此时可看做pcur为parent的左节点的情况
RotateR(grand);
}
//如果叔节点为祖父节点的左节点
else
{
//如果pcur为parent的左节点
if (pcur == parent->_pLeft)
{
//对parent右单旋
RotateR(parent);
pcur->_color = RED;
}
//此时看看作pcur为parent的右节点的情况
RotateL(grand);
}
}
}
//如果叔节点不存在，则pcur一定为新增节点
else
{
//如果parent为grand的右节点
if (parent == grand->_pRight)
{
//如果pcur为parent的左节点
if (pcur == parent->_pLeft)
{
RotateR(parent);
pcur->_color = RED;
}
RotateL(grand);
}
//如果parent为grand的左节点
else
{
//如果pcur为parent的右节点
if (pcur == parent->_pRight)
{
RotateL(parent);
pcur->_color = RED;
}
RotateR(grand);
}
}
}
}
//更新最大最小值
Node* max = GetRoot();
while (max->_pRight)
{
max = max->_pRight;
}
Node* min = GetRoot();
while (min->_pLeft)
{
min = min->_pLeft;
}
//将最小给头节点的左
_pHead->_pLeft = min;
//将最大给头节点的右
_pHead->_pRight = max;
//统一返回真
return true;
}

4.6 检验红黑树：

//检测是否为有效红黑树
template<class T>
bool RBTree<T>::IsValidRBTree()
{
Node* pRoot = GetRoot();
if (pRoot == nullptr)
//空树是有效红黑树
return true;
//检查根节点是否为黑色
if (pRoot->_color != BLACK)
return false;

//记录任意一条路径的黑节点个数
size_t blackcount = 0;
Node* pcur = pRoot;
while (pcur)
{
if (pcur->_color == BLACK)
++blackcount;
pcur = pcur->_pRight;
}
size_t k = 0;
//调用子函数
return _IsValidRBTree(pRoot,k,blackcount);
}

//检测是否为有效红黑树
template<class T>
bool RBTree<T>::_IsValidRBTree(Node* pRoot, size_t k, size_t blackcount)
{
if (pRoot == nullptr)
{
//一条路径走完，检查黑色节点个数是否和一开始给的相同
if (k == blackcount)
return true;
else
return false;
}

//检查是否有连续的红色节点
Node* pParent = pRoot->_pParent;
//根节点为红色才判断pParent，不用考虑根节点
if ( pRoot->_color == RED && pParent->_color == RED)
//有连续的红色节点，违反规则
return false;
//如果pRoot为黑色节点，计数k+1
if (pRoot->_color == BLACK)
++k;
//继续向子树递归
return _IsValidRBTree(pRoot->_pLeft, k, blackcount) && _IsValidRBTree(pRoot->_pRight, k, blackcount);
}

5. 红黑树和AVL树的比较

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

6. 红黑树的应用

        1. C++ STL库 -- map/set、mutil_map/mutil_set。
        2. Java 库。
        3. linux内核。
        4. 其他一些库。

原文地址：https://blog.csdn.net/fulufulucode/article/details/142683691

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

上一篇：RocketMQ
下一篇：Java.数据结构.TreeSet

移动应用的界面配置-手机银行APP
设置登录界面为线性布局，组件垂直居中排列；设置主页为滚动模式，包括布局、添加背景图片；设置按钮样式，包括形状、边框线的宽度和颜色
阅读更多2024-10-05
79. 单词搜索
未终止，继续循环：记录当前已走过位置（等于work[k]），以当前位置向四周遍历，找到则往对应方向继续循环；四个方向都找不到匹配，则回退再继续遍历。v:代表等于work[k]且已走过的位置。找到了：终
阅读更多2024-10-05
设计一个 RESTful API：支持 CRUD 操作的实用指南
RESTful API 是一种基于 REST 架构风格的 Web 服务接口。它通过 HTTP 方法（如 GET、POST、PUT、DELETE）来操作资源。无状态性：每个请求都应包含所有必要的信息，服
阅读更多2024-10-05
idea 同一个项目不同模块如何设置不同的jdk版本
在IntelliJ IDEA中，可以为同一个项目中的不同模块设置不同的JDK版本。这样做可以让你在同一个项目中同时使用多个Java版本，这对于需要兼容多个Java版本的开发非常有用。通过以上步骤，你可
阅读更多2024-10-05
利用 Qt 和 MySQL 实现简单的数据库用户登录与创建功能
在以下应用程序中，实现了本地用户登录功能（如果有需要可以修改主机名来实现远程登陆），允许用户输入数据库的用户名和密码，并在成功登录后创建一个新的数据库和相关数据表。在实际开发中，可以考虑加强用户输入的
阅读更多2024-10-05
谈谈Java与python中的闭包
在计算机科学中，闭包是指一个函数以及其引用的周围环境（变量）所组成的整体。简单来说，闭包允许一个函数访问并操作其外部函数作用域中的变量，即使外部函数已经执行完毕。
阅读更多2024-10-05
Docker安装人大金仓（kingbase）关系型数据库教程
人大金仓数据库（KingbaseES）是由中国人民大学金仓公司研发的一款自主知识产权的关系型数据库管理系统。本章教程，主要介绍如何用Docker安装启动人大金仓（kingbase）关系型数据库。
阅读更多2024-10-05
MySQL高阶2004-职员招聘人数
第四步:第一个子查询从t1中选择"Senior"中小于或等于70000,第二个select子查询再从t2和t3中选择"Junior"出小于70000减去第一个s
阅读更多2024-10-05
华为OD机试真题---第k个排列
给定参数n，从1到n会有n个整数：1, 2, 3, ..., n。这n个数字共有n!种排列。按大小顺序升序列出所有排列的情况，并一一标记。给定n和k，返回第k个排列。
阅读更多2024-10-05
STL之stack&queue篇——探索C++ STL中的Queue与Stack——构建数据处理的基础框架
本文旨在深入探讨C++ STL中的queue与stack容器，从它们的基本概念、底层实现、成员函数到应用场景，全方位解析这两个容器的魅力所在。我们将通过生动的示例和详细的解释，帮助读者理解queue与
阅读更多2024-10-05