Loading [MathJax]/jax/input/TeX/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >红黑树

红黑树

原创
作者头像
大学里的混子
修改于 2019-03-04 06:49:05
修改于 2019-03-04 06:49:05
7750
举报
文章被收录于专栏:LeetCodeLeetCode

红黑树的介绍

红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树。 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值。 除了具备该特性之外,红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色,颜色是红(Red)或黑(Black)。 红黑树的特性: (1) 每个节点或者是黑色,或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!] (4) 如果一个节点是红色的,则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性,需要注意的是: 第一,特性(3)中的叶子节点,是只为空(NIL或null)的节点。 第二,特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

红黑树示意图如下:

AVL树的介绍

https://www.cnblogs.com/skywang12345/p/3577479.html

AVL树是高度平衡的而二叉树。它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。 

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
[转]红黑树
先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
DH镔
2019/12/20
8080
[转]红黑树
Java数据结构与算法解析(十一)——红黑树
前面一篇文章介绍了2-3查找树,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgN,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,本文介绍一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree)
老马的编程之旅
2022/06/22
4260
Java数据结构与算法解析(十一)——红黑树
001 红黑树(二)之 C语言的实现(1)
红黑树在日常的使用中比较常用,例如Java的TreeMap和TreeSet,C++的STL,以及Linux内核中都有用到。之前写过一篇文章专门介绍红黑树的理论知识,本文将给出红黑数的C语言的实现代码,后序章节再分别给出C++和Java版本的实现。还是那句话,三种实现原理相同,择其一了解即可;若文章有错误或不足的地方,望不吝指出! 目录 1.红黑树的介绍 2.红黑树的C实现(代码说明) 3.红黑树的C实现(完整源码) 4.红黑树的C测试程序 更多内容:数据结构与算法系列 目录 (01) 红黑树(一)之 原理和算法详细介绍 (02) 红黑树(二)之 C语言的实现 (03) 红黑树(三)之 Linux内核中红黑树的经典实现 (04) 红黑树(四)之 C++的实现 (05) 红黑树(五)之 Java的实现 (06) 红黑树(六)之 参考资料
范蠡
2019/07/01
1.5K0
001 红黑树(二)之 C语言的实现(1)
算法之红黑树
红黑树(一) 原理和算法详细介 1 R-B Tree简介     R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。 红黑树的特性: (1)每个节点或者是黑色,或者是红色。 (2)根节点是黑色。 (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!] (4)如果一个节点是红色的,则它的子节点必须是黑色的。 (5)从一个节点到该节点的子
xiangzhihong
2018/02/01
1.1K0
算法之红黑树
重温数据结构:深入理解红黑树
读完本文你将了解到: 什么是红黑树 黑色高度 红黑树的 5 个特性 红黑树的左旋右旋 指定节点 x 的左旋 右图转成左图 指定节点 y 的右旋左图转成右图 红黑树的平衡插入 二叉查找树的插入 插入后
张拭心 shixinzhang
2018/01/05
1.3K0
重温数据结构:深入理解红黑树
【动态图文详解,史上最易懂的红黑树讲解】手写红黑树(Red Black Tree)
红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)。
一个会写诗的程序员
2020/11/03
19.8K1
【动态图文详解,史上最易懂的红黑树讲解】手写红黑树(Red Black Tree)
红黑树是怎么实现的,看这篇真的就够了!
红黑树由来:在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees),后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树,就此红黑树出现在软件开发者的视野里!
纯洁的微笑
2020/03/12
4.1K0
红黑树
红黑树
Java架构师必看
2021/04/30
7230
红黑树
红黑树深入浅出
先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
bear_fish
2018/09/20
6600
红黑树深入浅出
重学数据结构和算法(二)之二叉树、红黑树、递归树、堆排序
最近学习了极客时间的《数据结构与算法之美]》很有收获,记录总结一下。 欢迎学习老师的专栏:数据结构与算法之美 代码地址:https://github.com/peiniwan/Arithmetic
六月的雨
2021/03/04
4490
奈学:红黑树(RedBlackTree)的概述
AVL树是一种自平衡的二叉查找树,又称平衡二叉树。AVL用平衡因子判断是否平衡并通过旋转来实现平衡,它的平衡的要求是:所有节点的左右子树高度差不超过1。AVL树是一种高平衡度的二叉树,执行插入或者删除操作之后,只要不满足上面的平衡条件,就要通过旋转来保持平衡,而的由于旋转比较耗时,由此我们可以知道AVL树适合用于插入与删除次数比较少,但查找多的情况。   由于维护这种高度平衡所付出的代价可能比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。   红黑树(Red Black Tree),它一种特殊的二叉查找树,是AVL树的特化变种,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 红黑树的平衡的要求是:从根到叶子的最长的路径不会比于最短的路径的长超过两倍。 因此,红黑树是一种弱平衡二叉树,在相同的节点情况下,AVL树的高度<=红黑树。   红黑树是用弱平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,降低了对旋转的要求,从而提高了性能,所以对于查询,插入,删除操作都较多的情况下,用红黑树。
江帅帅
2020/08/26
1.4K0
HashMap为什么用链表加红黑树?目的是什么?原理是什么
关于hashmap的其他有关问题我在源码研究专栏中都有讲解,深入到源码层次的讲解,绝对一看就懂 链接: 深入源码,探究设计思想
向着百万年薪努力的小赵
2022/12/02
2.5K0
HashMap为什么用链表加红黑树?目的是什么?原理是什么
二叉树及其作用浅析
树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。先从整体上认识下二叉树及其他各种树的区别和用途。
杨永贞
2022/01/07
3.7K0
二叉树及其作用浅析
数据结构--红黑树 Red Black Tree
1.概念 二叉树在频繁动态增删后,可能退化成链表,时间复杂度由 O(lgn) 变成 O(n)。(不平衡) 平衡二叉树,树中任意一个节点的左右子树的高度相差 <= 1。完全二叉树、满二又树其实都是平衡二
Michael阿明
2021/02/20
3040
数据结构--红黑树 Red Black Tree
图解红黑树
红黑树(Red-black tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,常用于关联数组、字典等。C++ 中的标准关联容器 set、multiset、map、multimap 内部采用的数据结构就是红黑树。
yhlin
2023/02/27
1.3K0
图解红黑树
我画了 20 张图,给女朋友讲清楚红黑树
红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java 的 TreeMap 和 TreeSet 就是基于红黑树实现的。
五分钟学算法
2019/12/19
5790
我画了 20 张图,给女朋友讲清楚红黑树
文心一言 VS 讯飞星火 VS chatgpt (247)-- 算法导论18.1 5题
如果红黑树中的每个黑结点吸收它的红色孩子,并把它们的孩子作为自己的孩子,这种操作会破坏红黑树的性质,因为红黑树要求从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。这种操作可能会导致某些路径上的黑色结点数量减少,从而不再满足红黑树的定义。
福大大架构师每日一题
2024/04/30
850
文心一言 VS 讯飞星火 VS chatgpt (247)-- 算法导论18.1 5题
动画红黑树,旋转的艺术
对于程序员来说,红黑树是一个用的很多但是很少去实现的一种数据结构,用的多是因为高效,不管是插入删除操作还是查找操作,复杂度都是
ACM算法日常
2021/05/11
1.4K1
【Java】基础篇-排序二叉树
大家好,最近更新的稍微慢了许多,参加了一些公司和外界的技术培训,也跟一些小伙伴聊了些技术文章,总的来说很不理想,讲的内容高大上,落地的过程踩坑很严重,和没听的效果差不多,感觉这几年,圈子太浮躁了,对新技术趋之若鹜,恨不得昨天出来,今天就用到项目上。很值得我反思了。
haoming1100
2019/05/31
7510
相关推荐
[转]红黑树
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档