当前位置： 首页 > news >正文

数据结构：红黑树讲解（C++）

news 来源：原创 2024/5/10 16:58:01

红黑树

    • 1.前言
    • 2.红黑树简述
      • 2.1概念
      • 2.2性质
    • 3.红黑树的插入
      • 3.1关于新插入节点的颜色
      • 3.2节点的定义
      • 3.3插入新节点
      • 3.4判断插入后是否需要调整
      • 3.5插入后维持红黑树结构（重点）
        • 3.5.1cur、p、u为红，g为黑
        • 3.5.2cur、p为红，g为黑，u为空/u存在为黑
    • 4.一些简单的测试接口
    • 5.完整代码

1.前言

  • 本文旨在理解红黑树基本概念以及变色旋转规则，以理解C++map和set的底层原理，不会讲红黑树的删除操作。
  • 对于基本的旋转操作(单旋和双旋)，本文不会展开讲，详细讲解在这里：
    AVL树旋转讲解。



2.红黑树简述

2.1概念

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


2.2性质

  1. 每个节点不是红色就是黑色。
  2. 根部节点是黑色的。(为了减少旋转次数，后面讲旋转大家就明白了）
  3. 对于一个红节点，它的孩子只能是黑色。(即一条路径上不能出现连续的红色节点)
  4. 每条路径都必须包含相同数量的黑色节点。

通过上面规则的限制，红黑树最长路径一定不会超过最短路径两倍，也就维持了高度的相对平衡。
结合3、4来看下面的两条路径：
最长：黑、红、黑、红、黑、红…………
最短：黑、黑、黑…………



3.红黑树的插入

3.1关于新插入节点的颜色

对于新插入节点，我们设置为红色，原因是红黑树每条路径都必须包含相同数量的黑色节点（性质4），新插入红节点不一定破坏红黑树的结构，新插入黑色节点一定不符合性质4而且很难调整。
在这里插入图片描述


3.2节点的定义

//用枚举来定义颜色
enum Color
{RED,BLACK
};//这里直接实现key_value模型
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(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED)  //新节点颜色为红色{}
};

3.3插入新节点

这里比较简单，按二叉搜索树的规则插入即可：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first) //待插入节点在右子树{parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first)  //待插入节点在左子树{parent = cur;cur = cur->_left;}else  //相同{return false;}}cur = new Node(kv);if (kv.first > parent->_kv.first) //新节点在父亲右子树{parent->_right = cur;}else  //新节点在父亲左子树{parent->_left = cur;}cur->_parent = parent;  //记得更新父亲指针/// 变色旋转维持红黑树结构（暂时省略）  //_root->_col = BLACK; //可能改变根部颜色，保持根部为黑色return true;
}

3.4判断插入后是否需要调整

其实红黑树插入后只需要看当前节点和父亲的颜色即可，其中新节点一定为红。

  1. 父亲为黑，符合规则，不需要调整。
  2. 父亲为红，此时出现红红的连续节点，需要进行调整。

3.5插入后维持红黑树结构（重点）

为了方便叙述，我们做如下定义：

  1. cur表示当前节点
  2. p表示cur父亲节点
  3. u表示叔叔节点
  4. g表示祖父(p和u的父亲)节点
3.5.1cur、p、u为红，g为黑

在这里插入图片描述
代码：

while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
{Node* granderfather = parent->_parent;  //祖父//需要对叔叔进行操作，需要判断叔叔是祖父的左还是右if (parent == granderfather->_left)  //父亲是祖父的左子树{Node* uncle = granderfather->_right;if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可{uncle->_col = parent->_col = BLACK;granderfather->_col = RED; //当前子树可能为部分，继续向上调整cur = granderfather;parent = cur->_parent;}else  //叔叔为空或为黑色{ //先省略}}else  //父亲是祖父的右子树{Node* uncle = granderfather->_left;if (uncle && uncle->_col == RED)  //叔叔不空并且为红{parent->_col = uncle->_col = BLACK;granderfather->_col = RED;  //当前可能为部分子树，需要继续上调cur = granderfather;parent = cur->_parent;}else  //叔叔为空或为黑色{// 先省略}}
}

3.5.2cur、p为红，g为黑，u为空/u存在为黑

下面是一会要用到的旋转接口：

void RotateL(Node* parent)  //左单旋,rotate->旋转
{Node* SubR = parent->_right;Node* SubRL = SubR->_left;  //这个有可能为空Node* ppnode = parent->_parent;  //原来父亲的父亲parent->_right = SubRL;if (SubRL)  SubRL->_parent = parent;SubR->_left = parent;parent->_parent = SubR;if (ppnode == nullptr)  //旋转的是整颗树{_root = SubR;SubR->_parent = nullptr;}else  //旋转的是部分{if (ppnode->_left == parent) //是左子树{ppnode->_left = SubR;}else  //是右子树{ppnode->_right = SubR;}SubR->_parent = ppnode;}
}void RotateR(Node* parent)  //右单旋细节处理和左单旋差不多
{Node* SubL = parent->_left;Node* SubLR = SubL->_right;  //这个有可能为空Node* ppnode = parent->_parent;parent->_left = SubLR;if (SubLR)  SubLR->_parent = parent;SubL->_right = parent;parent->_parent = SubL;if (ppnode == nullptr)  //旋转的是整颗树{_root = SubL;SubL->_parent = nullptr;}else  //旋转部分{if (ppnode->_left == parent)  //是左子树{ppnode->_left = SubL;}else  //右子树{ppnode->_right = SubL;}SubL->_parent = ppnode;}
}

涉及旋转情况比较复杂，分开讨论：

（1）p为g的左孩子，cur为p的左孩子
在这里插入图片描述


（2）p为g的左孩子，cur为p的右孩子

在这里插入图片描述


（3）p为g的右孩子，cur为p的右孩子

在这里插入图片描述


（4）p为g的右孩子，cur为p的左孩子

在这里插入图片描述

整合一下（1、2、3、4）得到下面的调整代码：

//到这里插入新节点的工作完成，下面进行结构调整：
while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
{Node* granderfather = parent->_parent;  //祖父if (parent == granderfather->_left)  //父亲是祖父的左子树，p为g的左孩子{Node* uncle = granderfather->_right;if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可{uncle->_col = parent->_col = BLACK;granderfather->_col = RED; //当前子树可能为部分，继续向上调整cur = granderfather;parent = cur->_parent;}else  //叔叔为空或为黑色{ //     g//   p   u// cif (cur == parent->_left)  //当前为父亲的左子树，cur为p的左孩子{RotateR(granderfather);granderfather->_col = RED;parent->_col = BLACK;}else   //当前为父亲的右子树，cur为p的右孩子{//    g//  p   u//    c//左右双旋RotateL(parent);RotateR(granderfather);granderfather->_col = RED;cur->_col = BLACK;}break;  //这两种情况调整完可以结束}}else  //父亲是祖父的右子树，p为g的右孩子{Node* uncle = granderfather->_left;if (uncle && uncle->_col == RED)  //叔叔不空并且为红{parent->_col = uncle->_col = BLACK;granderfather->_col = RED;  //当前可能为部分子树，需要继续上调cur = granderfather;parent = cur->_parent;}else  //叔叔为空或为黑色{if (cur == parent->_right)  //当前为父亲的右，cur为p的右孩子{//    g//  u   p//        c//左旋RotateL(granderfather);parent->_col = BLACK;granderfather->_col = RED;}else  //当前为父亲的左，cur为p的左孩子{//   g// u   p//   c//右左双旋RotateR(parent);RotateL(granderfather);cur->_col = BLACK;granderfather->_col = RED;	}break;  //这两种情况调整完可以结束}}
}
_root->_col = BLACK; //保持根部为黑色



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)  //到根部看看当前路径黑色节点和标准值是否一致{//cout << balcknum << endl;if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}/检查子比较复杂，可以反过来去检查红节点父是否为黑色if (root->_col == RED && 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()
{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);
}



5.完整代码

#pragma once
#include <iostream>
#include <utility>
using namespace std;//用枚举来定义颜色
enum Color
{RED,BLACK
};//这里直接实现key_value模型
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(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED)  //新节点颜色为红色{}
};template<class K, class V>
class RBTree
{
public:typedef RBTreeNode<K, V> Node;bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first) //待插入节点在右子树{parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first)  //待插入节点在左子树{parent = cur;cur = cur->_left;}else  //相同{return false;}}cur = new Node(kv);if (kv.first > parent->_kv.first) //在右子树{parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束{Node* granderfather = parent->_parent;  //祖父if (parent == granderfather->_left)  //父亲是祖父的左子树{Node* uncle = granderfather->_right;if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可{uncle->_col = parent->_col = BLACK;granderfather->_col = RED; //当前子树可能为部分，继续向上调整cur = granderfather;parent = cur->_parent;}else  //叔叔为空或为黑色{ //     g//   p   u// cif (cur == parent->_left)  //当前为父亲的左子树{RotateR(granderfather);granderfather->_col = RED;parent->_col = BLACK;}else   //当前为父亲的右子树{//    g//  p   u//    c//左右双旋RotateL(parent);RotateR(granderfather);granderfather->_col = RED;cur->_col = BLACK;}break;}}else  //父亲是祖父的右子树{Node* uncle = granderfather->_left;if (uncle && uncle->_col == RED)  //叔叔不空并且为红{parent->_col = uncle->_col = BLACK;granderfather->_col = RED;  //当前可能为部分子树，需要继续上调cur = granderfather;parent = cur->_parent;}else  //叔叔为空或为黑色{if (cur == parent->_right)  //当前为父亲的右{//    g//  u   p//        c//左旋RotateL(granderfather);parent->_col = BLACK;granderfather->_col = RED;}else  //当前为父亲的左{//   g// u   p//   c//右左双旋RotateR(parent);RotateL(granderfather);cur->_col = BLACK;granderfather->_col = RED;	}break;}}}_root->_col = BLACK; //保持根部为黑色return true;}/// //
/// /
/// 	测试代码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)  //到根部看看当前路径黑色节点和标准值是否一致{//cout << balcknum << endl;if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}/检查子比较复杂，可以反过来去检查红节点父是否为黑色if (root->_col == RED && 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(){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);}int Height(){return _Height(_root);}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;}Node* Find(K key){return _Find(key, _root);}Node* _Find(K key, Node* root){if (root == nullptr)return nullptr;if (key > root->_kv.first) //在右子树{return _Find(key, root->_right);}else if (key < root->_kv.first) //在左子树{return _Find(key, root->_left);}else  //找到了{return root;}}private:Node* _root = nullptr;void RotateL(Node* parent)  //左单旋,rotate->旋转{Node* SubR = parent->_right;Node* SubRL = SubR->_left;  //这个有可能为空Node* ppnode = parent->_parent;  //原来父亲的父亲parent->_right = SubRL;if (SubRL)  SubRL->_parent = parent;SubR->_left = parent;parent->_parent = SubR;if (ppnode == nullptr)  //旋转的是整颗树{_root = SubR;SubR->_parent = nullptr;}else  //旋转的是部分{if (ppnode->_left == parent) //是左子树{ppnode->_left = SubR;}else  //是右子树{ppnode->_right = SubR;}SubR->_parent = ppnode;}}void RotateR(Node* parent)  //右单旋细节处理和左单旋差不多{Node* SubL = parent->_left;Node* SubLR = SubL->_right;  //这个有可能为空Node* ppnode = parent->_parent;parent->_left = SubLR;if (SubLR)  SubLR->_parent = parent;SubL->_right = parent;parent->_parent = SubL;if (ppnode == nullptr)  //旋转的是整颗树{_root = SubL;SubL->_parent = nullptr;}else  //旋转部分{if (ppnode->_left == parent)  //是左子树{ppnode->_left = SubL;}else  //右子树{ppnode->_right = SubL;}SubL->_parent = ppnode;}}
};

相关文章：

  • 【数据结构】栈与队列面试题（C语言）
  • 矩阵运算_矩阵的协方差矩阵/两个矩阵的协方差矩阵_求解详细步骤示例
  • 机器学习第8天：SVM分类
  • 【论文阅读】A Survey on Video Diffusion Models
  • Linux--网络概念
  • ZJU Beamer学习手册（二）
  • 全志XR806基于http的无线ota功能实验
  • 创新研报｜新业务发展是CEO推动企业增长的必要选择 – Mckinsey研究
  • 音视频项目—基于FFmpeg和SDL的音视频播放器解析（十）
  • android开发连接网络
  • Leetcode—141.环形链表【简单】
  • csapp深入理解计算机系统 bomb lab(1)phase_1
  • Redis数据的持久化
  • SpringCloud Alibaba详解
  • NoSQL 与传统数据库的集成
  • IE9 : DOM Exception: INVALID_CHARACTER_ERR (5)
  • 分享的文章《人生如棋》
  • 【跃迁之路】【641天】程序员高效学习方法论探索系列（实验阶段398-2018.11.14）...
  • 【跃迁之路】【669天】程序员高效学习方法论探索系列（实验阶段426-2018.12.13）...
  • fetch 从初识到应用
  • Flex布局到底解决了什么问题
  • Java 内存分配及垃圾回收机制初探
  • Javascript设计模式学习之Observer(观察者)模式
  • JavaScript设计模式与开发实践系列之策略模式
  • java中的hashCode
  • Redis字符串类型内部编码剖析
  • SpiderData 2019年2月25日 DApp数据排行榜
  • Swift 中的尾递归和蹦床
  • 闭包--闭包之tab栏切换(四)
  • 不用申请服务号就可以开发微信支付/支付宝/QQ钱包支付！附：直接可用的代码+demo...
  • 从@property说起（二）当我们写下@property (nonatomic, weak) id obj时，我们究竟写了什么...
  • 从零开始的无人驾驶 1
  • 大整数乘法-表格法
  • 短视频宝贝=慢？阿里巴巴工程师这样秒开短视频
  • 聊聊directory traversal attack
  • 容器服务kubernetes弹性伸缩高级用法
  • 时间复杂度与空间复杂度分析
  • 手写双向链表LinkedList的几个常用功能
  • 问题之ssh中Host key verification failed的解决
  • 详解移动APP与web APP的区别
  • 小程序开发中的那些坑
  • 一个JAVA程序员成长之路分享
  • 移动端解决方案学习记录
  • AI算硅基生命吗，为什么？
  • 带你开发类似Pokemon Go的AR游戏
  • 函数计算新功能-----支持C#函数
  • 浅谈sql中的in与not in,exists与not exists的区别
  • ​HTTP与HTTPS：网络通信的安全卫士
  • #经典论文 异质山坡的物理模型 2 有效导水率
  • #每日一题合集#牛客JZ23-JZ33
  • （1）虚拟机的安装与使用,linux系统安装
  • (Matlab)遗传算法优化的BP神经网络实现回归预测
  • （Oracle）SQL优化技巧（一）：分页查询
  • （大众金融）SQL server面试题（1）-总销售量最少的3个型号的车及其总销售量
  • （附源码）spring boot校园健康监测管理系统 毕业设计 151047