教你透彻了解红黑树概论

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

本文适合那些有对二叉树有一定的基础，并且熟悉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. 要删除的节点没有子节点或只有一个子节点：直接删除该节点，并将其子节点接替上来。

红黑树简介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)步之所以将新插入的节点的颜色赋为红色，是因为：如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。

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

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

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

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

一、红黑树的定义红黑树是一种自平衡二叉查找树，它满足以下性质：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. 删除操作在红黑树中删除一个节点时，也需要进行相应的调整，以保持树的平衡。

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