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++右移运算符的一个小坑及解决

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned
阅读更多...
C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2