C++笔记：从零开始一步步手撕红黑树

2024-03-17 14:20
文章标签 c++ 笔记 从零开始 一步步 黑树 撕红

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

文章目录

  • 红黑树概念
  • 红黑树的性质
  • 红黑树 VS AVL树
  • 红黑树的结点与树的描述——定义类
  • 红黑树的插入操作
    • 步骤一：按照二叉搜索树的规则插入新结点
    • 步骤二：检测新节点插入后，红黑树的性质是否造到破坏
      • 情况一：uncle存在且为红
      • 情况二：uncle不存在或者uncle存在且为黑
    • 验证一棵红黑树是否符合规则

红黑树概念

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

在这里插入图片描述

红黑树的性质

红黑树主要靠以下几条性质或者说规则达到高度近似平衡：

  1. 结点的颜色不是 黑色 就是 红色。
  2. 根结点的颜色是 黑色。
  3. 任意一条路径中不存在连续的红色结点。
  4. 每条路径上的黑色结点数量相同。
  5. 规定空结点才是叶子结点，叶子结点都是黑色的（主要作用：数路径）。

为什么满足以上几条规则，红黑树就能保证：最长路径的有效结点个数不超过最短路径结点个数的 2 倍，接下来举个例子证明一下：
在这里插入图片描述

红黑树 VS AVL树

  1. 平衡条件的严格性：

AVL 树要求达到的是一种左右子树高度差的绝对值不超过 1 的绝对平衡；
红黑树要求达到的是一种最长路径上的结点数不超过最短路径上的结点数的 2 倍的近似平衡。

  1. 查找的效率分析：

假设红黑树和 AVL 树都具有 N N N 个结点:

对于AVL树：高度最多达到 l o g 2 ( N + 1 ) log_2(N+1) log2​(N+1)，最坏的情况下的查找次数为 2 log ⁡ 2 ( N + 1 ) 2\log_2(N+1) 2log2​(N+1)；

对于红黑树：高度最多达到 2 log ⁡ 2 ( N + 1 ) 2\log_2(N+1) 2log2​(N+1)，最坏的情况下的查找次数为 2 log ⁡ 2 ( N + 1 ) 2\log_2(N+1) 2log2​(N+1)；

虽然从分析来看红黑树的查找效率稍差于 AVL 树，但是由于 l o g 2 ( N + 1 ) log_2(N+1) log2​(N+1) 这个数值足够小，它们之间的差异其实可以忽略不计。

举个例子来说，当 N = 10 亿 N = 10亿 N=10亿 时，AVL 树最多查找 30 次，红黑树最多也才查找 60 次，对于现代每秒钟运算上亿次的 CPU 来说，差异几乎不存在。

  1. 旋转操作的频率：

由于AVL树对平衡要求更严格，因此在插入或删除结点时可能需要更频繁地执行旋转操作来保持平衡；相比之下，红黑树对于树的平衡性有更宽松的要求，因此在实际操作中可能需要更少的旋转操作。

红黑树的结点与树的描述——定义类

// 结点的颜色
enum COLOR 
{RED,BLACK
};// 结点类
template<class K, class V>
struct RBTreeNode 
{RBTreeNode(const pair<K, V>& kv): _parent(nullptr), _left(nullptr), _right(nullptr), _color(RED), _kv(kv){}RBTreeNode *_parent;RBTreeNode *_left;RBTreeNode *_right;COLOR _color;pair<K, V> _kv;
};template<class K, class V>
class RBTree 
{typedef RBTreeNode<K, V> Node;
public:RBTree() : _root(nullptr) {}
protected:Node *_root;
};

【说明】

  1. 枚举类型COLOR： 用于表示红黑树结点的颜色。这样的设计是为了提高可读性，如结点->_color == RED 表示结点是红色，结点->_color == BLACK 表示结点是黑色的。
  2. RBTreeNode 结构体(类)： 用于描述红黑树结点，包含了红黑树节点的基本属性和数据。
    • _parent：指向父节点的指针。
    • _left、_right：分别指向左子节点和右子节点的指针。
    • _color：节点的颜色位，是一个枚举类型（红色或黑色）。
    • _kv：表明设计的红黑树结点中存储的数据是键值对结构。
  3. RBTree 类： 描述红黑树的结构，只包含一个指向根节点的指针成员_root，红黑树的所有操作都是在这个基础上进行的。
    • RBTree() 是红黑树的无参默认构造函数，构造一棵空的红黑树。

关于结点类，这里有一个问题：为什么新构造的结点是红色的，不能是黑色的吗？

答案是不能，因为红黑树中有这样的两条规则：“ 任意一条路径中不存在连续的红色结点。 ”、“ 每条路径上的黑色结点数量相同。 ”

由于在插入和删除操作过程中，难免会违反规则其中的一或者两条规则，但是在这两条规则中违反后者比违反前者的代价来得更大，新构造的结点是红色的在插入过程中很容易出现连续的红色结点，但是可以通过对结点的颜色重新调整或者旋转来处理，但是如果新增加黑色却很难处理，因为黑色结点的数量关乎到所有路径。

红黑树的插入操作

步骤一：按照二叉搜索树的规则插入新结点

  1. 树为空，则构造新结点，让_root 指针指向该结点，由于根结点必定是黑色的规定，将根结点的颜色置为黑，返回true。
  2. 树不空，按key的大小寻找插入位置，如果已存在，按插入失败处理，返回false。
  3. 走到空表示找到合适位置，然后插入构造的新结点，插入时要判断左边插入或者右边插入。

【步骤一部分的代码如下：】

/*** 函数介绍：插入一个键值对。** 函数参数：*		kv: 要插入的键值对，其中第一个元素为键，第二个元素为值。** 返回值：插入成功返回true，否则返回false。*/
bool insert(const pair<K, V>& kv) 
{if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}else{Node *parent = nullptr;Node *cur = _root;while (cur != nullptr){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{// 待插入kv已存在，插入失败return false;}}// 循环结束，构造新结点并链接cur = new Node(kv);if (parent->_kv.first < cur->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 检测新节点插入后，红黑树的性质是否造到破坏// 如果被性质被破坏要进行特殊处理// 步骤二的代码写在这里// ...}
}

步骤二：检测新节点插入后，红黑树的性质是否造到破坏

新插入节点的默认颜色是红色，插入之后又可能存在两种情况：

  1. 新节点的双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整插入结束；
  2. 新插入节点的双亲节点颜色为红色，违反了不能有连续红色节点的规则，需要重新设置结点颜色；

而结点颜色具体怎么设置和 以下 4 个结点的情况有关：
在这里插入图片描述

仔细想一下，我们不难发现，cur、parent、grandparent这三个结点的颜色基本固定为红、红、黑，cur可能是新插入的结点，也有可能是从黑色变成红色的结点（为什么等下会说），所以唯一的变量就是uncle结点。

情况一：uncle存在且为红

满足情况一时不关注结点位置，只进行颜色转换处理：

  • 将parent和uncle变成黑色；
  • 将grandparent变成红色；
  • 让cur成为grandparent后重新判断；
    在这里插入图片描述

情况二：uncle不存在或者uncle存在且为黑

当遇到情况二时，单纯的颜色调整就不管用了，得旋转 + 颜色调整一起上，这里的旋转和AVL树的旋转几乎是一样的，关于旋转的部分的细节我就不多分析了，旋转的细节可以参考我之前写的《C++笔记：从零开始一步步手撕高阶数据结构AVL树》

当uncle不存在时：
在这里插入图片描述

当uncle存在且为黑时
在这里插入图片描述
综上所述：

  • parent为grandparent的左孩子时
    • cur为parent的左孩子时，右单旋，parent置黑，grandparent置红。
    • cur为parent的右孩子时，左右双旋，cur置黑，grandparent置红。
  • parent为grandparent的右孩子时
    • cur为parent的右孩子时，左单旋，parent置黑，grandparent置红。
    • cur为parent的左孩子时，右左双旋，cur置黑，grandparent置红。

【完整的红黑树插入代码如下，仅供参考】

bool insert(const pair<K, V>& kv) 
{if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}else{Node *parent = nullptr;Node *cur = _root;while (cur != nullptr){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{// 待插入kv已存在，插入失败return false;}}// 循环结束，构造新结点并链接cur = new Node(kv);if (parent->_kv.first < cur->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 满足该条件下执行特殊处理while (parent && parent->_color == RED){Node *grandparent = parent->_parent;if (parent == grandparent->_left){Node *uncle = grandparent->_right;// 情况1：uncle存在且为RED ---> recolor(只变色处理)if (uncle != nullptr && uncle->_color == RED){// recolorparent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else // 情况2：uncle不存在 或者 uncle存在且为BLACK// 调整颜色 + 旋转{if (cur == parent->_left){// recolor + 右旋//       g//   p       u// cR_Rotate(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{// recolor + 左右双旋//       g//   p       u//     cL_Rotate(parent);R_Rotate(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}else // parent == grandparent->_right{Node *uncle = grandparent->_left;// 情况1：uncle存在且为RED ---> recolor(只变色处理)if (uncle != nullptr && uncle->_color == RED){// recolorparent->_color = uncle->_color = BLACK;grandparent->_color = RED;// 继续往上处理cur = grandparent;parent = cur->_parent;}else // 情况2：uncle不存在 或者 uncle存在且为BLACK// 调整颜色 + 旋转{if (cur == parent->_right){// recolor + 左旋//       g//   u       p//             cL_Rotate(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{// recolor + 右左双旋//       g//   u       p//         cR_Rotate(parent);L_Rotate(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}}// parent == nullptr || parent->_color == BLACK// 暴力处理，根节点一定为黑色_root->_color = BLACK;		return true;}
}

验证一棵红黑树是否符合规则

使用上面的插入接口构建的红黑树，我们不能保证一定就没有问题，也许过程中存在某一处违反规则的情况出现，所以这里要针对红黑树的定义和规则写一个函数来验证它是否符合规则。

红黑树的检测分为两步：

  1. 检测其是否满足二叉搜索树，即中序遍历是否为有序序列；
void _inorder(Node *root)
{if (root == nullptr)return;_inorder(root->_left);cout << root->_kv.first << endl;_inorder(root->_right);
}void inorder()
{_inorder(_root);
}
  1. 检测其是否满足红黑树的性质，主要有以下三条：
    • 根结点的颜色是 黑色。
    • 任意一条路径中不存在连续的红色结点。
    • 每条路径上的黑色结点数量相同。
bool isRBTree()
{// 规则：根结点是黑色的if (_root && _root->_color == RED){return false;}// 规则：每条路径的黑色结点数量一致 -> EqualBLACKint numOfBLACK = 0;Node *cur = _root;while (cur){if (cur->_color == BLACK){++numOfBLACK;}cur = cur->_left;}// 规则：不存在连续红结点 -> DiscontinuousREDreturn DiscontinuousRED(_root) && EqualBLACK(_root, 0, numOfBLACK);
}bool DiscontinuousRED(Node *root)
{if (root == nullptr){return true;}if (root->_color == RED && root->_parent->_color == RED){return false;}return DiscontinuousRED(root->_left) && DiscontinuousRED(root->_right);
}bool EqualBLACK(Node *root, int curPathBLACK, int &standardNumOfBALCK)
{if (root == nullptr){// 走到空说明一条路径已经走完，该路径上的黑色结点数也同统计好了return curPathBLACK == standardNumOfBALCK;}if (root->_color == BLACK){++curPathBLACK;}return EqualBLACK(root->_left, curPathBLACK, standardNumOfBALCK)&& EqualBLACK(root->_right, curPathBLACK, standardNumOfBALCK);
}

【顺带一提，这是优化后的代码】

判断是否存在连续红结点的函数和判断每条路径黑色结点数量是否相同的思路相似的，完全可以二合一。

bool isRBTree()
{// 规则：根结点是黑色的if (_root && _root->_color == RED){return false;}// 规则：每条路径的黑色结点数量一致int numOfBLACK = 0;Node *cur = _root;while (cur){if (cur->_color == BLACK){++numOfBLACK;}cur = cur->_left;}return Check(_root, 0, numOfBLACK);
}bool Check(Node* root, int curPathBLACK, int& standardNumOfBALCK)
{if (root == nullptr){if (curPathBLACK != standardNumOfBALCK){// 走到空说明一条路径已经走完，该路径上的黑色结点数也同统计好了return false;}return true;}if (root->_color == BLACK){++curPathBLACK;}if (root->_color == RED && root->_parent->_color == RED){return false;}return Check(root->_left, curPathBLACK, standardNumOfBALCK)&& Check(root->_right, curPathBLACK, standardNumOfBALCK);
}

至于红黑树的删除操作，这里留一个坑，之后有时间再填，完整的代码已经上传gitee仓库，这里是链接：https://gitee.com/ljinhao03/study-achievement/tree/master/RBTree

这篇关于C++笔记：从零开始一步步手撕红黑树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
C++11委托构造函数和继承构造函数的实现

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函
阅读更多...
C++11作用域枚举(Scoped Enums)的实现示例

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C
阅读更多...
C++链表的虚拟头节点实现细节及注意事项

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,：本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点（Dummy Head）一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二
阅读更多...
C++ 检测文件大小和文件传输的方法示例详解

C++ 检测文件大小和文件传输的方法示例详解

《C++检测文件大小和文件传输的方法示例详解》文章介绍了在C/C++中获取文件大小的三种方法,推荐使用stat()函数,并详细说明了如何设计一次性发送压缩包的结构体及传输流程,包含CRC校验和自动解... 目录检测文件的大小✅ 方法一：使用 stat() 函数（推荐）✅ 用法示例：✅ 方法二：使用 fsee
阅读更多...
Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2