【C++进阶】红黑树的复仇(红与黑的爱恨厮杀)

2024-04-04 17:20

本文主要是介绍【C++进阶】红黑树的复仇(红与黑的爱恨厮杀),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

          主厨:邪王真眼

主厨的主页:Chef‘s blog  

 所属专栏:c++大冒险
 

 总有光环在陨落,总有新星在闪烁


引言:

之前我们学习了 AVL树,不得不惊叹于他那近乎绝对的平衡,然而也惋惜于插入删除效率的低下,今天要讲的红黑树则是以相对的平衡换来了插入删除效率的大幅提高,可谓是各有千秋

ps:建议先看过AVL树后再来学习红黑树:

带你手撕AVL树 


一. 红黑树的概念

         红黑树是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

二 红黑树的性质

  • 1. 每个结点不是红色就是黑色
  • 2. 根节点是黑色的 
  • 3. 如果一个节点是红色的,则它的两个孩子结点是黑色的 
  • 4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点 
  • 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
思考:
为什么满足以上性质,红黑树就能保证:最长路径中节点个数不会超过最短路径节点 个数的2倍?

推导:

  • 性质1不必多说
  • 性质2与后面的旋转有关
  • 性质3表明不能有连续的红色结点
  • 性质4表明理论最短路径就是纯黑节点路径

综上:

            我们可以认为事先建造好一颗纯黑节点的满二叉树,再在两个黑节点之间插入红节点,则理论最长路径就是一黑一红交替,不超过最短路径的二倍。

 三.红黑树的节点讲解及模拟

enum Color
{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;Color _col;RBTreeNode(pair<K, V>& kv = pair<K, V>()):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)
};

代码讲解:

  • 1.我们枚举出了Color
  • 2.除左右指针外,还有父亲指针,使得可以向上回溯
  • 3.用pair对象存储K值V值
  • 4.增加了颜色的成员变量,且默认颜色为红色

提问:

           为什么结点的颜色初始化为红色呢?

回答:

           因为插入新节点时(不为根部),如果插入黑色,一定破坏性质4,导致每条路径黑结点数目不同;而如果插入红色,有可能不会破坏性质3,所以结点初始化为红色。

四.红黑树模拟

4.1 成员变量

template<class K, class V>
class RBTree
{
protected:typedef RBTreeNode<K, V> Node;
public://函数
protected :Node* _root;
};

4.2插入

与搜索二叉树以及AVL树相比,红黑树的默认成员函数和遍历相差不大,所以这里重点讲插入

4.2.1插入过程:

  1. 以普通二叉搜索树的方式进行插入
  2. 根据插入后的不同情况进行调整 
	bool Insert(pair<K, V>& kv){if (_root == nullptr){_root = new Node(val);return true;}else{Node* cur = _root;Node* parent = nullptrwhile (cur){parent = cur;if (cur->_val > val)cur = cur->left;else if (cur->_val < val)cur = cur->_right;elsereturn false;}cur = new Node(val);if (parent->_val.first > cur->_val.first){parent->_left = cur;}else{parent->_parent = cur;}cur->_parent = parent;///从此处开始进行插入后的调整while (parent && parent->_col == RED){Node* grandparent = parent->_parent;Node* uncle = nullptr;if (grandparent->_left == parent)uncle = grandparent->_right;elseuncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else if (grandparent->_left == parent){if (parent->_left = cur){RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateL(parent);RotateR(grandparent);grandparent->_col = RED;cur->_col = BLACK;}}else{if (parent->_right = cur){RotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandparent);grandparent->_col = RED;cur->_col = BLACK;}}void RotateL(AVLNode * parent)//左旋{Node* grandparent = parent->_parent;Node* ChildR = parent->_right;if (grandparent){if (grandparent->_left == parent)grandparent->_left = ChildR;elsegrandparent->_right = ChildR;}else_root = ChildR;ChildR->_parent = grandparent;parent->_right = ChildR->_left;ChildR->_left->_parent = parent;ChildR->_left = parent;parent->_parent = ChildR;ChildR->_bf = parent->_bf = 0;}void RotateR(AVLNode * parent)//右旋{Node* grandparent = parent->_parent;Node* ChildL = parent->_left;if (grandparent){if (grandparent->_left == parent)grandparent->_left = ChildL;elsegrandparent->_right = ChildL;}else_root = ChildL;ChildL->_parent = grandparent;//两两一组进行改变parent->_left = ChildL->_right;ChildL->_right->_parent = parent;ChildL->_right = parent;parent->_parent = ChildL;//ChildL->_bf = parent->_bf = 0;}void RotateRL(AVLNode * parent)//双旋,先右旋在左旋{Node* ChildR = parent->_right;int bf = ChildR->_left->_bf;RotateR(ChildR);RotateL(parent);if (bf == 0){parent->_bf = 0;ChildR->_bf = 0;ChildR->_left->_bf = 0;}else if (bf == 1){parent->_bf = -1;ChildR->_bf = 0;ChildR->_left->_bf = 0;}else if (bf == -1){parent->_bf = 0;ChildR->_left->_bf = 0;ChildR->_bf = 1;}else{assert(false);}}void RotateLR(AVLNode * parent)//双旋,先左旋,再右旋{Node* ChildL = parent->_left;int bf = ChildL->_right->_bf;RotateR(ChildL);RotateL(parent);if (bf == 0){parent->_bf = 0;ChildL->_bf = 0;ChildL->_right->_bf = 0;}else if (bf == 1){parent->_bf = 0;ChildL->_bf = -1;ChildL->_right->_bf = 0;}else if (bf == -1){parent->_bf = 1;ChildL->_right->_bf = 0;ChildL->_bf = 0;}else{assert(false);}}void Inorde(AVLNode * root, vector<pair<K, V>>&v){if (root == nullptr)return;Inorde(root->_left, v);v.push_back(root->_val);Inorde(root->_right, v);}}}}

插入后调整的分析:

  • 1.像AVL树一样,大框架也是向上回溯,判断循环进行条件是父亲节点不为空且父亲节点颜色为红.因为新节点的默认颜色是红色,如果其双亲节点的颜色是黑色,没有违反红黑树任何 性质,则不需要调整;
  • 2当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点

    🍒🍒4.2.2情况一:

cur为红,p为红,g为黑,u存在且为红 

解决方式:
              将p,u改为黑,g改为红,然后把g当成cur,继续向上调整。


🍒🍒4.2.3情况二:

cur为红,p为红,g为黑,u不存在/u存在且为黑,p是g的左孩子,cur是p的左孩子

解决方案:

  1. 先对grandparent进行右单旋
  2. 再将parent变黑,grandparent变红


🍒🍒4.2.4情况三

cur为红,p为红,g为黑,u不存在/u存在且为黑,p是g的左孩子,cur是p的右孩子

  重点提醒:

               可以发现左单旋后就变成了情况二

解决方案:

  1. 先对parent进行左单旋
  2. 再对grandparent进行右单旋
  3. 最后将cur变黑,grandparent变红,这里将cur变黑而不是parent是因为左单旋后cur取代了parent的位置


🍒🍒4.2.5情况四:

cur为红,p为红,g为黑,u不存在/u存在且为黑,p是g的右孩子,cur是p的右孩子

解决方案:

  1. 先对grandparent进行左单旋
  2. 再将parent变黑,grandparent变红


🍒🍒4.2.6情况五:

cur为红,p为红,g为黑,u不存在/u存在且为黑,p是g的右孩子,cur是p的左孩子

重点提醒:

               可以发现右单旋后就变成了情况四

解决方案:

  1. 先对parent进行右单旋
  2. 再对grandparent进行左单旋
  3. 最后将cur变黑,grandparent变红,这里将cur变黑而不是parent是因为左单旋后cur取代了parent的位置

5.红黑树的验证

红黑树的检测分为两步:

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

void Inorde(AVLNode * root, vector<pair<K, V>>&v)
{if (root == nullptr)return;Inorde(root->_left, v);v.push_back(root->_val);Inorde(root->_right, v);
}

2. 检测其是否满足红黑树的性质

bool IsBalance(Node*root)
{//空树也是红黑树if (root == nullptr)return true;//违反性质2if (root->_col == RED){cout << "树的根节点应该是黑色,可该树却是红色" << endl;return false;}//计算一条路径黑节点数量Node* cur = root;int num = 0;while (cur){if (cur->_col == BLACK)num++;cur = cur->_left;}return _IsBlance(root, num);
}
IsBalance(Node* root, size_t num, size_t cur_num)
{if (root == nullptr){//违反性质4if (num != cur_num){cout << "对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点,但该树却不是" << endlreturn false;}elsereturn true;}if (root->_col == BLACK)num++;//违反性质3if (root->_parent && root->_parent == RED && root->_col == RED){cout << "如果一个节点是红色的,则它的两个孩子结点是黑色的,可该树却出现了连续的红色节点" << endl;return false;}return IsBalance(root->_left, num, cur_num) && IsBalance(root->_right, num, cur_num);
}

6. 红黑树与AVL树的比较

       红黑树和 AVL 树都是高效的平衡二叉树, 增删改查的时间复杂度都是O(log N) ,红黑树不追 求绝对平衡,其只需保证 最长路径不超过最短路径的2倍 降低了插入和旋转的次数 所以在经常进行增删的结构中性能比 AVL 树更优,而且红黑树实现比较简单,所以实际运用中红 黑树更多。

7. 红黑树的应用

  • 1. C++ STL库 -- map/set、mutil_map/mutil_set 
  • 2. Java 库
  • 3. linux内核
  • 4. 其他一些库

创作不易,点赞关注支持一下吧

这篇关于【C++进阶】红黑树的复仇(红与黑的爱恨厮杀)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/876390

相关文章

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

C++ Primer 标准库vector示例详解

《C++Primer标准库vector示例详解》该文章主要介绍了C++标准库中的vector类型,包括其定义、初始化、成员函数以及常见操作,文章详细解释了如何使用vector来存储和操作对象集合,... 目录3.3标准库Vector定义和初始化vector对象通列表初始化vector对象创建指定数量的元素值

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

MySQL进阶之路索引失效的11种情况详析

《MySQL进阶之路索引失效的11种情况详析》:本文主要介绍MySQL查询优化中的11种常见情况,包括索引的使用和优化策略,通过这些策略,开发者可以显著提升查询性能,需要的朋友可以参考下... 目录前言图示1. 使用不等式操作符(!=, <, >)2. 使用 OR 连接多个条件3. 对索引字段进行计算操作4

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》:本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没