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++如何通过Qt反射机制实现数据类序列化

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类，并对数据类进行存储、打印、调试等操作。由于数据类
阅读更多...
Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
C/C++错误信息处理的常见方法及函数

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,：本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例：2. strerror()示例：3. perror(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2