C++的红黑树

2024-05-24 01:36
文章标签 c++ 黑树

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

目录

基本概念

插入结点的颜色

判断性质是否破坏

调整方式

 u为g的右孩子

u存在且为红

u存在且为黑

u不存在

结论 

红黑树结点定义

代码实现

基本概念

1、红黑树是一种特殊的二叉搜索树，每个结点会增加一个存储位表示结点的颜色（红或黑）

2、红黑树通过对所有从根到叶子的路径上的各个结点的着色方式的限制，确保红黑树中没有一条路径会比其它路径长出两倍，从而使二叉搜索树接近平衡

3、AVL树是一个严格平衡（平衡因子，二叉树能做到的最好的平衡），而红黑树是一个近似平衡，插入100万个数据，AVL树会进行大量的旋转，形成的树可能是30层，但是红黑树的旋转会少一些，形成的树可能是60层，但是对于CPU而言其实二者差别也不大

4、红黑树有五个性质（紫色是重点）：

  1. 每个结点不是红色就是黑色
  2. 根结点是黑色的
  3. 如果一个结点是红色，则它的两个孩子结点都是黑色（一个黑结点的孩子可以是红也可以是黑的，不可以不存在连续的红红、可以存在连续黑红、红黑和黑黑的结点）
  4. 对于每个结点，该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点（一个结点向下的每条路径中的黑色结点相同，空结点也是黑色结点）（最难维护的规则）
  5. 每个叶子结点都是黑色的（红黑树中所指的叶子结点是空结点）

5、满足以上五条性质就能保证红黑树的最长路径 <= 最短路径 * 2

  • 最短路径（极端情况）：全黑（由性质4可得：其它路径中也有相同数目的黑色结点以及红色结点，但是全黑的路径中没有红色结点）
  • 最长路径（极端情况）：一黑一红（不算空结点）
  • 一个红黑树肯定有最长或最短路径，只不过不一定有以上的理想情况下的最短和最长路径，正常情况下最长路径小于最短路径的2倍，极端情况下最长路径可能还会等于最短路径的2倍（没有极端情况就矮子里挑将军了）

插入结点的颜色

问题：插入结点时还可以依据二叉搜索树的插入规则吗？插入结点应该都是什么颜色？

解释：可以且新插入的结点应该都是红色，因为插入结点的颜色是红色那么你只是可能违反性质3（如果一个结点是红色，则它的两个孩子结点都是黑色）：

        但是如果插入结点的颜色是黑色则一定违法性质4（对于每个结点，该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点）：

判断性质是否破坏

        规定cur表示新插入结点，p表示父结点（parent）、g表示爷爷结点（grandfather）、u表示叔叔结点（uncle）

问题：如何确认在插入新结点后，红黑树的性质是否被破坏？

解释：新结点的颜色为红色，如果新结点的父结点颜色为红色，则违法性质3，需要进行调整

补充：p一定为红，g一定为黑，因为新插入结点的颜色是红色，插入该结点导致需要调整只可能是因为该结点的插入导致性质3遭到了破坏，那么p结点一定为红，而g也肯定为黑，因为在新插入结点前整颗红黑树应该是没有错误的（跟AVL树旋转是一个道理）

调整方式

问题：发现红黑树性质被破坏后，如何进行调整？（后面还有更准确的划分）

①由上述内容可知，在性质被破坏时cur一定为红、p一定为红、g一定为黑，那么关键点就在于p的兄弟结点u，对u的关注点应该在于它的“位置 + 存在情况”

②u的位置：p为g的左孩子，u就是g的右孩子，p为g的右孩子，u就是g的左孩子

③u的存在情况：u存在且为黑色，u存在且为红色、u不存在

 u为g的右孩子

u存在且为红

解决办法：将p和u变为黑，g变为红（p和u替代了g保证路径上黑色结点数量不变）

遗留问题：

  • 如果g是根结点，那么在g变红后为了满足性质2，仅需要将g重新变为黑色即可
  • 如果g不是根结点，那么在g变红且g的父结点的颜色是黑色时，不需要继续向上调整
  • 如果g不是根结点，那么在g变红且g的父结点的颜色是红色时，就需要继续向上调整

注意事项：

1、不能在发现新插入结点导致违法性质3后将cur再变为黑，因为那样还不如规定插入结点的颜色为黑色但是那样又一定会违法性质4

2、p和u改变后不能让g仍然为黑，因为如果g不是根结点，那么也会违法性质4

关于cur：无论cur是p的左孩子还是右孩子，当u存在且为红时，调整时只需要调色即可

u存在且为黑

补充：下图演示的是u存在且为红在调整后，向上调节时遇到的u存在且为黑的情况，用一个例子将u存在且为红 + 向上调整 + u存在且为黑的情况都总结了

解决办法：先旋转（以g为旋转点进行LL右单旋），后变色（p变为黑，g变为红）

关于cur：

①上面的cur是p左孩子则以g为旋转点进行LL右单旋，p变黑g变红

②若cur是p的右孩子先以p为旋转点进行左单旋，后以g为旋转点进行右单旋，cur变黑g变红

（颜色改变没有先后顺序，只要发生改变即可，先旋转后变色只是为了理解变色原因）

u不存在

解决办法：先变色（p变为黑，g变为红），后旋转（以g为旋转点进行LL右单旋）

关于cur：

①上面的cur是p左孩子则以g为旋转点进行LL右单旋，p变黑g变红

②若cur是p的右孩子先以p为旋转点进行左单旋，后以g为旋转点进行右单旋，cur变黑g变红

（颜色改变没有先后顺序，只要发生改变即可，先旋转后变色只是为了理解变色原因）

u为g的右孩子的情况不再分析，通过最终代码自己画图感受，主要区别在于旋转方式的不同

结论 

  1. 每一次的调整都可能导致另一次红黑树性质的被破坏
  2. cur和parent均为红色是由“新增”或“向上调整”两种原因导致的，因此无论是这两种的哪一种，只有当cur和parent均不为红时才不需要继续调整（循环）
  3. 红黑树是否调整取决于cur和parent是否均为红，怎么调整取决于叔叔u的情况 + cur是p的哪个孩子

红黑树结点定义

// 结点颜色
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;						// 节点的颜色        
};
  • 演示的内容与最终代码中变量的名字存在区别

代码实现

#pragma once#include <iostream>
#include<vector>using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};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);cur->_col = RED; // 规定新增节点的颜色是红色if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 当parent指向的结点不为空，且parent指向的结点的颜色不为黑色就继续向上调整（因为cur和parent均为红可能是由新增和向上调整导致的，因此无论是这两种情况的哪一种，// 只有当cur和parent均不为红时才结束循环）while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//通过父亲找到爷爷，父亲的父亲信息是爷爷//红黑树的关键点在于判断叔叔的情况if (parent == grandfather->_left)//如果父亲是爷爷的左孩子，那么叔叔就只能是爷爷的右孩子//这里if中的叔叔一直都是爷爷的右孩子，不过还会存在为红、为黑、不存在的三种情况{Node* uncle = grandfather->_right;// 如果叔叔存在且叔叔的颜色是红色，则直接将叔叔和父亲的颜色都变为黑色，将爷爷的颜色变为红色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 防止修改颜色导致上方出现新的两个连续的红色结点，需要移动指针继续向上处理cur = grandfather;//cur指向爷爷结点parent = cur->_parent;//parent指向的是cur的父结点（cur向上走，parent也要向上走）}else // 叔叔不存在，或者存在且为黑{if (cur == parent->_left)//如果cur是父亲的左孩子，进行LL右单，旋转后将父亲的颜色变为黑，将爷爷的颜色变为红{//     g  //   p   u// c 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//如果父亲结点是爷爷结点的右孩子，那么叔叔结点就是爷爷结点的左孩子{Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;//不管最后整棵红黑树的根结点是什么颜色（因为向上调整可能会导致根结点颜色变为红色，也有可能根结点也颜色不变）//我们这里都直接重新将根结点的颜色设置为黑色，这样就不需要再在循环中去判断是否到达根结点return true;}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 (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}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 (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}}//对用户暴露的中序遍历红黑树接口void InOrder(){_InOrder(_root);cout << endl;}//判断红黑树是否平衡bool IsBalance(){//首先根结点颜色得为黑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 << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};//测试红黑树能否正常使用
void TestRBTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,8, 3, 1, 10, 6, 4, 7, 14, 13 };RBTree<int, int> t1;for (auto e : a){if (e == 10){int i = 0;}// 1、先看是插入谁导致出现的问题// 2、打条件断点，画出插入前的树// 3、单步跟踪，对比图一一分析细节原因t1.Insert({e,e});std::cout << "Insert:" << e << "->" << t1.IsBalance() << std::endl;}t1.InOrder();std::cout << t1.IsBalance() << std::endl;
}//测试红黑树对百万数据处理所需时间
void TestRBTree2()
{const int N = 1000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);//cout << v.back() << endl;}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();std::cout << t.IsBalance() << std::endl;
}

~over~

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


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

相关文章

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