c++ 红黑树（自平衡二叉搜索树）

2024-09-01 03:28
文章标签 c++ 搜索 二叉 红黑树 平衡

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

目录

 红黑树的概念

红黑树的由来

红黑树的性质

红黑树结点的定义

红黑树的插入

情况一：插入结点的叔叔存在，且叔叔的颜色是红色。

情况二：插入结点的叔叔存在且颜色是黑色 / 叔叔不存在，

情况A：p为g的左孩子，cur为p的左孩子

情况B：p为g的右孩子，cur为p的右孩子

情况C：p为g的左孩子，cur为p的右孩子

情况D：p为g的右孩子，cur为p的左孩子

红黑树的验证

同样红黑树作为特别的AVL树也是禁止进行修改的！！！

 红黑树的概念

对于题目也可以大致猜出红黑树是一种什么类型的树，其是一种特殊的平衡二叉搜索树（AVL树）。其产生也是因为避免了AVL树中的单枝树的存在。从而整体上进行了优化。

之所以叫红黑树是因为：在每个结点上增加了一个存储位用于表示结点的颜色，这个颜色可以是红色的，也可以是黑色的，因此我们称之为红黑树。

红黑树的由来

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。

红黑树的性质

红黑树有以下五点性质：

  1. 每个结点不是红色就是黑色。
  2. 根结点是黑色的。
  3. 如果一个结点是红色的，则它的两个孩子结点是黑色的。
  4. 对于每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。
  5. 每个叶子结点都是黑色的（此处的叶子结点指定是空结点）。

由此还是可以引出一些疑惑的

比如：

红黑树如何确保从根到叶子的最长可能路径不会超过最短可能路径的两倍？ 

 其实从性质三我们可以得到一个信息：红黑树当中不会出现连续的红色结点，所以父子节点只有三种颜色情况：红--->黑，黑--->黑，黑--->红。而根据性质4又可以得出，从某一结点到其后代叶子结点的所有路径上包含的黑色结点的数目是相同的。

我们假设在红黑树中，从根到叶子的所有路径上包含的黑色结点的个数都是N个，那么最短路径就是全部由黑色结点构成的路径，即长度为N。

与之对应的最长可能路径就是由一黑一红结点构成的路径，该路径当中黑色结点与红色结点的数目相同，即长度为2N。

因此，红黑树从根到叶子的最长可能路径不会超过最短可能路径的两倍。

这里再解释一下性质5，这里的叶子结点不是传统意义上的叶子，不是下图中的25/74/78/86/90

 

实际上，在红黑树中真正被定义为叶子结点的，是那些空节点，如下图。

 

 

红黑树结点的定义

因为红黑树是一种特殊的AVL树（但少了平衡因子的存在），所以其结点的定义是在AVL树上加上新的成员变量，用于表示结点的颜色。

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){}
};

首先我们在默认构造上，默认构造结点的颜色默认情况下为红色

所以为什么构造结点时，默认将结点的颜色设置为红色？

这是因为：当我们向红黑树插入结点时，若我们插入的是黑色结点，那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个，即破坏了红黑树的性质4，此时我们就需要对红黑树进行调整。

若我们插入红黑树的结点是红色的，此时如果其父结点也是红色的，那么表明出现了连续的红色结点，即破坏了红黑树的性质3，此时我们需要对红黑树进行调整；但如果其父结点是黑色的，那我们就无需对红黑树进行调整，插入后仍满足红黑树的要求。

总的来说：

  • 插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整。
  • 插入红色结点，可能破坏红黑树的性质3，可能对红黑树进行调整。

权衡利弊后，我们在构造结点进行插入时，默认将结点的颜色设置为红色。

红黑树的插入

红黑树插入结点的逻辑分为三步：

  1. 按二叉搜索树的插入方法，找到待插入位置。
  2. 将待插入结点插入到树中。
  3. 若插入结点的父结点是红色的，则需要对红黑树进行调整。

看起来，其实插入的步骤其实与AVL树是大差不差的，前两步都是按照二叉搜索树的方式进行插入，与之不同的就是第三步，AVL树对此的解决方法就是进行旋转，红黑树作为特殊的AVL树，那么也是要进行旋转的，同样也设计到了旋转。

红黑树在插入结点后是否要进行旋转处理呢？ 

实际上，在插入结点后并不是一定会对红黑树进行调整，若插入结点的父结点是黑色的，那么我们就不用对红黑树进行调整，因为本次结点的插入并没有破坏红黑树的五点性质。

所以要调整的大前提就是：只有当插入结点的父结点是红色时才需要对红黑树进行调整，因为我们默认插入的结点就是红色的，如果插入结点的父结点也是红色的，那么此时就出现了连续的红色结点，因此需要对红黑树进行调整。

因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在。

红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整总分为两种情况。

情况一：插入结点的叔叔存在，且叔叔的颜色是红色。

此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。 

但是这次调整还没有完全结束

  • 此时祖父结点变成了红色，如果祖父结点是根结点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。
  • 如果祖父不是根节点的话，因为祖父原本是黑色，所以其父亲可以是红色，也可以是黑色，但如果是红色的情况下，在本次的颜色调整过后，祖父变为了红，但其父亲又为红，这就会破坏性质三，这就还需要再看其祖父的叔叔的情况，再次进行选择调整。

因此，情况一的抽象图表示如下： 

注意： 叔叔存在且为红时，cur结点是parent的左孩子还是右孩子，调整方法都是一样的。

情况二：插入结点的叔叔存在且颜色是黑色 / 叔叔不存在，

对于这种情况的错误，肯定不是因为cur作为新增结点造成的错误，即使删掉cur那也是需要调整的，那么其造成的原因一定是因为在情况一继续往上调整的过程中出现的，所以对于此cur结点一定不是新插入的结点，而是上一次情况一调整过程中的祖父结点。

所以对于此图需要进行修改

对于此的解决方案处理起来比较简单，但也细分为四种小情况，主要是cur与p，p与g的父子关系。

情况A：p为g的左孩子，cur为p的左孩子

解决方案：对g进行右单旋，p变为黑色，g变为红色。

情况B：p为g的右孩子，cur为p的右孩子

解决方案：对g进行左单旋，p变为黑色，g变为红色。

情况C：p为g的左孩子，cur为p的右孩子

解决方案：对p进行左单旋，后变为情况A（注意记得更换cur与p的名称，图中为了直观看，就不更换了）

情况D：p为g的右孩子，cur为p的左孩子

解决方案：对p进行右单旋，后变为情况B（注意记得更换cur与p的名称，图中为了直观看，就不更换了）

这里就拿情况A来说一些小点吧，我们从上面的分析，cur不是作为新插入的结点，而是因为情况一的调整后使得情况一下的祖父颜色变为了红，而导致情况二中的cur变为了红，所以我们得知a，b子树中至少是存在一个黑色结点的，所以再进行此次的调整后从抽象图中看貌似是不符合性质四，其实是符合的，然而更不必说c子树了，因为在本次的插入是原本就是一个完整的红黑树，c子树中必有一个黑结点，并且c中本就不会存在情况一，也不会导致情况二。

从思路上来讲是简便的，但是代码实现上还是非常复杂的

这里先直接展示代码，稍后说一下注意点

	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;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//大前提//parent在左if (parent == grandfather->_left){Node* uncle = grandfather->_right;//Node* uncle = parent->_right;//错误二if (uncle && uncle->_col == RED){//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红//     g//   p   u// c// //解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{					if (cur == parent->_left){//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑//     g//   p   u// c// // 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接breakRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑//       g//   p      u//     c// 解决：对p左单旋，后变为情景二。RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}				break;}}else//情景大概反着来{//1  uncleNode* uncle = grandfather->_left;//错误一//Node* uncle = parent->_right;//错误一if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right)//2{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//3{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}			}//最后_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}

注意点：其实对于情况二中的A，B小情况其实进行的是单旋，而C，D小情况是进行的双旋，所以也可以将C，D单独归为情况三，就如上面的代码展示一样，然而对于每次的插入后，都需要进行检查是否破坏红黑树的结构，然后破坏的大前提就是其父亲结点也是红，然而对于情况一，我们在调整完后会将祖父颜色置为红，这就导致其可以继续向上进行查看是否导致发生情况二，三的存在，所以还需要继续向上，然而对于情况二，三都是调整完就已经保证了是完整的红黑树了，这就可以直接break跳出即可。

注意： 在红黑树调整后，需要将根结点的颜色变为黑色，因为红黑树的根结点可能在情况一的调整过程中被变成了红色。

红黑树的验证

红黑树也是一种特殊的二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断该二叉树是否满足二叉搜索树的性质。

判断依据：

  1. 是否存在 红-红 
  2. 每条路径黑色结点是否相同个数
  3. 最长的不超过最短的二倍
  4. 根，叶子为黑
	void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){if (refVal != blacknum){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED){if (root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}bool IsBalance(){//1:是否存在 红-红 //每条路径黑色结点是否相同个数//最长的不超过最短的二倍//根，叶子为黑if (_root == nullptr)return true;if (_root->_col == RED)return false;int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}

剩下的内容也就是像二叉搜索树的平常函数：查找，看看有多少层，打印某一层......这里不在多多展示

同样红黑树作为特别的AVL树也是禁止进行修改的！！！

红黑树的删除代码复杂，并且不会就不多说了，但也推荐篇好的文章：

【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树-CSDN博客

这篇关于c++ 红黑树（自平衡二叉搜索树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2