首页/新闻资讯/正文详情

红黑树原理 红黑树五大性质 二叉搜索树 平衡树 HashMap红黑树 面试

发布时间:2026/9/27 22:03:58 来源:云帆数科 栏目:资讯中心
红黑树原理 红黑树五大性质 二叉搜索树 平衡树 HashMap红黑树 面试
基础不牢地动山摇。上一期讲HashMap我们提到一个关键词链表过长会转成红黑树。很多新手卡在这二叉搜索树是什么平衡树是什么红黑树到底好在哪HashMap为什么不直接用AVL树网上很多教程一上来甩一堆复杂定义、旋转代码越看越懵。今天我们循序渐进从最简单二叉树开始大白话拆解红黑树搞懂HashMap引入红黑树的目的。一、铺垫二叉搜索树BST二叉搜索树规则想象一个图书馆书架每个书架格子节点最多分出左右两个分支左格子、右格子左边分支放的书编号 当前格子书编号右边分支放的书编号 当前格子书编号✅ 优点找书很快类似二分查找理想情况下O(logn)每次排除一半分支❌ 致命缺陷如果按顺序放书1、2、3、4、5依次放进去书架会直接变成一条竖长的单列例子依次放编号1、2、3、4、5的书全部只能往右放。此时找编号5的书必须一本一本从头翻查询从O(logn)降级成O(n)和一条链表没有区别。 所以就诞生了平衡二叉树目标不让书架“长歪”左右两边高度差距不能太大。二、AVL平衡树平衡二叉搜索树AVL树规则书架左右两个分支高度差不能超过1。一旦左右高度差超标立刻挪动书本旋转调整平衡。✅ 查询极快书架永远整齐对称❌ 缺点每次新增/拿走一本书很容易触发挪动书本调整成本很高。放到HashMap场景频繁put新增、remove删除元素AVL树不停挪节点开销太大不合适。三、红黑树是什么一句话总结红黑树一种弱平衡二叉搜索树。类比它不会像AVL树那样要求绝对平衡不追求书架绝对左右对称只做一条硬性限制从起点到最远端最长的找书路径不能超过最短路径的2倍。怎么做到给每本书贴标签红色标签、黑色标签5条标签规则约束书架防止书架严重歪掉。平衡要求放宽换来新增、拿走书本时挪动书本旋转次数更少写操作性能更好。通过给节点标记红色/黑色加上5条约束规则限制树不会严重“长歪”。权衡之后插入、删除时旋转次数更少写操作性能更好查询不错增删代价低。HashMap选择它就是看中这个取舍。四、红黑树五大核心性质节点只有两种颜色红色、黑色。根节点一定是黑色。所有叶子节点NIL空节点都是黑色。红色节点的两个子节点必须是黑色。不能出现两个红节点相连。从任意一个节点到它所有后代叶子节点经过的黑色节点数量必须相同黑高一致。✅ 记住核心推论因为规则4、5最长路径最多是最短路径2倍树不会极端倾斜。五、红黑树如何维持平衡变色 旋转新增/拿走一本书会破坏上面5条标签规则红黑树用两种方式修复书架变色改标签红标签改成黑、黑改成红成本最低优先用这个方案。只换标签不用挪动书本。旋转挪动书本左旋、右旋调整书本的上下父子位置不改变书本编号的大小顺序。对比AVLAVL书架稍微不对称就要挪书旋转红黑树优先换标签变色实在不行才挪书旋转次数很少。六、回到HashMap为什么要用红黑树而不是AVL回顾HashMap场景哈希桶上链表过长≥8链表查询O(n)太慢需要升级树。AVL树严格平衡查询快但是增删频繁旋转put/remove旋转多开销大。红黑树弱平衡查询接近AVL增删旋转次数少综合性能更好。所以很多标准库都用红黑树比如C 的std::map、std::setJava 的TreeMap、TreeSetLinux 内核里的一些数据结构HashMap的访问模式查询多但是put、remove也不少红黑树综合性价比更高。补充当树节点减少到≤6红黑树退化成链表。因为节点很少的时候链表遍历更快省去树维护成本。七、高频坑点红黑树不是绝对平衡树是弱平衡不要和AVL混淆。红黑树平衡不靠高度差靠颜色规则约束黑高。HashMap树化不是只要链表≥8就转树还要求数组容量≥64数组容量不足优先扩容不树化。红黑树的节点除了key/value还会保存左右子节点、父节点、颜色标记内存占用比链表节点更大。节点少的时候链表更省内存。专栏总结二叉搜索树有序但是容易长歪退化成链表。AVL树严格平衡查询快但是增删旋转开销巨大。红黑树是弱平衡二叉搜索树通过红黑5条规则约束最长路径不超过最短路径2倍。修复手段优先变色必要时左旋/右旋。增删的旋转次数远少于AVL。HashMap选用红黑树在查询性能和增删维护成本之间做权衡。节点少时链表更合适节点多了升级红黑树节点变少再退回链表。欢迎点赞收藏关注下一期继续更新Java 泛型让我们一起轻松学习每个知识点。

相关推荐

Claude Code 究竟牛在哪里?从 settings.json 到 TaoToken 的 AI Agent 配置实战
Claude Code 究竟牛在哪里?从 settings.json 到 TaoToken 的 AI Agent 配置实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 22:03:58

QML 自定义按钮:带图标变形过渡效果的按钮
QML 自定义按钮:带图标变形过渡效果的按钮

目录 最终效果 核心原理 播放变暂停 状态怎么变化 可调参数 适用场景 完整代码 工程下载 这篇做一个图标形变按钮,点击时图标平滑变形,三横线菜单变成 X 关闭、播放三角变成暂停双竖线。 最终效果 16056 的按钮,点击时图标平滑变形,文字也同步切换。示例里有两个按钮,一个… · 2026/9/27 22:03:58

3步搞定怎么用wordpress打开网站图解步骤新手避坑指南
3步搞定怎么用wordpress打开网站图解步骤新手避坑指南

3步搞定怎么用wordpress打开网站图解步骤新手避坑指南 很多新手卡在第一步就头晕,域名服务器搞不懂,对着浏览器地址栏发呆。别慌,这套怎么用wordpress打开网站图解步骤专治各种“小白症”。哪怕你连什么是DNS都没听过,跟着这篇实操… · 2026/9/27 22:03:52

NumPy的扩展:SciPy
NumPy的扩展:SciPy

SciPy是一个非常著名的开源计算库, 它专门用于科学研究领域, 这套库是依托在NumPy基础之上构建出来的, 它还额外提供了许多功能模块, 其中包括对数据进行数值积分的操作能力、实现最优化求解的功能、进行统计分析的工具以及调用各类专用函数的手段。1、先把那些.mat格式的文件给… · 2026/9/27 22:34:48

Python中判断列表是否包含某个元素的方法大全
Python中判断列表是否包含某个元素的方法大全

关于如何在中判断列表是否包含某个元素这一事情, 现将所有的方法都进行一个全面的汇总。更新时间是2026年01月04日09:25:34, 作者是Sitin涛哥。在编写代码的过程当中, 大家经常需要做的一件事, 就是去查一个列表里到底有没有包含某个特定的东西。在这篇文章里面, 我们会好好地剖… · 2026/9/27 22:34:48

print(squared_numbers)
print(squared_numbers)

Enum是绑定到唯一值的一组符号名, 它们类似于全局变量, 但它们提供了更有用的repr()、分组、类型安全和其他一些特性。请用户提供您需要改写的句子内容。from enum import Enumclass Status(Enum):NO_STATUS -1NOT_STARTED 0IN_PROGRESS 1COMPLETED 2print(Status.IN_PROGR… · 2026/9/27 22:34:48

少切屏、多提效:Gitee 企业版 MCP Server 配 TaoToken 的 settings.json 骨架
少切屏、多提效:Gitee 企业版 MCP Server 配 TaoToken 的 settings.json 骨架

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 22:34:48

2026最新5款Cursor平替实测合集:TaoToken统一Key接入TRAE/Windsurf/CodeBuddy配置骨架
2026最新5款Cursor平替实测合集:TaoToken统一Key接入TRAE/Windsurf/CodeBuddy配置骨架

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 22:34:42

10个图像处理的Python库
10个图像处理的Python库

来源:Deephub IMBA本文约1600字,建议阅读5分钟无论你是刚开始基本的图像处理还是探索高级机器学习模型,这些库都为广泛的图像处理任务提供了必要的工具。在这篇文章中, 我们要把计算机视觉项目里常用到的库整理一遍, 大家要是想要进入计算机视… · 2026/9/27 22:34:42

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码