数据结构===红黑树

简介: 红黑树是平衡二叉搜索树,关键点在于其满足5个性质,包括根节点为黑,叶子为黑,红色节点不能相邻且路径上黑节点数相等。插入和删除时结合左旋、右旋操作。插入时,针对叔叔节点颜色(红或黑),参照AVL树的失衡处理,分为4种情况,并调整颜色策略。删除操作同样复杂,涉及节点替换和颜色调整。

概要
这篇说下红黑树
其实,红黑树,对于我来说,比较重要的几点。

满足几个条件
基本思想
插入
删除
这些是很重要的。
满足的条件
红黑树需要满足什么条件呢?
应该有四个,如下:

节点非黑既红
根节点是黑色
叶子(NIL)结点是黑色
红色节点下面接两个黑色节点
从根节点到叶子结点路径上,黑色节点数量相同
基本思想
这个,除了上边四个条件;还要有2个操作,左旋和右旋。
有了这些条件,再加上左旋右旋操作,接下来看看红黑树的插入,删除。
红黑树的插入
叔叔节点为红色的时候,修改三元组小帽子,改成红黑黑
叔叔节点为黑色的时候,参考 AVL 树的失衡情况,分成 L L , L R , R L , R R LL,LR,RL,RRLL,LR,RL,RR, 先参考 AVL 树的旋转调整策略,然后再修改三元组的颜色,有两种调整策略:红色上浮,红色下沉。
两大类情况,包含 8 种小情况

目录
相关文章
|
7月前
|
算法 C++
【数据结构与算法】—— 手撕红黑树
【数据结构与算法】—— 手撕红黑树
|
7月前
|
存储 关系型数据库 数据库
【数据结构】—红黑树(C++实现)
【数据结构】—红黑树(C++实现)
|
关系型数据库
|
4月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
106 1
【数据结构】红黑树——领略天才的想法
【数据结构】红黑树——领略天才的想法
|
2月前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
33 0
|
7月前
【数据结构】红黑树的原理及其实现
【数据结构】红黑树的原理及其实现
|
4月前
|
存储 Java 程序员
"揭秘HashMap底层实现:从数组到链表,再到红黑树,掌握高效数据结构的秘密武器!"
【8月更文挑战第21天】HashMap是Java中重要的数据结构,采用数组+链表/红黑树实现,确保高效查询与更新。构造方法初始化数组,默认容量16,负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素,利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制,提升性能。理解这些原理能帮助我们更高效地应用HashMap。
49 0
|
6月前
|
算法 架构师 NoSQL
【数据结构之红黑树】深入原理与实现
意节点的左子树和右子树的层高差不大于1,为了维护树的平衡,我们介绍了树的左右旋转。但是,AVL树维护平衡的代价是比较大的。所以,我们又介绍了红黑树这种数据结构,这是因为红黑树插入的效率相对AVL树是比较高的,在统计意义上来讲红黑树在插入和查找综合上效率是比较高的,这也是为什么红黑树为什么广泛应用在计算机各个方面。
56 2
|
6月前
|
C++
数据结构===红黑树
数据结构===红黑树