第八节:红黑树(初阶)

devtools/2025/3/16 10:58:41/

【本节要点】

  • 红黑树概念
  • 红黑树性质
  • 红黑树结点定义
  • 红黑树结构
  • 红黑树插入操作的分析

一、红黑树的概念与性质

1.1 红黑树的概念

红黑树 ,是一种 二叉搜索树 ,但 在每个结点上增加一个存储位表示结点的颜色,可以是 Red和 Black 。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍 ,因而是 接近平衡 的。
红黑树构造:[10(黑)] /        \[5(红)]     [20(黑)]/     \       /     \[3(黑)] [8(黑)] [15(红)] [25(红)]/  \    /  \     /  \    /  \NIL NIL  NIL NIL  NIL NIL NIL NIL

1.2 红黑树的性质 

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

 以上五点性质可以保证:其最长路径中节点个数不会超过最短路径节点个数的两倍。

 二、红黑树结点定义

// 结点的颜色
enum Colour
{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; // 结点的双亲(红黑树需要旋转,为了实现简单所以给出该结点)Colour _col;               // 结点的颜色// 结点的构造函数RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};

注意:红黑树定义结点时,默认结点颜色为红色,这一设计选择直接增加红黑树的平衡维护效率和整体性能,大大减少时间复杂度。

三、红黑树的结构

// 以本数组为例
num[3, 5, 8, 10, 15, 20, 25]
红黑树构造:[10(黑)] /        \[5(红)]     [20(黑)]/     \       /     \[3(黑)] [8(黑)] [15(红)] [25(红)]/  \    /  \     /  \    /  \NIL NIL  NIL NIL  NIL NIL NIL NIL

图示说明

  1. 根结点标记:根结点 10 为黑色,符合性质2(根结点必黑)

  2. 红色结点规则:红色结点 51525 的子结点均为黑色,满足性质3(红色结点不连续)

  3. 黑高一致性验证:从根结点到任意 NIL 的路径黑色结点数均为 2

  4. NIL结点处理:所有叶子结点显式标记为 NIL(黑色),符合性质5

  5. 最长/最短路径对比

    路径类型示例路径结点数比例
    最短路径10→20→NIL21:1
    最长路径10→5→3→NIL31.5:1
    理论极限红黑交替路径(未出现)≤4≤2:1

 四、红黑树的插入操作

                              [开始插入新结点Z]│▼┌─────────执行标准BST插入─────────┐│                                │▼                                ▼[Z设为红色]                   [保持BST性质]│▼┌─────父结点P是否为红色?─────┐│                            │▼ (是)                       ▼ (否)[存在双红冲突需处理]               [插入完成]│▼┌────叔结点U的颜色?────┐│                      │▼ (红色)               ▼ (黑色/NIL)
[Case1: 颜色翻转]     [判断冲突结构类型]│                      │▼                      ├─────────────────────────┐
[将P、U设为黑色]           ▼                         ▼│               [Z-P-G呈三角型]            [Z-P-G呈直线型]▼                      │                         │
[将G设为红色]        [Case2: 旋转父结点]      [Case3: 旋转祖父结点]│                      │                         │▼                      ▼                         ▼
[以G为新Z向上回溯]   [转为直线型冲突]         [交换颜色并旋转]│▼[调整完成]│▼[最终确保根结点为黑]

4.1 基本BST插入阶段

  • 插入位置遵循二叉搜索树规则

  • 新结点初始颜色必须为红色(最小化规则破坏)

4.2 冲突检测阶段

  • 要素1:父结点状态判断
  • 要素2:叔结点颜色判定
  • 要素3:冲突结构类型识别

4.3  典型场景演练

场景1:叔结点为红(Case1)

         G(黑)                 G(红)/   \     颜色翻转     /   \P(红) U(红)  →       P(黑) U(黑)/                   /Z(红)              Z(红)

检测要点

  • 确认U存在且为红

  • 将冲突标记上移给G

  • 继续以G作为新Z向上检测

场景2:叔结点为黑-三角型(Case2)

     G(黑)            G(黑)/               /P(红)   →      Z(红)\           /Z(红)     P(红)

检测要点

  • 判断Z是P的右子结点

  • 识别为三角型冲突

  • 转换为直线型处理

场景3:叔结点为黑-直线型(Case3)

      G(黑)             P(黑)/               /   \P(红)   →      Z(红) G(红)/Z(红)

检测要点

  • 确认Z是P的左子结点

  • 直接触发祖父旋转

  • 完成颜色交换

 4.4 总结

冲突检测阶段通过三级条件筛选(父结点状态→叔结点颜色→冲突结构类型),将复杂的平衡问题分解为可控的局部操作。这种分层检测机制:

  1. 确保90%以上的插入操作只需1次检测即可完成
  2. 将最坏情况的时间复杂度严格控制在O(log n)
  3. 为后续的旋转/颜色调整提供精准的操作依据

该设计体现了红黑树"以检测换计算,以分类求高效"的核心优化思想,是其能在大规模数据场景下保持卓越性能的关键所在。


以上就是红黑树初阶知识的了解,接下来我会继续更新红黑树进阶红黑树的模拟实现、使用红黑树底层对map和set容器的模拟实现。制作不易,请大家多多点赞收藏啦!!


http://www.ppmy.cn/devtools/167536.html

相关文章

Flutter三棵树是什么,为什么这么设计

目录 1. 三棵树的定义与职责 (1) Widget 树 (2) Element 树 (3) RenderObject 树 2. 三棵树的协同工作流程 3. 为什么设计三棵树&#xff1f; (1) 性能优化 (2) 逻辑解耦 (3) 灵活性 4. 三棵树的设计优势总结 示例&#xff1a;动态列表更新 常见面试追问 Flutter 的…

【gopher的java学习笔记】如何知道一个jar包对应的maven中的groupId和atrifactId

java程序常见的一个错误之一就是通过Class类的方法&#xff08;比如Class.forName&#xff09;的时候会抛出ClassNotFoundException&#xff0c;要排查这个异常&#xff0c;就需要确认我们到底有没有这个Class。但是当我排查的时候&#xff0c;我发现我能排查的只是我的jar包里…

Node.js 模块的分类 require 的使用详细介绍

目录 1. 介绍 2. 模块的分类及 require 使用示例 1. 核心模块 2. 第三方模块 3. 自定义模块 3. require 的解析规则 4. 总结 1. 介绍 Node.js 采用模块化的方式组织代码&#xff0c;使得开发更加清晰、可维护&#xff0c;并且可以重复利用已有的代码。Node.js 模块主要分…

前端 Webpack 面试题

1、什么是 Webpack?它有什么作用? Webpack 是一个前端资源打包工具,用于将 JavaScript、CSS、图片等项目资源进行模块化管理和打包。它能够将复杂的项目结构转化为浏览器友好的代码,提高前端项目的开发效率和性能。 模块打包:Webpack 将项目中的各个模块及依赖打包成一个…

R语言零基础系列教程-01-R语言初识与学习路线

代码、讲义、软件回复【R语言01】获取。 R语言初识 R是一个开放的统计编程环境&#xff0c;是一门用于统计计算和作图的语言。“一切皆是对象”&#xff0c;数据、函数、运算符、环境等等都是对象。易学&#xff0c;代码像伪代码一样简洁&#xff0c;可读性高强大的统计和可视…

F4拉力赛(滑动窗口)

题目描述 F4拉力赛在一个环形公路上举行&#xff0c;主办方为了拉来更多赞助&#xff0c;在环形公路每间隔一米就设立一块广告牌。 假设赛车的速度为 x 米/秒&#xff0c;请问赛车在一秒内经过最多数量的广告牌编号是什么&#xff1f; 输入描述 第一行输入一个数组&#xf…

PowerInfer论文阅读

论文原文链接 论文github链接 论文结构 1. 引言 讨论了当前大语言模型的推理需求与挑战&#xff0c;尤其是在消费级GPU上运行模型的难点&#xff1a; 大语言模型的内存需求巨大&#xff0c;远超消费级GPU的容量。 数据中心部署的方法通常无法满足本地部署的低延迟需求。 …

图解AUTOSAR_CP_BSW_General

AUTOSAR BSW通用规范详解 AUTOSAR基础软件模块通用规范与架构解析 目录 1. 概述 1.1. AUTOSAR BSW通用规范简介1.2. 文档目的与范围2. BSW模块文件结构 2.1. 标准文件组织2.2. 命名规范3. BSW模块接口 3.1. 接口类型3.2. 模块API3.3. 配置参数4. BSW通用架构 4.1. 分层架构4.2.…