红黑树学习笔记之红黑树的结构

我会带着你远行 2022-05-26 06:29 262阅读 0赞

**一. 定义规则**

![70][]

**二. 实例**

**![70 1][]**

**1. 根节点是黑色。**

**2. 该树已经做过一个预处理，为所有有需要的节点，都添加了一个或者两个外部节点，而这些外部节点都是假想，实际上并不存在。**

**（注：在二叉树中，度数为0的节点就是外部节点，度数为2的节点就是内部节点）**

**3.每一个红节点，其父亲及孩子都是黑的。**

**4.外部节点到根，途中黑节点数目相等。**

**![70 2][]**

**三. 提升变换**

**为了更直观地理解红黑树的定义，将每一个红色的节点都向上提升至与它的父亲平齐。**

**![70 3][]**

**![70 4][]**

**四. 末端节点**

**![70 5][]**

**实施提升变换之后，提升之后，所有底层的节点都变成沿同一水平高度平齐的分布。**

**![70 6][]**

**五. 红黑树，即是B-树**

![70 7][]

**每个超级节点至少拥有2个分支，至多不超过4个分支。**

**六. 平衡性**

**![70 8][]**

**规模为n的红黑树，黑高度不超过O(logn)，高度不超过O(logn)。**

[70]: /images/20220526/d05d9cfa1fff4ae881a96776cae7259e.png
[70 1]: /images/20220526/8f0f224bd38a41dbb0b2b78a0a042e8f.png
[70 2]: /images/20220526/aaec3d198c5c46b89e46fc48ae13df81.png
[70 3]: /images/20220526/50457b2b270e41d688d3ee905ce413dc.png
[70 4]: /images/20220526/1198edbc574544e3aad01422d670b309.png
[70 5]: /images/20220526/d8590057a5d24e7ca4605a70b9d6792c.png
[70 6]: /images/20220526/2459a72a93794f2da63943c4d482f4a5.png
[70 7]: /images/20220526/6b77d0641f81482ab0c32bca1ee66da4.png
[70 8]: /images/20220526/5575656d3d40420ba07dd08fa0de895b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，262人围观）

还没有评论，来说两句吧...

相关阅读

相关红黑树学习

开始复习红黑树，根据算法4，上面先介绍2-3树，再引入红黑树方便理解红黑树是 2-3 查找树，但它不需要分别定义 2- 节点和 3- 节点，而是在普通的二叉查找树之上，为节

向右看齐/ 2023年06月01日 12:57/ 0 赞/ 79 阅读

相关树：红黑树

1，红黑树引入红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1，超过后需要进行左旋或者右旋操作再次对树进行平衡，虽然这样能够解决二叉树退化为链表的缺

╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 212 阅读

相关数据结构学习笔记 - 红黑树

红黑树一般讲到平衡二叉查找树, 都会拿红黑树作为例子, 工程中, 很多用到平衡二叉查找树的地方都会用到红黑树但凡用到动态插入, 删除, 查找数据的场景, 都可以用

傷城~/ 2022年11月01日 13:46/ 0 赞/ 177 阅读

相关红黑树学习笔记之红黑树的删除

1. 红黑树的规则 ![70][] 2. 双黑缺陷 ![70 1][] ![70 2][] 3 BB-1 ![70 3][] 通过关键码的旋转，消除超级

Bertha 。/ 2022年05月26日 06:29/ 0 赞/ 233 阅读

相关红黑树学习笔记之红黑树的结构

一. 定义规则 ![70][] 二. 实例 ![70 1][] 1. 根节点是黑色。 2. 该树已经做过一个预处理，为所有有需要的节点，都添加了一个或者两

我会带着你远行/ 2022年05月26日 06:29/ 0 赞/ 263 阅读

相关红黑树学习笔记之红黑树的插入

附加知识点： 1. 红黑树的规则 ![70][] 2.“3+4”重构 ![70 1][] 无论插入还是删除，无论是单旋还是双旋，最终效果应该都是这样一种形

朴灿烈づ我的快乐病毒、/ 2022年05月26日 06:29/ 0 赞/ 323 阅读

相关红黑树学习笔记之红黑树的动机

一. 初认红黑树 ![70][] 节点具有颜色，红色或者黑色。二. 持久性无论是线性结构：向量，列表，栈，队列半线性结构：树非线性结构：图每

雨点打透心脏的1/2处/ 2022年05月26日 06:29/ 0 赞/ 217 阅读

相关数据结构之红黑树

红黑树的由来红黑树的引入是用来解决二叉查找树在频繁的插入、删除操作的情况下，可能会出现的性能快速退化的问题。二叉查找树最坏的情况下可能退化为链表，成为 O ( n )

清疚/ 2022年04月15日 04:20/ 0 赞/ 258 阅读

相关数据结构之——红黑树

红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是red或black。通过对任何一条从根到叶子简单路径上的颜色来约束，红黑树保证最长路径不超过最短路

约定不等于承诺〃/ 2022年01月11日 02:33/ 0 赞/ 301 阅读

相关红黑树笔记

> 红黑树的五条性质： > > 1. 树中的每个结点颜色不是红的，就是黑的； > 2. 根结点的颜色是黑的； > 3. 所有为 NULL 的叶子结点的颜色是黑的； >

野性酷女/ 2022年01月07日 01:21/ 0 赞/ 256 阅读