拿捏红黑树（C++）

2024-06-06 07:20
文章标签 c++ 红黑树 拿捏

本文主要是介绍拿捏红黑树（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 前言
  • 一、红黑树介绍
  • 二、插入操作
  • 三、验证红黑树
  • 四、红黑树与AVL性能比较与应用
  • 五、总体代码
  • 总结

前言

我们之前介绍了一种AVL的高阶数据结构，在本篇文章中，我们将会介绍一种与AVL旗鼓相当的数据结构–红黑树。
我们并且会对它的部分接口进行模拟实现

一、红黑树介绍

AVL是保证左右高度不超过1，实现平衡。
红黑树是在每个节点存储位表示颜色，包括红色和黑色，并且保证最长路径的节点个数不超过最短节点路径的两倍，我们就可以达到一种近似平衡
在这里插入图片描述

性质

🌟每个节点颜色不是红色就是黑色
🌟根节点是黑色的
🌟如果一个节点是红色，那么它的孩子必须是黑色节点（不允许出现连续的红色节点）
🌟每条路径都包含相同数量的黑色节点（路径：根节点到空）
🌟空节点设置为黑色，这个节点也称为NIL节点

为什么这几条规则就可以保证最长路径的节点数量不超过最短路径节点数量的两倍呢？？

我们从极端场景分析：
最短路径：全黑节点
最长路径：一黑一红

二、插入操作

我们需要一个位置表示颜色，这里我们采用枚举（enum）的方式。

我们插入到节点是插入红色呢还是黑色呢？？

我们看一下主要的规则：每条路径都包含相同数量的黑色节点；不允许出现连续的红色节点。

如果我们插入黑色节点，每条路径都会受到影响，我们是很难控制调整的。
如果我们插入红色节点，不允许出现连续的红色节点。我们只是在一条路径上插入，只需要调整这条路径上的节点，保证不出现连续的红色节点就可以。

先把大框架实现。

enum Col
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Col  _col;//表示颜色pair<K, V>_kv;RBTreeNode(const pair<K, V>kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)//初始化为红色,_kv(kv){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

如何插入节点呢？？
1.按照二叉搜索树规则找到插入节点
2.进行颜色调整

我们插入的是红色节点，如果父亲节点的颜色也是红色，我们就需要进行调整。
如果父亲节点的颜色是黑色，我们就不需要进行处理，直接退出。

调整：
我们这里的关键是看叔叔
因为我们已经知道我们插入的节点是红色，并且父亲也是红色，爷爷节点必定是黑色。
我们唯一不确定的就是叔叔节点

uncle存在且为红

在这里插入图片描述

我们分析一下具象图

当a/b/c/d/e都为空时，cur就是新插入节点。
在这里插入图片描述

我们需要把p和u变黑，同时把g变黑
在这里插入图片描述

如果这个节点是根节点，我们就把g变黑。
否则cur=g，p=g->p;继续调整。（原来根是黑色，现在变为红色）

当c/d/e是包含一个黑色节点的子树

有四种情况
在这里插入图片描述

我们选择最简单的看一下，插入的位置有四个选择。
在这里插入图片描述

我们把p和u变黑，同时g变红

下图才是我们这种去情况的具象图，这种情况是由之前的情况调整过来的。
在这里插入图片描述

把p和u变黑，同时g变红
如果这个节点是根节点，我们就把g变黑。
否则cur=g，p=g->p;继续调整。（原来根是黑色，现在变为红色）

在这里插入图片描述
我们发现g就是根节点，我们把g变黑

在这里插入图片描述

我们发现现在每条路径上黑节点的数量增加了，由原来两个黑节点变为现在3个黑节点。
黑色节点的数量增加是在根节点增加的，根节点增加就相当于每条路径都增加。

uncle不存在，或者存在且为黑

在这里插入图片描述

如果u不存在，cur就是新增加点，我们通过之前的变色已经完成不了了。
在这里插入图片描述

我们这时就需要进行旋转，旋转方式还是按照AVL树的情况。
这个场景下我们需要右旋

在这里插入图片描述、
旋转完之后，进行变色，p变黑，g变红
在这里插入图片描述

如果是下面这种情况，我们就需要进行双旋之后，再进行变色
在这里插入图片描述

首先对p进行左旋
在这里插入图片描述

再对g进行右旋
在这里插入图片描述
最后进行变色，cur变为黑，g变为红
在这里插入图片描述

总结：
🌟我们新插入节点颜色是红色
🌟如果新插入节点的父亲节点是黑色，我们不进行调整，直接退出
🌟如果新插入节点的父亲节点是红色，此时关键看叔叔。
🌟如果叔叔存在且为红，将p和u变黑，g变红。判断g是否为根节点。如果为根节点，g变黑。否则继续调整。
我们不关心左右，p和u是g的左右都不收影响，cur是p的左右也不受影响。
🌟如果uncle不存在或者存在且为黑，调整完之后结束。原来根是黑色，现在根也是黑色，不影响
🌟p为g的左孩子，cur为p的左孩子，对g进行右单旋，p变黑，g变红
🌟p为g的右孩子，cur为p的右孩子，对g进行左单旋，p变黑，g变红
🌟p为g的左孩子，cur为p的右孩子，对p进行左单旋，对g进行右单旋，c变黑，g变红
🌟p为g的右孩子，cur为p的左孩子，对p进行右单旋，对g进行左单旋，c变黑，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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//颜色调整while (parent && parent->_col == RED){//因为parent存在且不是黑色节点，则parent一定不是根，一定存在。Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//左子树的左边if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//左子树的右边else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//右子树的右边if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//右子树的左边else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}_root->_col = BLACK;}return true;}

我们有可能需要大量判断是否为根节点的情况，我们直接在结尾处加上
_root->_col = BLACK;暴力处理

三、验证红黑树

我们如何进行验证是一颗红黑树呢？？
我们从主要的规则入手

🌟根节点是黑色的
🌟不允许出现连续的红色节点
🌟每条路径都包含相同数量的黑色节点

我们只需要判断这三条成立，就能保证最长路径的节点个数不超过最短节点路径的两倍，从而证明这就是一颗红黑树。

根是黑节点很好证明，其他两条呢？？

不允许出现连续红色节点,判断一个节点和它的父节点是否都是红色。
这里如果判断这个节点和它的孩子节点会很复杂。

每条路径都包含相同数量的黑色节点，我们可以选择其中一条路径，计算出有多少个黑色节点，从而判断其他路径的黑色节点数量。

bool  IsBalance(){if (_root && _root->_col == RED){cout << "根节点为红色" << endl;return false;}//参考值int level = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){level++;}cur = cur->_left;}return check(_root, 0, level);}//BlackNum不能加引用
bool check(Node* root, int BlackNum, int level)
{if (root == nullptr){if (BlackNum != level){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, level) && check(root->_right, BlackNum, level);
}

四、红黑树与AVL性能比较与应用

性能

红黑树和AVL都是高效的平衡二叉树，增删查改的时间复杂度为·O(logN).
红黑树不追求绝对平衡，只需要保证最长路径不超过最短路径的两倍。相对而言，降低了插入和旋转次数，所以在经常进行增删的结构中比AVL更优，红黑树的实现比较简单，实际应用中红黑树更多。

AVL高度logN，红黑树高度logN*2.红黑树搜索效率相对AVL差一点，但是logN足够小，可以忽略不计。
N=10亿。logN=30.

应用：
1.C++ STL库 – map/set、mutil_map/mutil_set
2.Java 库
3. linux内核
4.其他库

五、总体代码

#pragma onceenum Col
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Col  _col;pair<K, V>_kv;RBTreeNode(const pair<K, V>kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public: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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//颜色调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//左子树的左边if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//左子树的右边else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在，或者存在且为黑else{//右子树的右边if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//右子树的左边else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}_root->_col = BLACK;}return true;}//1.根节点是黑色//2.不包含连续的红色节点//3.每条路径都包含相同黑色节点bool  IsBalance(){if (_root && _root->_col == RED){cout << "根节点为红色" << endl;return false;}//参考值int level = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){level++;}cur = cur->_left;}return check(_root, 0, level);}void Inorder(){_Inorder(_root);}
private://BlackNum不能加引用bool check(Node* root, int BlackNum, int level){if (root == nullptr){if (BlackNum != level){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, level) && check(root->_right, BlackNum, level);}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right= subRL;if (subRL){subRL->_parent = parent;}subR->_left= parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}Node* _root = nullptr;
};

总结

以上就是今天要讲的内容，本文仅仅详细介绍了红黑树的特征，已经模拟实现了插入操作 。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘

这篇关于拿捏红黑树（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1035445。

相关文章

C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
c++中std::placeholders的使用方法

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1：部分参数绑定示例 2：参数重排序4. 注意事项5.
阅读更多...
使用C++将处理后的信号保存为PNG和TIFF格式

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...
使用C/C++调用libcurl调试消息的方式

使用C/C++调用libcurl调试消息的方式

《使用C/C++调用libcurl调试消息的方式》在使用C/C++调用libcurl进行HTTP请求时,有时我们需要查看请求的/应答消息的内容（包括请求头和请求体）以方便调试,libcurl提供了多种... 目录1. libcurl 调试工具简介2. 输出请求消息使用 CURLOPT_VERBOSE使用 C
阅读更多...
C++实现获取本机MAC地址与IP地址

C++实现获取本机MAC地址与IP地址

《C++实现获取本机MAC地址与IP地址》这篇文章主要为大家详细介绍了C++实现获取本机MAC地址与IP地址的两种方式,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实际工作中，项目上常常需要获取本机的IP地址和MAC地址，在此使用两种方案获取1.MFC中获取IP和MAC地址获取
阅读更多...
C/C++通过IP获取局域网网卡MAC地址

C/C++通过IP获取局域网网卡MAC地址

《C/C++通过IP获取局域网网卡MAC地址》这篇文章主要为大家详细介绍了C++如何通过Win32API函数SendARP从IP地址获取局域网内网卡的MAC地址,感兴趣的小伙伴可以跟随小编一起学习一下... C/C++通过IP获取局域网网卡MAC地址通过win32 SendARP获取MAC地址代码#i
阅读更多...
C++中使用vector存储并遍历数据的基本步骤

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库（STL）提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,：本文主要介绍C... 目录（1）容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌（基于哈希表）：‌容器适配器‌：（
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2