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

朴灿烈づ我的快乐病毒、 2022-05-26 06:29 222阅读 0赞

**附加知识点：**

**1. 红黑树的规则**

![70][]

**2.“3+4”重构**

**![70 1][]**

**无论插入还是删除，无论是单旋还是双旋，最终效果应该都是这样一种形式。**

**一. 双红缺陷**

**1. 插入关键码e，并设T中文本不含e**

**2. x=insert(e)必为末端节点，设x的父亲p=x->parent存在**

**3. 将x染红（除非它是根），规则124依然满足，而3则不一定**

**4. 双红（double-red）：新插入的节点x与它的父亲p同时为红色=>双红缺陷**

**![70 2][]**

**二. RR-1**

**u->color=Black**

**1. zig-zig**

**![70 3][]**

**只需将超级节点中pg的颜色互换。**

**2. zag-zig**

![70 4][]

只需将超级节点中xg的颜色互换。

**三. RR-2**

**u->color=Red**

**![70 5][]**

**当叔父节点u为红色时，修正双红缺陷导致的红黑树拓扑结构的变化为没有变化。**

**四. 归纳**

**1. 重构，染色均属常数时间的局部操作，只需统计其总次数。**

**2.**

**![70 6][]**

**判读叔父节点的颜色，为黑色则做一次局部的3+4调整，再做常数次的染色操作。**

**为红色则略复杂，需做常数次的重染色，但可能导致在更高的节点处进而出现双红缺陷，需重新回到算法的入口。最坏的情况会多大O(logn)，但这个循环的过程，只需做重染色，不必做任何的结构调整。**

![70 7][]

**3.**

**![70 8][]**

[70]: /images/20220526/8cb75ade1c48455eac870ce9cad634d4.png
[70 1]: /images/20220526/2a1818e44181408483bfc564513e369b.png
[70 2]: /images/20220526/d74c1e383cb3404f8e87e43e6533dbb4.png
[70 3]: /images/20220526/ea35fb304ca048cfa2e818558c414fc5.png
[70 4]: /images/20220526/6ccf4dfec96d46d7ab2840c00b1d4d69.png
[70 5]: /images/20220526/79d237b4a414416a99fb9b1bbab69d9b.png
[70 6]: /images/20220526/c4ecfb43c08244a5be6ccaa11f5a74a0.png
[70 7]: /images/20220526/dd2be0a4559a43cfa54551565ceadcdc.png
[70 8]: /images/20220526/a0e7afa8000f484290773a0425546c23.png

发表评论取消回复

表情：

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

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

相关阅读

相关树：红黑树

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

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

相关红黑树的插入

一概述根据红黑树对二叉搜索树的一种平衡策略，保证当前结点比自己的父结点小（当前结点为父结点的左结点）或者保证当前结点比自己的父结点大（当前结点为父结点的右结点）。

╰半夏微凉°/ 2022年12月05日 04:55/ 0 赞/ 102 阅读

相关红黑树-插入篇

出处：http://www.cnblogs.com/sandy2013/p/3270999.html 红黑树插入操作比较复杂，特地从网上整理了一下，下面这两种解释结合起

小鱼儿/ 2022年09月28日 14:28/ 0 赞/ 152 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关红黑树

先Mark，后续补充： [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58

柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 258 阅读

相关红黑树笔记

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

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

相关红黑树

1. 从 2-3 树说起一棵标准的 BST （二叉查找树 / 二叉搜索树）是长这个样子的： BST 其中，这棵二叉查找树中的每个结点也叫 2-结点，2-结点就表示树...

系统管理员/ 2020年11月29日 04:30/ 0 赞/ 760 阅读