红黑树详解

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

本文适合那些有对二叉树有一定的基础，并且熟悉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要小，那么目标结点必定在当前结点的左子树上。

c++map的底层实现原理
C++ STL中的map是通过红黑树实现的，红黑树是一种自平衡的二叉查找树，它的插入、删除、查找操作都能在对数时间复杂度内完成，可以保证较稳定的性能。

具体来说，map内部是用一颗红黑树（Red-Black Tree）实现的。

红黑树是一种对平衡性要求比较低的二叉查找树（Binary Search Tree），在红黑树上进行查找、插入、删除等操作的时间复杂度都是log(N)。

红黑树的特点是每个节点要么是红色，要么是黑色，并且满足以下规则：
1、根节点是黑色的；
2、每个叶子节点都是黑色的空节点（NIL节点）；
3、如果一个节点是红色的，则它的子节点必须是黑色的；
4、从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点；
由于map底层采用红黑树实现，因此它具有以下特点：
1、自动排序；
2、查找、插入、删除操作的时间复杂度都是O(logN)，极端情况下会退化成链表；
3、可以支持迭代器操作，比如反向迭代；
4、支持按照自定义规则排序；
综上所述，map的底层实现原理是通过红黑树实现的，红黑树是一种自平衡的二叉查找树，能够保证较稳定的性能。

红黑树面试题红黑树（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. 要删除的节点没有子节点或只有一个子节点：直接删除该节点，并将其子节点接替上来。

红黑树的特点范文红黑树是一种自平衡的二叉树，它具有以下特点：1.二叉树属性：红黑树满足二叉树的基本性质，即对于树中的每个节点，其左子树的所有节点的值都小于该节点的值，而右子树的所有节点的值都大于该节点的值。

2.红黑性质1：每个节点要么是红色，要么是黑色。

3.红黑性质2：根节点是黑色的。

4.红黑性质3：每个叶子节点（NIL节点，空节点）是黑色的。

5.红黑性质4：如果一个节点是红色的，那么它的两个子节点都是黑色的。

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

7.黑高度相等：从根节点到任意叶子节点的路径上的黑色节点数量必须相同，这个数量成为黑高度。

红黑树之所以被称为“红黑树”，是因为它的节点可以被标记为红色或黑色，并且通过这些颜色的约束规则实现了平衡性。

1. 自平衡性：通过红黑性质的约束规则，红黑树能够自动平衡，保持树的高度相对较低，从而能够提供较快的、插入和删除操作的平均时间复杂度为O(log n)，保证了树的高效性能。

2.结构简单：红黑树的基本特点较为简单，只有5个约束规则，相较于AVL树等平衡二叉树，实现和维护的复杂度较低。

3.有序性：红黑树是一个有序树，即树中的节点按照特定的顺序排列。

这使得红黑树非常适用于需要有序数据的场景，例如字典、索引等。

4. 广泛应用：红黑树被广泛应用于各种数据结构和算法中，如集合、映射、区间树、数据库索引等。

在C++的STL库中，map和set容器的实现就是基于红黑树。

红黑树的缺点：1.相对复杂：相较于其他二叉树，红黑树的实现和维护较为复杂，因为需要遵循红黑性质。

这增加了代码的复杂度和难度。

2. 插入和删除操作相对慢：虽然红黑树的平均情况下插入和删除的时间复杂度为O(log n)，但相较于普通二叉树，红黑树在实际性能上略慢一些。

总结：红黑树是一种自平衡的二叉树，通过红黑性质的约束规则，保持树的平衡性和有序性。

它具有较高的查询、插入和删除效率，并且广泛应用于各种数据结构和算法中。

红黑树优点和应用场景红黑树优点及应用场景红黑树是一种自平衡二叉查找树，具有优秀的平均性能和较稳定的最坏情况性能。

它的优点包括高效的查找、插入和删除操作，以及平衡性能好，不易退化成链表等。

本文将详细介绍红黑树的优点及其应用场景。

一、红黑树优点1.高效的查找、插入和删除操作红黑树的查找、插入和删除操作时间复杂度均为O(log n)，其中n 为树中节点数。

由于红黑树的平衡性，它的查找性能非常高，并且插入和删除操作也能够保持比较稳定的性能。

这使得红黑树在实际应用中非常受欢迎。

2.平衡性能好，不易退化成链表红黑树是一种自平衡二叉查找树，它通过保持节点的颜色、旋转等方式来保持树的平衡性。

这使得红黑树不易退化成链表，从而保证了它的查找、插入和删除操作的时间复杂度稳定。

3.易于实现和理解红黑树的实现相对简单，且易于理解。

它的平衡性质也使得它的实现相对稳定，不易出现错误。

这使得红黑树在实际应用中非常受欢迎，尤其是对于那些需要高效查找、插入和删除操作的应用场景。

二、红黑树应用场景1.数据库索引数据库索引是一种常见的应用场景，它通过建立一棵树来实现对数据的快速查找。

在这种情况下，红黑树是一种非常合适的数据结构，因为它能够提供高效的查找、插入和删除操作，并且能够保持较好的平衡性。

2.操作系统调度操作系统调度是一种需要高效查找和插入操作的应用场景。

在这种情况下，红黑树可以用来实现进程优先级的管理，从而保证高优先级进程的优先执行。

3.路由表路由表是一种需要高效查找和插入操作的应用场景。

在这种情况下，红黑树可以用来实现路由表的管理，从而保证路由的高效查找和更新操作。

4.编译器实现编译器是一种需要高效查找和插入操作的应用场景。

在这种情况下，红黑树可以用来实现符号表的管理，从而保证编译器的高效性能。

红黑树是一种非常优秀的数据结构，它具有高效的查找、插入和删除操作，以及平衡性能好，不易退化成链表等优点。

它在数据库索引、操作系统调度、路由表和编译器实现等应用场景中都有广泛的应用。

红黑树的定义和节点结构红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。

红黑树具有如下性质：1. 每个节点要么是红色，要么是黑色。

2. 根节点是黑色。

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

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

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

红黑树的节点结构通常包含以下几个字段：1. 键值（Key）：存储节点的关键字，用于进行搜索和比较。

2. 数据（Value）：存储节点关联的数据。

3. 左子节点（Left）：指向该节点的左子节点。

4. 右子节点（Right）：指向该节点的右子节点。

5. 父节点（Parent）：指向该节点的父节点。

6. 颜色（Color）：表示节点的颜色，通常用布尔值或枚举类型表示。

红黑树的定义和节点结构相互依赖，通过节点间的关系和颜色属性，实现了树的自平衡。

下面将详细介绍红黑树的定义和节点结构。

红黑树的定义是基于二叉搜索树的基础上进行的。

二叉搜索树是一种有序的二叉树，对于任意节点，其左子节点的键值小于该节点的键值，而右子节点的键值大于该节点的键值。

这个性质使得在二叉搜索树上进行搜索、插入和删除等操作非常高效。

然而，如果只使用二叉搜索树，可能会出现树的不平衡情况，导致某些操作的时间复杂度变高。

为了解决这个问题，红黑树引入了节点的颜色属性，并通过一些特定的规则来保持树的平衡。

红黑树的节点结构包含了键值、数据和指向子节点的指针。

其中，键值用于进行搜索和比较，数据存储了节点关联的信息。

左子节点和右子节点分别指向该节点的左右子树，父节点指向该节点的父节点。

通过这些指针，可以在树中进行节点的插入、删除和查找等操作。

红黑树的节点还包含了颜色属性，用于表示节点的颜色。

颜色通常用布尔值或枚举类型表示，红色用true或RED表示，黑色用false 或BLACK表示。

⾯试题——轻松搞定⾯试中的红⿊树问题版权所有，转载请注明出处，谢谢！连续两次⾯试都问到了红⿊树，关键两次都没有答好，这次就完整地来学习整理⼀下。

没有学习过红⿊树的同学请参考：<<Introduction to Algorithms>> Chapter 13 Red-Black Trees Chapter 14 Augmenting Data Structures1.stl中的set底层⽤的什么数据结构？2.红⿊树的数据结构怎么定义的？3.红⿊树有哪些性质？4.红⿊树的各种操作的时间复杂度是多少？5.红⿊树相⽐于BST和AVL树有什么优点？6.红⿊树相对于哈希表，在选择使⽤的时候有什么依据？7.如何扩展红⿊树来获得⽐某个结点⼩的元素有多少个？8.扩展数据结构有什么步骤？9 为什么⼀般hashtable的桶数会取⼀个素数详细解答1.stl中的set底层⽤的什么数据结构？红⿊树2.红⿊树的数据结构怎么定义？[cpp]1. enum Color2. {3. RED = 0,4. BLACK = 15. };6.7. struct RBTreeNode8. {9. struct RBTreeNode*left, *right, *parent;10. int key;11. int data;12. Color color;13. };3.红⿊树有哪些性质？⼀般的，红⿊树，满⾜以下性质，即只有满⾜以下全部性质的树，我们才称之为红⿊树：1）每个结点要么是红的，要么是⿊的。

2）根结点是⿊的。

3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是⿊的。

4）如果⼀个结点是红的，那么它的俩个⼉⼦都是⿊的。

5）对于任⼀结点⽽⾔，其到叶结点树尾端NIL指针的每⼀条路径都包含相同数⽬的⿊结点。

4.红⿊树的各种操作的时间复杂度是多少？能保证在最坏情况下，基本的动态⼏何操作的时间均为O（lgn）5.红⿊树相⽐于BST和AVL树有什么优点？红⿊树是牺牲了严格的⾼度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从⽽提⾼了性能。

treeset排序原理
TreeSet是一种基于红黑树的Set集合，它可以自动进行元素排序。

TreeSet的排序原理是通过对元素进行比较，将它们按照特定的顺序排列。

在创建TreeSet时，可以传入一个Comparator对象，它可以定义元素的比较规则。

如果没有传入Comparator，则元素必须实现Comparable接口，该接口中定义了一个compareTo()方法，该方法用于定义元素的自然顺序。

TreeSet使用红黑树的数据结构来存储元素。

红黑树是一种自平衡的二叉搜索树，它具有以下特点：
1. 每个节点都是红色或黑色。

2. 根节点是黑色的。

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

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

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

由于红黑树是自平衡的，因此在插入和删除元素时，它会自动调整树的结构，以保持树的平衡。

这样可以确保元素的插入和删除操作的时间复杂度都是O(log n)，其中n为树中元素的个数。

另外，由于TreeSet是一个Set集合，因此它不允许包含重复的元素。

如果试图将重复元素插入TreeSet中，它会被忽略。

总之，通过使用红黑树作为数据结构和元素比较规则，TreeSet
可以自动对元素进行排序，并且具有高效的插入和删除操作。

hashmap红黑树退化条件
hashmap的实现中，使用了红黑树来优化hash冲突引起的链表退化问题，但红黑树也有可能会退化，那么什么条件下红黑树会发生退化呢？
1. 大量重复的key：当hashmap中存在大量重复的key时，会导致红黑树退化成链表。

因为红黑树的时间复杂度是O(logn)，而链表的时间复杂度是O(n)，所以红黑树退化成链表后，性能会大幅下降。

2. key的hashCode相同：hashmap使用hashCode来计算key在数组中的位置，如果存储的key的hashCode相同，会导致红黑树的插入、查找等操作退化成链表操作。

因为此时，红黑树的左右子树都为空，相当于链表。

3. 扩容导致的rehash：当hashmap扩容时，会导致所有的key 重新计算hash值，如果新的hash值相同，会导致红黑树退化成链表。

因此，为了避免这种情况，可以使用自定义的hashCode方法，使得每个key的hashCode都不相同，从而避免rehash引起的退化。

总之，红黑树退化成链表是一种很严重的问题，会影响hashmap 的性能。

因此，在实际开发中，需要注意避免上述情况的发生。

- 1 -。

红黑树的时间复杂度红黑树（Red-Black Tree）是一种自平衡的二叉查找树，通过保持树的黑高（从根节点到任意叶节点的黑色节点个数）相等，来确保树的高度始终保持在O(log n)的级别。

红黑树的时间复杂度在插入、删除和查找操作中都能够保持较好的性能。

一、插入操作在红黑树中插入节点的过程中，我们需要涉及到一些调整，以保持树的平衡。

这主要包括旋转操作和颜色调整。

1.1 旋转操作旋转操作是红黑树中的核心操作之一，用于维持树的平衡。

在插入节点时，如果出现了某些情况，比如连续的红色节点或者违反了树的性质，就需要进行旋转操作。

左旋操作和右旋操作分别通过改变节点指针的指向来实现。

左旋操作将一个节点的右子节点提升为其父节点，同时原来的父节点成为新的左子节点。

右旋操作则是左旋操作的镜像操作。

1.2 颜色调整在插入节点后，可能会违反红黑树性质的第三条和第四条。

第三条要求红黑树的每个红色节点的两个子节点都是黑色，而第四条则要求从任意节点到其每个叶子的路径上包含相同数目的黑色节点。

为了恢复平衡，我们会进行一系列的颜色调整操作。

这包括变换节点颜色、变换父子节点的颜色以及进行旋转操作。

综上，红黑树的插入操作的时间复杂度为O(log n)。

二、删除操作红黑树的删除操作相对于插入操作稍微复杂一些。

同样也需要进行旋转操作和颜色调整。

2.1 旋转操作删除节点后，为了保持树的平衡，我们可能需要进行多次旋转操作，使树保持平衡。

2.2 颜色调整删除节点后可能会导致红黑树的性质被破坏，我们需要进行颜色调整以恢复性质。

删除操作的时间复杂度也是O(log n)。

三、查找操作红黑树的查找操作与二叉查找树相同，通过比较节点的值进行搜索。

由于红黑树始终保持平衡，查找操作的时间复杂度为O(log n)。

综上，红黑树的插入、删除和查找操作的时间复杂度均为O(log n)，其中n为红黑树的节点个数。

红黑树的时间复杂度保持在一个较低的级别，使其在各种应用场景中都能够提供高效的性能。

红⿊树（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出发到达的所有的叶节点具有相同数⽬的⿊节点。

java treeset原理Java中的TreeSet是一个基于红黑树实现的有序集合，具有自动排序和去重功能。

它是Set接口的实现类之一，继承自AbstractSet 类，实现了NavigableSet接口。

本文将深入介绍Java TreeSet的原理，包括红黑树、TreeSet的实现、遍历方式和常用操作等内容。

1. 红黑树红黑树是一种自平衡二叉查找树，它的每个节点都有一个颜色属性，可以是红色或黑色。

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

2. 根节点是黑色。

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

4. 如果一个节点是红色，那么它的子节点必须是黑色。

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

这些特性确保了红黑树的平衡性和搜索效率。

插入、删除节点时，需要对树进行旋转和改变颜色等操作，以维持平衡。

2. TreeSet的实现Java TreeSet是基于红黑树实现的有序集合，它的元素按照自然顺序或者指定的比较器顺序进行排序。

TreeSet中的元素必须是可比较的，即实现了Comparable接口或者传入了Comparator比较器。

TreeSet的底层数据结构是红黑树，它的节点类是TreeMap中的Entry类，包含三个属性：key、value和color。

TreeSet的实现主要涉及以下几个方法：1. add(E e)：向TreeSet中添加元素e。

首先通过比较器或者自然顺序找到要插入的位置，然后将元素包装成Entry对象，插入红黑树中，最后进行平衡操作。

2. remove(Object o)：从TreeSet中删除元素o。

首先通过比较器或者自然顺序找到要删除的节点，然后进行删除操作，最后进行平衡操作。

3. clear()：清空TreeSet中的所有元素。

4. iterator()：返回一个迭代器，按照自然顺序或者指定的比较器顺序遍历元素。

5. size()：返回TreeSet中元素的个数。

STLmap 是C++ STL (Standard Template Library) 中的关联容器，它实现了基于key-value 对的映射功能。

stlmap 的实现原理基于红黑树（Red-Black Tree）数据结构。

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

2. 根节点总是黑色的。

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

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

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

stlmap 利用红黑树的这些性质来实现高效的插入、删除和查找操作。

它通过维护key-value 对的排序顺序来实现这个目标。

具体来说，对于stlmap 中的每个元素，它都存储了一个key 和一个value，并且通过比较key 的大小来维持树的结构。

当插入一个新的key-value 对时，stlmap 会根据key 的大小找到相应的插入位置，并调整树的结构以满足红黑树的性质。

同样地，删除元素和查找元素也是通过维护红黑树的性质来实现的。

由于红黑树具有自平衡的特性，因此stlmap 能够保证在插入、删除和查找操作上的时间复杂度为O(log n)，其中n 是stlmap 中元素的数量。

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

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

你可以在这里获得配套源代码红黑树由来：他是在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 新节点的叔叔是红色。

什么是红黑树
红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B 树（symmetric binary B-trees）。

后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

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

它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。

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

其他平衡树还有：AVL，SBT，伸展树，TREAP 等等。

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

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

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

所以我们都希望树结构都是矮矮胖胖的，像这样：⽽不是像这样：在这种需求下，平衡树（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-节点的⽗节点中去。

红黑树的真实原理红黑树是一种自平衡的二叉查找树，它的设计目的是保持树的平衡，以保证插入、删除和搜索操作的最坏情况时间复杂度都是O(log n)。

红黑树的名字来源于节点的颜色，每个节点都被标记为红色或黑色。

在红黑树中，存在以下五条性质：1. 每个节点要么是红色，要么是黑色。

2. 根节点是黑色的。

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

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

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

这五条性质确保了红黑树的平衡性。

下面将介绍红黑树的插入和删除操作，以及对性质的维护过程。

插入操作：插入一个节点时，首先将其按照二叉查找树的规则插入到合适的位置上，并将该节点标记为红色。

之后，需要对树进行调整，确保红黑树的性质得以维护。

有三种情况需要进行调整：1. 如果插入节点的父节点是黑色的，那么红黑树的性质没有被破坏，无需进行额外的操作。

2. 如果插入节点的父节点是红色的，需要判断父节点的兄弟节点的颜色。

（1）如果父节点的兄弟节点是红色的，将父节点和兄弟节点都变为黑色，祖父节点变为红色，然后以祖父节点为当前节点进行进一步调整。

（2）如果父节点的兄弟节点是黑色的或者NIL节点，需要进行旋转操作，以确保红黑树的性质得以维护。

（a）如果插入节点是其父节点的右子节点，并且父节点是祖父节点的左子节点，需要对父节点进行左旋操作，然后再对祖父节点进行右旋操作。

（b）如果插入节点是其父节点的左子节点，并且父节点是祖父节点的左子节点，需要对祖父节点进行右旋操作。

（c）如果插入节点是其父节点的左子节点，并且父节点是祖父节点的右子节点，需要对父节点进行右旋操作，然后再对祖父节点进行左旋操作。

删除操作：删除一个节点时，首先将其按照二叉查找树的规则删除。

如果删除的节点是红色的，或者删除的节点有一个红色子节点，那么红黑树的性质仍然被保持，无需进行额外的操作。