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

【C++】：红黑树深度剖析 --- 手撕红黑树！

news 来源：原创 2024/9/20 21:27:08

目录

  • 前言
  • 一，红黑树的概念
  • 二，红黑树的性质
  • 三，红黑树节点的定义
  • 四，红黑树的插入操作
    • 4.1 第一步
    • 4.2 第二步
    • 4.3 插入操作的完整代码
  • 五，红黑树的验证
  • 六，实现红黑树的完整代码
  • 五，红黑树与AVL树的比较

点击跳转至上一篇文章： 【C++】：AVL树的深度解析及其实现

点击跳转至文章：【C++】：二叉树进阶 — 搜索二叉树

前言

上一篇文章介绍了什么是AVL树和AVL树的实现，AVL树也有它的缺点：就是太过追求绝对平衡，比如在插入时要维护其绝对平衡，旋转次数太多，在删除时甚至有可能要一直旋转到根位置，使之性能低下。

本篇文章介绍的红黑树也是一种平衡树，是通过改变节点颜色以及旋转操作，使之接近平衡。

红黑树比AVL树的用途更加广泛，在一些方面效率甚至要优于AVL树，并且 map/set 的底层封装用的也是红黑树。

一，红黑树的概念

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

在这里插入图片描述

二，红黑树的性质

(1) 每个结点不是红色就是黑色 ；
(2) 根节点是黑色的 ；
(3) 如果一个节点是红色的，则它的两个孩子结点是黑色的（重点）；
(4) 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（重点） ；
(5) 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，这条性质可有可无，平时不关注)。

三，红黑树节点的定义

红黑树的节点结构与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(BLACK){}
};

四，红黑树的插入操作

首先我们要思考一个问题，插入节点时，到底是插入红色节点还是黑色节点？为什么？

答案：插入红色节点。

因为我们知道红黑树最重要的两条性质是第(3)(4)条，通过维护这两条规则使之成为红黑树，而当新插入一个节点时，必定会破坏两条规则之一。

假设插入节点为黑色节点，则所有路径的黑色节点数量均不相同，如何让它们相同将是一个巨大的难题，而插入红色节点(此时一定是作为孩子节点)，就破坏规则(3)，但是只要根据其父亲和叔叔节点进行适当的变色就可以继续恢复规则(3)。

显而易见，规则(3)(4)就好比"慈父严母"，非要选择得罪其中一人，那当然是"慈父"了。

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

4.1 第一步

按照二叉搜索的树规则插入新节点：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);//新增节点，颜色为红色cur->_col = RED;//链接时要判断链接在parent的左还是右if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//检测新节点插入后，红黑树的性质是否造到破坏//……}

4.2 第二步

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

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

约定：
(1) cur 为当前节点，p为父节点，g为祖父节点，u为叔叔节点

(2) 下面的抽象图中，a/b/c/d/e 表示具有 n 个节点的红黑树，n >=0。

(一) 情况一: cur为红，p为红，g为黑，u存在且为红：

在这里插入图片描述

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

(二) 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

在这里插入图片描述

下面我们根据 u 的情况用具象图分别解释单旋与双旋操作：

(1) u 不存在，a/b/c/d/e都是空，cur 是新增：

p为g的左孩子，cur为p的左孩子，则进行右单旋转，再 p 变黑，g 变红：

在这里插入图片描述

相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转，再 p 变黑，g 变红：

在这里插入图片描述

p为g的左孩子，cur为p的右孩子，先针对p做左单旋转，再针对 g 做右单旋，cur 变黑，g 变红：

在这里插入图片描述

(2) u 存在且为黑

单旋情况：

在这里插入图片描述
双旋情况：
在这里插入图片描述

4.3 插入操作的完整代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);//新增节点，颜色为红色cur->_col = RED;//链接时要判断链接在parent的左还是右if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//    g// p     uif (parent == grandfather->_left){//找到u的位置Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//u存在且为红,把p/u变黑，g变红,继续向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_left){//     g//  p     u    //c//单旋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;//u存在且为红,把p/u变黑，g变红,继续向上调整if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_right){//    g// u      p//            c//单旋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;
}

五，红黑树的验证

红黑树的检测分为两步：

(1) 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
(2) 检测其是否满足红黑树的性质

这里重点检测的是性质(3)与性质(4)。

检测性质(3)：只要判断当前节点与其父亲节点是否为连续的红色节点；

检测性质(4)：先计算出任意一条路径上的黑色节点作为参考值，再用这个参考值与其他路径上的黑色节点数量比较。

private://中序遍历void InOrder(){_Inorder(_root);cout << endl;}//判断是否平衡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 << "存在连续的红色节点" << endl;return false;}//blackNum表示：根节点到当前节点的路径上黑色节点的数量if (root->_col == BLACK)blackNum++;return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}

六，实现红黑树的完整代码

RBTree.h

#pragma once#include <iostream>
#include <assert.h>
using namespace std;//枚举颜色
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(BLACK){}
};template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:Node* Find(const pair<K, V>& kv){Node* cur = _root;while (cur){if (cur->_kv.first > kv.first)cur = cur->_left;else if (cur->_kv.first < kv.first)cur = cur->_right;elsereturn cur;}return nullptr;}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new Node(kv);//新增节点，颜色为红色cur->_col = RED;//链接时要判断链接在parent的左还是右if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//    g// p     uif (parent == grandfather->_left){//找到u的位置Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//u存在且为红,把p/u变黑，g变红,继续向上调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_left){//     g//  p     u    //c//单旋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;//u存在且为红,把p/u变黑，g变红,继续向上调整if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//u不存在或存在且为黑if (cur == parent->_right){//    g// u      p//            c//单旋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;}//中序遍历void InOrder(){_Inorder(_root);cout << endl;}//判断是否平衡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://每个节点的位置记录一个值blackNum//blackNum表示：根节点到当前节点的路径上黑色节点的数量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 << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK)blackNum++;return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;if (subLR)subLR->_parent = parent;parent->_left = subLR;subL->_right = parent;//改变之前记录Node* ppNode = parent->_parent;parent->_parent = subL;//parent为根if (parent == _root){_root = subL;_root->_parent = nullptr;}else{//parent为一颗子树if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;if (subRL)subRL->_parent = parent;parent->_right = subRL;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;//parent为根if (parent == _root){_root = subR;_root->_parent = nullptr;}else{//parent为一颗子树if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}
private:Node* _root = nullptr;
};//测试代码
void Test1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 16,3,7,11,9,26,18,14,15 };RBTree<int, int> t;for (auto e : a)t.Insert({ e ,e });t.InOrder();cout << t.IsBalance() << endl;
}

Test.cpp

#include "RBTree.h"int main()
{Test1();return 0;
}

运行结果如下：

中序遍历是有序的，说明是搜索二叉树，返回1，说明满足红黑树的性质，是平衡树。

在这里插入图片描述

五，红黑树与AVL树的比较

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

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • MySQL之索引及简单运用
  • 文本编辑三巨头（grep）
  • 【Node.js基础04】node.js模块化
  • 个人电脑网络安全 之 防浏览器和端口溢出攻击 和 权限对系统的重要性
  • C++ set
  • vue3学习记录1：emit的写法
  • java8函数式编程学习（二）：optional，函数式接口和并行流的学习
  • Java-根据前缀-日期-数字-生成流水号（不重复）
  • 力扣34题 双二分查找（简单易懂）
  • go语言的命名规则
  • C#中的Func
  • 探索 IPython %%sql 魔术：数据库交互的高效工具
  • git 使用教程
  • 压测实操--kafka-consumer压测方案
  • 【MSP430】DriverLib库函数，GPIO相关函数介绍
  • fetch 从初识到应用
  • httpie使用详解
  • Joomla 2.x, 3.x useful code cheatsheet
  • MySQL QA
  • PaddlePaddle-GitHub的正确打开姿势
  • ReactNative开发常用的三方模块
  • uva 10370 Above Average
  • Vue.js-Day01
  • vue：响应原理
  • 马上搞懂 GeoJSON
  • 说说动画卡顿的解决方案
  • 网页视频流m3u8/ts视频下载
  • 数据库巡检项
  • 新海诚画集[秒速5センチメートル:樱花抄·春]
  • ​力扣解法汇总1802. 有界数组中指定下标处的最大值
  • # 20155222 2016-2017-2 《Java程序设计》第5周学习总结
  • #define与typedef区别
  • （11）工业界推荐系统-小红书推荐场景及内部实践【粗排三塔模型】
  • （3）llvm ir转换过程
  • （5）STL算法之复制
  • （9）STL算法之逆转旋转
  • (iPhone/iPad开发)在UIWebView中自定义菜单栏
  • （JS基础）String 类型
  • （PHP）设置修改 Apache 文件根目录 (Document Root)（转帖）
  • (poj1.3.2)1791(构造法模拟)
  • (几何:六边形面积)编写程序，提示用户输入六边形的边长，然后显示它的面积。
  • (三)docker：Dockerfile构建容器运行jar包
  • （算法）N皇后问题
  • （一）RocketＭＱ初步认识
  • (原創) 未来三学期想要修的课 (日記)
  • （转）人的集合论——移山之道
  • .helper勒索病毒的最新威胁：如何恢复您的数据？
  • .NET 5.0正式发布，有什么功能特性(翻译)
  • .net 写了一个支持重试、熔断和超时策略的 HttpClient 实例池
  • .net程序集学习心得
  • .NET单元测试使用AutoFixture按需填充的方法总结
  • .NET开源纪元：穿越封闭的迷雾，拥抱开放的星辰
  • .NET连接MongoDB数据库实例教程
  • .NET轻量级ORM组件Dapper葵花宝典
  • .NET序列化 serializable，反序列化