拿捏红黑树（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++ 中的 if-constexpr语法和作用

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if（staticif）,：本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa
阅读更多...
C++中::SHCreateDirectoryEx函数使用方法

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1：创建单层目录示例 2：创建多级目录3. 关键注
阅读更多...
C++从序列容器中删除元素的四种方法

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque
阅读更多...
C++常见容器获取头元素的方法大全

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素（即第一个元素）是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa
阅读更多...
C++字符串提取和分割的多种方法

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示
阅读更多...
C++原地删除有序数组重复项的N种方法

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体：最多保留两次五、分析和代码实现5.1、问题分析5.
阅读更多...
C++ 各种map特点对比分析

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map（如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现：基于红黑
阅读更多...
C++中函数模板与类模板的简单使用及区别介绍

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中，模板是实现泛型编程
阅读更多...
利用Python和C++解析gltf文件的示例详解

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提
阅读更多...
C++快速排序超详细讲解

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2