教你透彻了解红黑树概论

红黑树详解在本文，我将比较透彻地讲解红黑树。

本文适合那些有对二叉树有一定的基础，并且熟悉C语言的读者。

本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。

1.1 二叉查找树1.1.1 基本概念二叉查找树是在数据结构中比较重要的数据结构之一，从外部看它满足集合性质，具有查找，插入和删除的基本功能，同时还可以求最大值和最小值。

由于二叉查找树独特的性质，它特别适合用来存储动态集合。

定义：对于二叉树上的所有结点x，如果y是x的左子树，那么y.key ≤ x.key。

如果y 是x的右子树，那么y.key ≥ x.key，这样的二叉树就称为二叉查找树(Binary Search Tree)。

我们关心的二叉查找树的逻辑结构，下面的两棵二叉树：图1 二叉查找树。

(a)这一棵高度为3的二叉树，因为10比15小，所以10在15的左子树上；同理在以10为根的左子树里，7比10小所以7在左子树上，12在10为根的子树的右子树上；20在以15为根的右子树上。

(b)这是一棵高度是4的二叉查找树，它的所有key与图(a)是一样的。

在图(a)中，查找最坏的情况是7和12，它们需要经过3次比较才能找到，而图(b)最坏情况是20，需要经过4次比较才能找到。

要想二叉树的查找的花费时间小，我们尽可能让二叉树不出现类以于单链形态的二叉树，让树的高度尽量的低。

对于高度为h的二叉查找树，从树根对叶子最坏的情况是比较h 次。

也就是说，对于高度为h的二叉查找树的最坏查找情况的运行时间是O(h)。

二叉树的查找效率取决于树的高度。

1.1.2 操作二叉树做为动态集，它有查找、插入、删除、最大值、最小值、前驱和后继这些基本操作。

为了后序的方便，我们定义了结点和树，另外我们还用0表示空子树。

查找在二叉查找树中根据给定的key找到该结点。

由于二叉树的性质，我们就知道，如果目标key比当前结点的key要小，那么目标结点必定在当前结点的左子树上。

红⿊树-RBT（⼀、红⿊树定义以及简介）
⼀、红⿊树
1、介绍：红⿊树是⼀种⼆叉查找树，但在每个节点上增加⼀个存储位表⽰节点的颜⾊，可以是red或black。

通过对任何⼀条从根到叶⼦的路径上的各个节点着⾊⽅式的限制，红⿊树确保没有⼀条路径会⽐其他路径长出两倍，因⽽是接近平衡的。

2、定义：它或者是⼀颗空树，或者是具有⼀下性质的⼆叉查找树
1）：每个节点或是红的，或是⿊的。

2）：根节点是⿊的。

3）：每个叶节点（NIL）是⿊的。

（所有NULL结点称为叶⼦节点，且认为颜⾊为⿊）
4）：如果⼀个节点是红的，则他的两个⼦节点是⿊的。

5）：对每个节点，从该节点到其⼦孙节点的所有路径上包含相同数⽬的⿊节点。

3、结构：树中的每个节点上包含五个域：color、key、left、right、p。

如果其节点没有⼀个⼦节点或者⽗节点，则该节点相应的指针（p）域包含值NIL。

我们把这些NIL视为指向⼆叉查找树的外节点，⽽把带关键字的节点是为树的内节点。

4、⾼度：⼀颗有n个内节点的红⿊树的⾼⾄多为2lg(n+1)。

5、应⽤：Java集合中的和，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红⿊树去实现的。

　。

【算法】红⿊树原理和算法介绍红⿊树介绍⼆叉查找树 学红⿊树，⾸先理解⼆叉查找树 ⼆叉查找树（BST）具备特性1. 左⼦树上所有结点的值均⼩于或等于它的根结点的值。

2. 右⼦树上所有结点的值均⼤于或等于它的根结点的值。

3. 左、右⼦树也分别为⼆叉排序树。

⼆叉查找树是⼆分查找的思想，查找所需的最⼤次数等同于⼆叉树的⾼度。

在插⼊节点的时候也是利⽤类似的⽅法，⼀层⼀层⽐较⼤⼩，找到合适的插⼊位置。

如下图，这样虽然满⾜了⼆叉查找树的条件，但是这个是瘸腿的⼆叉查找树，就和链表没有区别了。

这是⼆叉查找树的缺点解决⼆叉查找树多次插⼊新节点⽽导致的不平衡的⽅法，就是使⽤红⿊树。

红⿊树是⼀种⾃平衡的⼆叉查找树。

红⿊树 R-B Tree，全称是Red-Black Tree，⼜称为“红⿊树”，它⼀种特殊的⼆叉查找树。

红⿊树的每个节点上都有存储位表⽰节点的颜⾊，可以是红(Red)或⿊(Black)。

红⿊树的特性: （1）每个节点或者是⿊⾊，或者是红⾊。

（2）根节点是⿊⾊。

（3）每个叶⼦节点（NIL）是⿊⾊。

[注意：这⾥叶⼦节点，是指为空(NIL或NULL)的叶⼦节点！] （4）如果⼀个节点是红⾊的，则它的⼦节点必须是⿊⾊的。

（5）从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点。

上⾯⼀系列的规则，保证了红⿊树的⾃平衡。

红⿊树从根到叶⼦的最长路径不会超过最短路径的2倍当插⼊或删除节点的时候，红⿊树的规则有可能被打破，这个时候需要进⾏调整来维持红⿊树的规则。

如下图，如果向原红⿊树插⼊值为21的新节点，由于⽗节点22是红⾊节点，因此这种情况打破了红⿊树的规则4（每个红⾊节点的两个⼦节点都是⿊⾊），必须进⾏调整，使之重新符合红⿊树的规则。

调整的⽅法有两种：1. 变⾊：红变⿊，⿊变红2. 旋转：左旋转和右旋转变换规则旋转和颜⾊变换规则：所有插⼊的点默认为红⾊1. 变颜⾊的情况：当前结点的⽗亲是红⾊，且它的祖⽗结点的另⼀个⼦结点也是红⾊（叔叔结点）：（1）把⽗节点设为⿊⾊（2）把叔叔也设为⿊⾊（3）把祖⽗也就是⽗亲的⽗亲设为红⾊（爷爷）（4）把指针定义到祖⽗结点设为当前要操作的（爷爷）分析的点变换的规则2. 左旋：当前⽗结点是红⾊，叔叔是⿊⾊的时候，且当前的结点是右⼦树。

红黑树面试题红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它能够保持在插入、删除等操作之后仍保持平衡。

在面试中，红黑树是常见的面试题目之一。

本文将通过解答一些常见的红黑树面试题来帮助读者更好地理解红黑树的性质和操作。

1. 什么是红黑树？红黑树是一种自平衡的二叉搜索树，它的每个节点都有一个额外的存储位来表示节点的颜色，可以是红色或黑色。

它满足以下性质：(1) 每个节点要么是红色，要么是黑色。

(2) 根节点是黑色。

(3) 每个叶子节点（NIL节点，空节点）是黑色。

(4) 如果一个节点是红色的，则它的两个子节点都是黑色的。

(5) 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

2. 如何实现红黑树的插入操作？红黑树的插入操作可以分为以下几个步骤：(1) 将节点插入到二叉搜索树中，按照二叉搜索树的规则找到合适的位置。

(2) 将插入的节点标记为红色。

(3) 根据红黑树的性质，调整树的结构来满足红黑树的要求，确保不会出现连续的红色节点。

具体的调整操作分为几种情况，我们以插入节点为A为例进行说明：(1) A是根节点，将A标记为黑色。

(2) A的父节点是黑色，不需要进行调整。

(3) A的父节点是红色：a. A的叔节点是红色：将A的父节点和叔节点都标记为黑色，将A的祖父节点标记为红色，然后以祖父节点为当前节点进行进一步的调整。

b. A的叔节点是黑色或不存在，且A是其父节点的右子节点：以A的父节点为支点进行左旋转，然后再以A的父节点为当前节点进行进一步的调整。

c. A的叔节点是黑色或不存在，且A是其父节点的左子节点：将A的父节点标记为黑色，将A的祖父节点标记为红色，以A的祖父节点为支点进行右旋转，最后整个树都符合红黑树的要求。

3. 如何实现红黑树的删除操作？红黑树的删除操作相对于插入操作要复杂一些。

删除操作可以分为以下几个步骤：(1) 根据删除节点的值，在红黑树中找到要删除的节点。

(2) 根据要删除的节点的情况进行不同的处理：a. 要删除的节点没有子节点或只有一个子节点：直接删除该节点，并将其子节点接替上来。

// 前提：这里里里假设x的右孩子子为y。下面面开始正式操作 // 将 “y的左孩子子” 设为 “x的右孩子子”，即 将β设为x的右孩子子 // 将 “x” 设为 “y的左孩子子的父父亲”，即 将β的父父亲设为x // 将 “x的父父亲” 设为 “y的父父亲”
05 if p[x] = nil[T] 06 then root[T] ← y
的右孩子子”
10 left[y] ← x
// 将 “x” 设为 “y的左孩子子”
11 p[x] ← y
// 将 “x的父父节点” 设为 “y”
理理解左旋之后，看看下面面更更鲜明的例例子子。
2.2 右旋
对Y进行行行右旋，意味着“将Y变成一一个右节点”
右旋的伪代码《算法导论》：参考上面面的示意图和下面面的伪代码，理理解“红黑黑树T的节点y进行行行右 旋”是如何进行行行的。
1.2 红广泛，主要是用用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非非常之
高高。
例例如，Java集合中的TreeSet和TreeMap，C++的STL中的Set、Map，以及Linux虚拟内存的管
理理，都是通过红黑黑树去实现的。
二二、红黑黑树的基本操作：左旋和右旋
数据结构与算法（8）：红黑黑树
红黑黑树，即R-B Tree，本文文的主要内容包括：红黑黑树的特性、红黑黑树的时间复杂度和它的证明， 红黑黑树的时间复杂度和它的证明，红黑黑树的左旋、右旋、插入入、删除等操作
一一、红黑黑树的定义
1.1 红黑黑树的定义
R-B Tree，全称是Red-black Tree，又又称为“红黑黑树”，它是一一种特殊的二二叉查找树。红黑黑树的每 个节点上都有存储位表示节点的颜色色，可以是红（Red）或黑黑（Black）

红黑树简介1. 简介红黑树是一种自平衡二叉查找树。

它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。

在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。

它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除等操作。

本文介绍了红黑树的基本性质和基本操作。

2. 红黑树的性质红黑树，顾名思义，通过红黑两种颜色域保证树的高度近似平衡。

它的每个节点是一个五元组：color（颜色），key（数据），left（左孩子），right（右孩子）和p（父节点）。

红黑树的定义也是它的性质，有以下五条：性质1. 节点是红色或黑色性质2. 根是黑色性质3. 所有叶子都是黑色（叶子是NIL节点）性质4. 如果一个节点是红的，则它的两个儿子都是黑的性质5. 从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。

这五个性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

为什么呢？性质4暗示着任何一个简单路径上不能有两个毗连的红色节点，这样，最短的可能路径全是黑色节点，最长的可能路径有交替的红色和黑色节点。

同时根据性质5知道：所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

3. 红黑树的基本操作因为红黑树也是二叉查找树，因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。

然而，红黑树上的插入操作和删除操作会导致不再符合红黑树的性质。

恢复红黑树的性质需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。

虽然插入和删除很复杂，但操作时间仍可以保持为O(log n) 次。

3.1 插入操作插入操作可以概括为以下几个步骤：(1) 查找要插入的位置，时间复杂度为：O(N)(2) 将新节点的color赋为红色(3) 自下而上重新调整该树为红黑树其中，第(1)步的查找方法跟普通二叉查找树一样，第(2)步之所以将新插入的节点的颜色赋为红色，是因为：如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。

红黑树的删除
删除节点后对RBT性质的影响讨论：
若删除结点为红色，则对RBT性质没有影响，原因？ • 树中各结点的黑高没有变化 • 不存在两个相邻的红色结点 • 因为删除结点为红色，就不可能是根，所以根仍然 为黑
若删除结点为黑色，则对RBT性质会产生影响，因此 需要调整
红黑树的删除
删除的调整算法 讨论
红黑树
目录
§.1 红黑树的定义
§.2 红黑树的性质
§.3 红黑树的旋转
§.4 红黑树的插入
§.5 红黑树的删除
红黑树的插入
step 1：将z节点按二叉查找树规则插入红 黑树中，z是叶子节点； step 2：将z涂红； step 3：调整使其满足红黑树的性质；
红黑树的插入
插入算法示例
• RBInsert(T, z) { y ← nil[T]; x ← root[T]; while x ≠ nil[T] do { y ← x; if key[z] ＜ key[x] then x ← left[x]; else x ← right[x]; } p[z] ← y; if y = nil[T] then
红黑树的删除
Case1：z为叶结点 Case2：z只有一个孩子
处理方法：删除z，连接x。这里x是z的中序后继
注： • case 1是case 2的特例，因为处理模式是一样的 • z是p[z]的左孩子，类似讨论
红黑树的删除
Case3：z两个孩子均非空 实际删除的结点为y！
处理方法： (1)找z的中序后继，即找z的右子树中最左下节点y (2)删除y，将y的内容copy到z，再将y的右子连到 p[y]左下。
root[T] ← z;
//y用于记录当前扫描节点的双亲节点 //从根开始扫描 //查找插入位置 //z插入x的左边

数据结构与算法中的红黑树数据结构是计算机程序设计中的重要组成部分，用于存储和组织数据。

在计算机科学中，算法是解决问题的基础。

红黑树是一种常用的数据结构和算法，被广泛应用于计算机的操作系统、数据库、编译器、图形图像等领域。

本文将对红黑树的定义、实现、应用等方面进行详细介绍。

一、红黑树的定义红黑树是一种自平衡二叉查找树，它满足以下性质：1.每个节点要么是红色，要么是黑色。

2.根节点是黑色的。

3.每个叶节点（NIL节点，空节点）是黑色的。

4.如果一个节点是红色的，则它的两个子节点都是黑色的。

5.对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

这意味着红黑树是一种平衡二叉查找树，它通过不断的旋转和节点着色来使树保持平衡。

二、红黑树的实现红黑树的实现有两个关键步骤：插入和删除。

①插入操作插入新节点时，首先按照二叉查找树的原则将它放入合适的位置，然后将它的颜色设置为红色。

如果新插入的节点是根节点，则直接将其颜色改为黑色；如果其父节点是黑色的，则不影响红黑树的性质，直接结束操作即可。

如果其父节点是红色的，则需要进行颜色调整。

具体来说，需要根据其祖父节点的颜色和叔父节点的颜色进行分类讨论：1.祖父节点为黑色，则不需要调整。

2.叔父节点是红色，则将父节点和叔父节点颜色都设置为黑色，将祖父节点颜色设置为红色，然后将当前节点指向祖父节点，重新开始操作。

3.叔父节点是黑色或为空，则需要旋转和着色，使得当前节点变成祖父节点，父节点变成红色，原来的祖父节点变成黑色。

此时，如果当前节点已经变成了根节点，则将其颜色设置为黑色，结束操作；否则，继续考虑其父节点的颜色和祖父节点的颜色，重复以上步骤。

②删除操作删除节点时，首先按照二叉查找树的原则找到它，然后根据其子节点的情况进行讨论。

如果删除的节点是叶子节点（没有子节点），直接将其删除即可。

如果删除的节点只有一个子节点，则将其子节点替换为该节点即可。

什么是红黑树？面试必问！优质文章，第一时间送达当在10亿数据中只需要进行10几次比较就能查找到目标时，不禁感叹编程之魅力！人类之伟大呀！——学红黑树有感。

终于，在学习了几天的红黑树相关的知识后，我想把我所学所想和所感分享给大家。

红黑树是一种比较难的数据结构，要完全搞懂非常耗时耗力，红黑树怎么自平衡？什么时候需要左旋或右旋？插入和删除破坏了树的平衡后怎么处理？等等一连串的问题在学习前困扰着我。

如果你在学习过程中也会存在我的疑问，那么本文对你会有帮助，本文帮助你全面、彻底地理解红黑树，面试官放马过来！本文将通过图文的方式讲解红黑树的知识点，并且不会涉及到任何代码，相信我，在懂得红黑树实现原理前，看代码会一头雾水的，当原理懂了，代码也就按部就班写而已，没任何难度。

阅读本文你需具备知识点：•二叉查找树•完美平衡二叉树关于红黑树的知识面试经常问，本文作者是安卓大叔，欢迎点击阅读原文关注作者的简书。

事不宜迟，让我们进入正题吧。

正文红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

现在在脑海想下怎么实现？是不是太多情景需要考虑了？啧啧，先别急，通过本文的学习后，你会觉得，其实也不过如此而已。

好吧，我们先来看下红黑树的定义和一些基本性质。

红黑树定义和性质红黑树是一种含有红黑结点并能自平衡的二叉查找树。

它必须满足下面性质：•性质1：每个节点要么是黑色，要么是红色。

•性质2：根节点是黑色。

•性质3：每个叶子节点（NIL）是黑色。

•性质4：每个红色结点的两个子结点一定都是黑色。

•性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

从性质5又可以推出：•性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点图1就是一颗简单的红黑树。

其中Nil为叶子结点，并且它是黑色的。

红黑树实现原理及应用技巧介绍红黑树作为一种自平衡的二叉查找树，具有高效的插入、删除和搜索操作。

它的实现原理以及应用技巧在算法和数据结构领域中具有重要的意义。

本文将介绍红黑树的实现原理，同时探讨一些应用中的技巧和注意事项。

一、红黑树的基本概念红黑树是一种二叉查找树，在普通的二叉查找树基础上增加了一组额外的规则，使得树保持平衡。

红黑树具有以下特点：1. 每个节点要么是红色，要么是黑色。

2. 根节点是黑色的。

3. 如果一个节点是红色的，则它的子节点必须是黑色的。

4. 从根节点到叶子节点或者空子节点的每条路径，必须包含相同数目的黑色节点。

5. 空子节点被视为黑色。

二、红黑树的实现原理红黑树的实现原理主要包括节点的插入、删除和搜索操作。

1. 插入操作在红黑树中插入一个节点时，首先按照二叉查找树的规则找到插入位置，将节点插入为叶子节点，并将其颜色设置为红色。

接下来，根据红黑树的规则进行调整，确保树仍然满足平衡性：- 如果插入节点的父节点是黑色，树保持平衡，插入操作完成。

- 如果插入节点的父节点是红色，需要进行颜色和结构的调整。

具体调整方式包括：- 如果插入节点的叔节点（父节点的兄弟节点）是红色，将父节点和叔节点的颜色改为黑色，祖父节点的颜色改为红色，然后将祖父节点设置为当前节点，重新进行调整；如果插入节点没有叔节点，或者叔节点是黑色，进行下一步操作。

- 如果插入节点的父节点是祖父节点的左子节点，插入节点是父节点的左子节点，进行右旋操作；如果插入节点是父节点的右子节点，先进行左旋操作，然后再进行右旋操作。

- 如果插入节点的父节点是祖父节点的右子节点，插入节点是父节点的右子节点，进行左旋操作；如果插入节点是父节点的左子节点，先进行右旋操作，然后再进行左旋操作。

最终，将根节点设为黑色，保证红黑树始终满足规则。

2. 删除操作在红黑树中删除一个节点时，也需要进行相应的调整，以保持树的平衡。

删除操作分为两种情况：被删除节点有零个或一个子节点，以及被删除节点有两个子节点。

还没吃透面试必问的红黑树？图文并茂的让你彻底理解红黑树11. 红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

2. 红黑树的性质2.1. 每个结点不是红色就是黑色2.2. 根节点是黑色的2.3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（不会出现连在一起的红色节点）2.4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（在计算一条路径中黑色节点个数的时候要带上叶子节点，因为叶子节点也是黑色的，也就是空节点）。

2.5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)（为了保证空树也是红黑树）2.6.红黑树确保没有一条路径会比其他路径长出俩倍（红黑树前面的性质保证了当前的性质）3. 红黑树的实现3.1. 带头节点的红黑树这里我们将红黑树的实现给为带头的红黑树，因为红黑树是map 和set的底层数据结构这里我们实现出来红黑树就可以直接用当前我们实现的带头红黑树来实现map和set至于头节点的给出是为了方便于map和set的遍历，在STL中我们区间给出都是左闭右开区间的，既然红黑树作为map和set的底层数据结构那么我们就一定有位置要来放map和set的迭代器，那么就可以将begin位置的迭代器放在head 的左，end位置的迭代器可以放在head位置。

这里我们将红黑树头节点的颜色给为红色。

3.2. 红黑树的节点3.3. 红黑树插入节点的分析（实现红黑树最最最关键的一步）可以看到我们上面在红黑树节点的构造的时候将节点的默认颜色给为红色，那么我们在插入节点的时候就要特别考虑性质3：不可以有两个红色节点连在一起。

这里我们可以一共可以分为两大类，一类将节点插入当前红黑树的左子树中，另一类就是将节点插入红黑树的右子树当中。

红黑树算法原理与实现红黑树是一种自平衡二叉查找树，它能够保证查找、插入和删除操作最坏情况下的时间复杂度都为O(log n)，是一种十分高效的数据结构。

本文将对红黑树算法的原理和实现进行介绍，帮助读者深入了解红黑树的运作流程和应用场景。

一、红黑树的定义和性质红黑树和其他的自平衡二叉查找树（如AVL树）一样，能够自动调整树的结构以保证平衡，并且能够保持树中每个节点的黑高相等。

下面是红黑树的具体定义：（1）每个节点要么是红色，要么是黑色。

（2）根节点是黑色。

（3）每个叶子节点（NIL节点，空节点）都是黑色的。

（4）如果一个节点是红色的，则它的子节点必须是黑色的。

（5）任意一个节点到每个叶子节点所经过的黑色节点数都相同。

这些性质确保了红黑树的平衡，在插入和删除节点时能够自动平衡而不需要人工干预，从而保证了树的性能。

二、红黑树的基本操作红黑树的插入和删除操作是它最为关键和难点的部分，下面我们将针对这两个操作进行介绍。

（1）插入操作插入节点时，首先按照二叉查找树的方式将新节点插入到树中。

接下来需要进行的操作是将节点的颜色进行调整，保证该节点符合红黑树的五大性质。

如果插入的节点不满足性质（4），需要执行进行一系列颜色调整和旋转操作，使得节点重新满足红黑树性质。

一般情况下，情况分为两种：（a）情况1：插入的节点为根节点此时只需要将节点的颜色设置为黑色即可。

（b）情况2：插入的节点的父节点为红色此时需要进行一系列的旋转和颜色调整操作。

可以分为以下三种情况：①插入节点的叔叔节点是红色的，此时需要进行颜色调整和旋转。

②插入节点的叔叔节点是黑色的，并且插入节点为父节点的右子节点，此时需要进行左旋操作。

③插入节点的叔叔节点是黑色的，并且插入节点为父节点的左子节点，此时需要进行颜色调整、右旋操作。

（2）删除操作删除节点时，首先按照二叉查找树的方式删除节点。

接着需要对树进行自平衡操作，使之重新满足红黑树性质。

与插入操作相比，删除操作需要考虑更多的情况。

红⿊树概述和原理
红⿊树概述
红⿊树和我们以前学过的AVL树类似，都是在进⾏插⼊和删除操作时通过特定操作保持⼆叉查找树的平衡，从⽽获得较⾼的查找性能。

不过⾃从红⿊树出来后，AVL树就被放到了博物馆⾥，据说是红⿊树有更好的效率，更⾼的统计性能。

这⼀点在我们了解了红⿊树的实现原理后，就会有更加深切的体会。

红⿊树和AVL树的区别在于它使⽤颜⾊来标识结点的⾼度，它所追求的是局部平衡⽽不是AVL树中的⾮常严格的平衡。

学过数据结构的⼈应该都已经领教过AVL树的复杂，但AVL树的复杂⽐起红⿊树来说简直是⼩巫见⼤巫，红⿊树才是真正的变态级数据结构。

由于STL中的关联式容器默认的底层实现都是红⿊树，因此红⿊树对于后续学习STL源码还是很重要的，有必要掌握红⿊树的实现原理和源码实现。

红⿊树是AVL树的变种，红⿊树通过⼀些着⾊法则确保没有⼀条路径会⽐其它路径长出两倍，因⽽达到接近平衡的⽬的。

所谓红⿊树，不仅是⼀个⼆叉搜索树，⽽且必须满⾜⼀下规则：
1、每个节点不是红⾊就是⿊⾊。

2、根节点为⿊⾊。

3、如果节点为红⾊，其⼦节点必须为⿊⾊。

4、任意⼀个节点到到NULL（树尾端）的任何路径，所含之⿊⾊节点数必须相同。

红⿊树（R-BTree）R-B Tree简介R-B Tree，全称是Red-Black Tree，⼜称为“红⿊树”，它⼀种特殊的⼆叉查找树。

红⿊树的每个节点上都有存储位表⽰节点的颜⾊，可以是红(Red)或⿊(Black)。

红⿊树的特性:（1）每个节点或者是⿊⾊，或者是红⾊。

（2）根节点是⿊⾊。

（3）每个叶⼦节点（NIL）是⿊⾊。

[注意：这⾥叶⼦节点，是指为空(NIL或NULL)的叶⼦节点！]（4）如果⼀个节点是红⾊的，则它的⼦节点必须是⿊⾊的。

（5）从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点。

注意：(01) 特性(3)中的叶⼦节点，是只为空(NIL或null)的节点。

(02) 特性(5)，确保没有⼀条路径会⽐其他路径长出俩倍。

因⽽，红⿊树是相对是接近平衡的⼆叉树。

红⿊树⽰意图如下：红⿊树的应⽤红⿊树的应⽤⽐较⼴泛，主要是⽤它来存储有序的数据，它的时间复杂度是O(lgn)，效率⾮常之⾼。

例如，Java集合中的和，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红⿊树去实现的。

红⿊树的时间复杂度和相关证明红⿊树的时间复杂度为: O(lgn)下⾯通过“数学归纳法”对红⿊树的时间复杂度进⾏证明。

定理：⼀棵含有n个节点的红⿊树的⾼度⾄多为2log(n+1).证明："⼀棵含有n个节点的红⿊树的⾼度⾄多为2log(n+1)" 的逆否命题是 "⾼度为h的红⿊树，它的包含的内节点个数⾄少为 2h/2-1个"。

我们只需要证明逆否命题，即可证明原命题为真；即只需证明"⾼度为h的红⿊树，它的包含的内节点个数⾄少为 2h/2-1个"。

从某个节点x出发（不包括该节点）到达⼀个叶节点的任意⼀条路径上，⿊⾊节点的个数称为该节点的⿊⾼度(x's black height)，记为bh(x)。

关于bh(x)有两点需要说明：第1点：根据红⿊树的"特性(5) ，即从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点"可知，从节点x出发到达的所有的叶节点具有相同数⽬的⿊节点。

前言：之所以要写这篇文章，第一个目的是为了各位朋友在查看我写的源代码之前有一个可以理解理论的文章因为红黑树还是有点难的，如果不想搞懂理论，而直接看代码，那绝对是云里雾里，不知所云。

第二个目的是我觉得网上虽然后不少我文章也在讲，但是我就是理解不上有点困难，在我参考了很多文章之后，认真阅读才慢慢摸透了其中的原理，所以我想用自己的方式来表达，希望有助于各位的朋友理解。

你可以在这里获得配套源代码红黑树由来：他是在1972年由Rudolf Bayer发明的，他称之为“对称二叉B树”，它现代的名字是Leo J. Guibas和 Robert Sedgewick 于1978年写的一篇论文中获得的。

它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

红黑树性质：1. 每个结点或红或黑。

2. 根结点为黑色。

3. 每个叶结点(实际上就是NULL指针)都是黑色的。

4. 如果一个结点是红色的,那么它的周边3个节点都是黑色的。

5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。

讨论的前提：1，我们只讨论往树的左边和从树的左边删除的情况，与之对称的情况一样。

2，假设我们要删除一个元素的方法都是采取删除后继节点，而非前驱节点。

3，NL或全黑表示黑空节点，也可以不用画出。

4，“=>”这个符号我们用来表示“变成”的意思。

一．插入当红黑树中没有节点的时候，新节点直接涂黑就可以了。

当树中已有节点，我们就将新节点涂红，并且底下挂两个黑空节点。

1.1 新节点的父亲为黑色这种情况最简单，只接插入将新节点可以了，不会出现红色警戒。

1.2 新节点的父亲为红色这种情况出现红色警戒，并且通过红色的父亲，我们可以推出一定有一个黑色的父，并且父亲不可能为树根(树根必须为黑)。

这种情况需要修复。

1.2.1 新节点的叔叔是红色。

红⿊树详解前⾔红⿊树的起源，⾃然是⼆叉查找树了，这种树结构从根节点开始，左⼦节点⼩于它，右⼦节点⼤于它。

每个节点都符合这个特性，所以易于查找，是⼀种很好的数据结构。

但是它有⼀个问题，就是容易偏向某⼀侧，这样就像⼀个链表结构了，失去了树结构的优点，查找时间会变坏。

所以我们都希望树结构都是矮矮胖胖的，像这样：⽽不是像这样：在这种需求下，平衡树（AVL）的概念就应运⽽⽣了。

红⿊树就是⼀种平衡树，它可以保证⼆叉树基本符合矮矮胖胖的结构，但是理解红⿊树之前，必须先了解另⼀种树，叫2-3树，红⿊树背后的逻辑就是它。

好吧来看2-3树吧。

2-3树是⼆叉查找树的变种，树中的2和3代表两种节点，以下表⽰为2-节点和3-节点。

2-节点即普通节点：包含⼀个元素，两条⼦链接。

3-节点则是扩充版，包含2个元素和三条链接：两个元素A、B，左边的链接指向⼩于A的节点，中间的链接指向介于A、B值之间的节点，右边的链接指向⼤于B的节点 2-节点： 3-节点：在这两种节点的配合下，2-3树可以保证在插⼊值过程中，任意叶⼦节点到根节点的距离都是相同的。

完全实现了矮胖矮胖的⽬标。

怎么配合的呢，下⾯来看2-3树的构造过程。

所谓构造，就是从零开始⼀个节点⼀个节点的插⼊。

在⼆叉查找树中，插⼊过程从根节点开始⽐较，⼩于节点值往右继续与左⼦节点⽐，⼤于则继续与右⼦节点⽐，直到某节点左或右⼦节点为空，把值插⼊进去。

这样⽆法避免偏向问题。

在2-3树中，插⼊的过程是这样的。

如果将值插⼊⼀个2-节点，则将2-节点扩充为⼀个3-节点。

如果将值插⼊⼀个3-节点，分为以下⼏种情况。

(1).3-节点没有⽗节点，即整棵树就只有它⼀个三节点。

此时，将3-节点扩充为⼀个4-节点，即包含三个元素的节点，然后将其分解，变成⼀棵⼆叉树。

此时⼆叉树依然保持平衡。

(2).3-节点有⼀个2-节点的⽗节点，此时的操作是，3-节点扩充为4-节点，然后分解4-节点，然后将分解后的新树的⽗节点融⼊到2-节点的⽗节点中去。

红黑树定义与特点红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它在每个节点上增加一个表示节点颜色的额外属性，可以是红色或黑色。

红黑树以其高效的插入、删除和查找操作而闻名，被广泛应用于数据结构和算法中。

一、红黑树的定义红黑树要求满足以下五个性质：1. 每个节点要么是黑色，要么是红色。

2. 根节点是黑色。

3. 每个叶节点（NIL节点，空节点）是黑色。

4. 如果一个节点是红色的，则其两个子节点都是黑色的。

5. 任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

二、红黑树的特点1. 黑平衡：红黑树是一种黑平衡（Black-Balanced）的二叉查找树，即从根节点到任意叶子节点的路径上，黑色节点的数量相同。

这个特点保证了红黑树的最长路径不会超过最短路径的两倍，使得红黑树保持了较好的平衡性。

2. 高效的查找、插入和删除操作：红黑树的查找操作与普通二叉查找树相同，时间复杂度为O(log n)。

红黑树的插入和删除操作相对复杂一些，但仍然能够在O(log n)的时间内完成。

由于红黑树的自平衡特性，插入和删除操作后只需要进行一些局部的变色和旋转操作就能保证红黑树的性质不变。

3. 应用广泛：红黑树在计算机科学中有着广泛的应用。

例如，C++ STL中的set和map容器通常使用红黑树实现，因为红黑树能够保持有序性并且具有较高的查找效率。

此外，数据库中的索引结构、操作系统中的进程调度、网络路由等众多领域都使用了红黑树。

4. 自平衡机制：红黑树通过一系列的自平衡操作来保持树的平衡，其中最关键的操作是颜色变换和旋转。

颜色变换可以改变节点的颜色，而旋转可以改变节点之间的相对位置。

通过合理的颜色变换和旋转操作，红黑树可以在插入和删除节点时保持平衡，避免树的高度过高或过低，保证了树的查找效率。

5. 插入和删除的情况分类处理：红黑树的插入和删除操作需要考虑多种不同的情况，根据节点的颜色、兄弟节点的颜色以及父节点的颜色等进行分类处理。