当前位置：首页 » 《我的小黑屋》 » 正文

【C++高阶数据结构】红黑树：全面剖析与深度学习

26 人参与  2024年11月11日 13:22  分类 : 《我的小黑屋》  评论

点击全文阅读


? 个人主页：Zfox_
? 系列专栏：C++从入门到精通

目录

? 前言：红黑树与AVL树的比较一： ? 红黑树的概念二： ? 红黑树的性质 三： ? 红黑树节点的定义和结构? 3.1 基本元素? 3.2 节点颜色? 3.3 构造函数? 3.4 红黑树节点的定义 四：? 红黑树的插入操作 五：? 红黑树的验证 六：? 红黑树的完整代码

? 前言：红黑树与AVL树的比较

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

一： ? 红黑树的概念

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

在这里插入图片描述

二： ? 红黑树的性质

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

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

三： ? 红黑树节点的定义和结构

? 3.1 基本元素

_left：指向节点的左子节点的指针_right：指向节点的右子节点的指针 _parent：指向节点的父节点的指针_kv：一个结构体或配对（pair），包含节点的键值（key）和值（value）。这取决于红黑的具体用途，可能只包含键或包含键值对。 _col：表示当前节点的颜色。

? 3.2 节点颜色

在上面的定义中，_col 成员变量用于表示节点的颜色，通过 Color 枚举类型来定义，可以是 RED 或 BLACK。

? 3.3 构造函数

初始化一个新节点时，通常需要一个构造函数，它接受一个键值对（或仅键），并设置节点的左子节点、右子节点、父节点和颜色（初始化为红色）

? 3.4 红黑树节点的定义

// 节点的颜色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;          // 节点的颜色}

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
答案：优先增加黑色节点会破坏红黑树的默认规则和结构，而新插入红色节点可以通过调整来适应规则，不一定会破坏结构。

四：? 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1. 按照二叉搜索的树规则插入新节点 
template<class ValueType>class RBTree{//……bool Insert(const ValueType& data){PNode& pRoot = GetRoot();if (nullptr == pRoot){pRoot = new Node(data, BLACK);// 根的双亲为头节点pRoot->_pParent = _pHead;_pHead->_pParent = pRoot;}else{// 1. 按照二叉搜索的树方式插入新节点// 2. 检测新节点插入后，红黑树的性质是否造到破坏，// 若满足直接退出，否则对红黑树进行旋转着色处理}// 根节点的颜色可能被修改，将其改回黑色pRoot->_color = BLACK;_pHead->_pLeft = LeftMost();_pHead->_pRight = RightMost();return true;}private:PNode& GetRoot(){ return _pHead->_pParent;}// 获取红黑树中最小节点，即最左侧节点PNode LeftMost();// 获取红黑树中最大节点，即最右侧节点PNode RightMost();private:PNode _pHead;};

2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定 : cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一: cur为红，p为红，g为黑，u存在且为红
在这里插入图片描述
cur和p均为红，违反了性质三，此处能否将p直接改为黑？

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

情况二 : cur为红，p为红，g为黑，u不存在/u存在且为黑
在这里插入图片描述
p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色–p变黑，g变红

情况三 : cur为红，p为红，g为黑，u不存在 / u存在且为黑
在这里插入图片描述
解决方式： p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转则转换成了情况2
具体实现代码如下：

bool Insert(const pair<K, V>& kv){if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;return true;}// 找到插入位置Node* cur = _root, * parent = nullptr;while (cur){if (cur->_kv.first == kv.first) return false;else if (cur->_kv.first < kv.first) {parent = cur;cur = cur->_right;}else {parent = cur;cur = cur->_left;}}cur = new Node(kv);//新增节点 颜色优先选择红色cur->_col = RED;if (kv.first > parent->_kv.first) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 1、parent不存在，cur就是根了，出去后把根处理成黑的// 2、parent存在，且为黑// 3、parent存在，且为红，继续循环处理// 变色了之后持续网上处理while (parent && parent->_col == RED)          // 父亲颜色是红色就需要继续处理（来连续的红节点， 关键看叔叔）{Node* grandfather = parent->_parent;if (parent == grandfather->_left)               // 父亲在爷爷的左边 右边就是对称的{Node* uncle = grandfather->_right;//    g//  p   uif (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  p   u// c// 单旋if (cur == parent->_left){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 {//    g//  u   pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  u   p//        c// 单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  u   p//    c// 双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}}_root->_col = BLACK;return true;}

五：? 红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质
具体代码如下： 
bool IsBalance(){if (_root == nullptr)return true;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);}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 << "存在连续的红色节点" << '\n';return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}

六：? 红黑树的完整代码

#pragma once#include <iostream>#include <algorithm>#include <cstring>#include <set>#include <map>#include <assert.h>using namespace std;enum Color{RED,BLACK};template<class K, class V>struct RBTreeNode {pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}};template<class K, class V>class RBTree {typedef RBTreeNode<K, V> Node;public:RBTree() = default;RBTree(const RBTree<K, V>& t){_root = Copy(t._root);}RBTree<K, V>& operator=(RBTree<K, V> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}bool Insert(const pair<K, V>& kv){if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;return true;}// 找到插入位置Node* cur = _root, * parent = nullptr;while (cur){if (cur->_kv.first == kv.first) return false;else if (cur->_kv.first < kv.first) {parent = cur;cur = cur->_right;}else {parent = cur;cur = cur->_left;}}cur = new Node(kv);//新增节点 颜色优先选择红色cur->_col = RED;if (kv.first > parent->_kv.first) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 1、parent不存在，cur就是根了，出去后把根处理成黑的// 2、parent存在，且为黑// 3、parent存在，且为红，继续循环处理// 变色了之后持续网上处理while (parent && parent->_col == RED)          // 父亲颜色是红色就需要继续处理（来连续的红节点， 关键看叔叔）{Node* grandfather = parent->_parent;if (parent == grandfather->_left)               // 父亲在爷爷的左边 右边就是对称的{Node* uncle = grandfather->_right;//    g//  p   uif (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  p   u// c// 单旋if (cur == parent->_left){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 {//    g//  u   pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  u   p//        c// 单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  u   p//    c// 双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}}_root->_col = BLACK;return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}Node* Copy(Node * root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_kv);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destroy(Node * root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void InOrder(){_InOrder(_root);}int Height(){return _Height(_root);}// 检查是否是红黑树bool IsBalance(){if (_root == nullptr)return true;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 << "存在连续的红色节点" << '\n';return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void RotateL(Node * parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;Node* parent_parent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent_parent == nullptr){_root = subR;subR->_parent = nullptr;}else {if (parent == parent_parent->_left) parent_parent->_left = subR;else parent_parent->_right = subR;subR->_parent = parent_parent;}}void RotateR(Node * parent){Node* subL = parent->_left;Node* subLR = parent->_left->_right;parent->_left = subLR;if (subLR) subLR->_parent = parent;Node* parent_parent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent_parent == nullptr){_root = subL;subL->_parent = nullptr;}else {if (parent == parent_parent->_left){parent_parent->_left = subL;}else {parent_parent->_right = subL;}subL->_parent = parent_parent;}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << '\n';_InOrder(root->_right);}Node* _root = nullptr;};void TestRBTree1(){RBTree<int, int> t;int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalance() << endl;}

以上就是红黑树的讲解与完整实现过程，红黑树因为其自平衡的特性，及通过节点颜色来操作其树形结构的特点，极大的提高了数据存储及处理的效率，需要我们好好掌握，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~?
在这里插入图片描述


点击全文阅读


本文链接：http://m.zhangshiyu.com/post/184576.html

<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 上离婚综艺：我红了，前妻疯了(江年李雨桐)小说全章节目录阅读
  • 穿越之下乡知青有空间免费阅读全文，主角江玥张春花小说
  • 正版小说《娇媚女配，她靠美貌俘虏男主》傅恹虞笙笙在线免费阅读
  • 玄漫写的小说东隅未辞桑非晚在线阅读
  • 老书虫推荐《道德绑架？笑死，我根本没有好吗》 在线阅读
  • 小说人死了先烂着，老板也一样主角为张明苏红吴国强免费阅读
  • 人死了先烂着，老板也一样小说-张明苏红吴国强全篇阅读
  • 主角是张青云张阿森的小说龙王棺最完整版热门连载
  • 李明张玉嬿小说《美女你好，为什么对我步步紧逼》全文阅读
  • 《许你朝朝又暮暮》by法染小说完结版在线阅读
  • 玉萦赵元祐全文阅读最新 玉萦赵元祐小说目录
  • 谢玉遥庄文佩全本章节在线阅读大结局

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1