【C++高阶数据结构】红黑树：全面剖析与深度学习
Zfox_ 2024-08-16 15:05:03 阅读 78
🌈 个人主页：Zfox_
🔥 系列专栏：C++从入门到精通
目录
🚀 前言：红黑树与AVL树的比较一： 🔥 红黑树的概念二： 🔥 红黑树的性质 三： 🔥 红黑树节点的定义和结构🚀 3.1 基本元素🚀 3.2 节点颜色🚀 3.3 构造函数🚀 3.4 红黑树节点的定义
四：🔥 红黑树的插入操作 五：🔥 红黑树的验证 六：🔥 红黑树的完整代码
🚀 前言：红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(
l
o
g
2
N
log_2 N
log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
一： 🔥 红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
二： 🔥 红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
三： 🔥 红黑树节点的定义和结构
🚀 3.1 基本元素
<code>_left：指向节点的左子节点的指针
_right：指向节点的右子节点的指针_parent：指向节点的父节点的指针_kv：一个结构体或配对（pair），包含节点的键值（key）和值（value）。这取决于红黑的具体用途，可能只包含键或包含键值对。_col：表示当前节点的颜色。
🚀 3.2 节点颜色
在上面的定义中，_col 成员变量用于表示节点的颜色，通过 Color 枚举类型来定义，可以是 RED 或 BLACK。
🚀 3.3 构造函数
初始化一个新节点时，通常需要一个构造函数，它接受一个键值对（或仅键），并设置节点的左子节点、右子节点、父节点和颜色（初始化为红色）
🚀 3.4 红黑树节点的定义
// 节点的颜色
enum Color{ RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _color(color)
{ }
RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
RBTreeNode<ValueType>* _pRight; // 节点的右孩子
RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给
出该字段)
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
}
思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
答案：优先增加黑色节点会破坏红黑树的默认规则和结构，而新插入红色节点可以通过调整来适应规则，不一定会破坏结构。
四：🔥 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索的树规则插入新节点
template<class ValueType>
class RBTree
{
//……
bool Insert(const ValueType& data)
{
PNode& pRoot = GetRoot();
if (nullptr == pRoot)
{
pRoot = new Node(data, BLACK);
// 根的双亲为头节点
pRoot->_pParent = _pHead;
_pHead->_pParent = pRoot;
}
else
{
// 1. 按照二叉搜索的树方式插入新节点
// 2. 检测新节点插入后，红黑树的性质是否造到破坏，
// 若满足直接退出，否则对红黑树进行旋转着色处理
}
// 根节点的颜色可能被修改，将其改回黑色
pRoot->_color = BLACK;
_pHead->_pLeft = LeftMost();
_pHead->_pRight = RightMost();
return true;
}
private:
PNode& GetRoot(){ return _pHead->_pParent;}
// 获取红黑树中最小节点，即最左侧节点
PNode LeftMost();
// 获取红黑树中最大节点，即最右侧节点
PNode RightMost();
private:
PNode _pHead;
};
2. 检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定 : cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
情况一: cur为红，p为红，g为黑，u存在且为红
cur和p均为红，违反了性质三，此处能否将p直接改为黑？
<code>解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。
情况二 : cur为红，p为红，g为黑，u不存在/u存在且为黑
p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色–p变黑，g变红
情况三 : cur为红，p为红，g为黑，u不存在 / u存在且为黑
解决方式： p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转则转换成了情况2
具体实现代码如下：
<code>bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
// 找到插入位置
Node* cur = _root, * parent = nullptr;
while (cur)
{
if (cur->_kv.first == kv.first) return false;
else if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
}
else {
parent = cur;
cur = cur->_left;
}
}
cur = new Node(kv);
//新增节点 颜色优先选择红色
cur->_col = RED;
if (kv.first > parent->_kv.first) parent->_right = cur;
else parent->_left = cur;
cur->_parent = parent;
// 1、parent不存在，cur就是根了，出去后把根处理成黑的
// 2、parent存在，且为黑
// 3、parent存在，且为红，继续循环处理
// 变色了之后持续网上处理
while (parent && parent->_col == RED) // 父亲颜色是红色就需要继续处理（来连续的红节点， 关键看叔叔）
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) // 父亲在爷爷的左边 右边就是对称的
{
Node* uncle = grandfather->_right;
// g
// p u
if (uncle && uncle->_col == RED) // 如果叔叔存在且为红色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = grandfather->_parent;
}
else { // 叔叔存在且为黑或者不存在 那么旋转+变色
// g
// p u
// c
// 单旋
if (cur == parent->_left)
{
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;
if (uncle && uncle->_col == RED) // 如果叔叔存在且为红色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = grandfather->_parent;
}
else { // 叔叔存在且为黑或者不存在 那么旋转+变色
// g
// u p
// c
// 单旋
if (cur == parent->_right)
{
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;
}
五：🔥 红黑树的验证
红黑树的检测分为两步：
检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质
具体代码如下：
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)
{
//cout << blackNum << endl;
if (refNum != blackNum)
{
cout << "存在黑色节点的数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在连续的红色节点" << '\n';
return false;
}
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
六：🔥 红黑树的完整代码
#pragma once
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#include <assert.h>
using namespace std;
enum Color
{
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;
Color _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:
RBTree() = default;
RBTree(const RBTree<K, V>& t)
{
_root = Copy(t._root);
}
RBTree<K, V>& operator=(RBTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~RBTree()
{
Destroy(_root);
_root = nullptr;
}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
// 找到插入位置
Node* cur = _root, * parent = nullptr;
while (cur)
{
if (cur->_kv.first == kv.first) return false;
else if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
}
else {
parent = cur;
cur = cur->_left;
}
}
cur = new Node(kv);
//新增节点 颜色优先选择红色
cur->_col = RED;
if (kv.first > parent->_kv.first) parent->_right = cur;
else parent->_left = cur;
cur->_parent = parent;
// 1、parent不存在，cur就是根了，出去后把根处理成黑的
// 2、parent存在，且为黑
// 3、parent存在，且为红，继续循环处理
// 变色了之后持续网上处理
while (parent && parent->_col == RED) // 父亲颜色是红色就需要继续处理（来连续的红节点， 关键看叔叔）
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) // 父亲在爷爷的左边 右边就是对称的
{
Node* uncle = grandfather->_right;
// g
// p u
if (uncle && uncle->_col == RED) // 如果叔叔存在且为红色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = grandfather->_parent;
}
else { // 叔叔存在且为黑或者不存在 那么旋转+变色
// g
// p u
// c
// 单旋
if (cur == parent->_left)
{
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;
if (uncle && uncle->_col == RED) // 如果叔叔存在且为红色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = grandfather->_parent;
}
else { // 叔叔存在且为黑或者不存在 那么旋转+变色
// g
// u p
// c
// 单旋
if (cur == parent->_right)
{
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;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
Node* Copy(Node * root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_kv);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
void Destroy(Node * root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
void InOrder()
{
_InOrder(_root);
}
int Height()
{
return _Height(_root);
}
// 检查是否是红黑树
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 << "存在连续的红色节点" << '\n';
return false;
}
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
int _Size(Node* root)
{
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
void RotateL(Node * parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* parent_parent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent_parent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else {
if (parent == parent_parent->_left) parent_parent->_left = subR;
else parent_parent->_right = subR;
subR->_parent = parent_parent;
}
}
void RotateR(Node * parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* parent_parent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent_parent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else {
if (parent == parent_parent->_left)
{
parent_parent->_left = subL;
}
else {
parent_parent->_right = subL;
}
subL->_parent = parent_parent;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << '\n';
_InOrder(root->_right);
}
Node* _root = nullptr;
};
void TestRBTree1()
{
RBTree<int, int> t;
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
t.InOrder();
cout << t.IsBalance() << endl;
}
以上就是红黑树的讲解与完整实现过程，红黑树因为其自平衡的特性，及通过节点颜色来操作其树形结构的特点，极大的提高了数据存储及处理的效率，需要我们好好掌握，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~😉
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。