㈠ 什么是红黑树
最近研究JDK源码的时候，发现TreeMap和TreeSet底层数据结构是红黑树，当然，TreeSet其实本质上就是Value为一个固定值的TreeMap。在JDK1.8以后，HashMap也用到了红黑树。
那红黑树到底是怎样的一种数据结构呢？相信大家都不是非常了解，我也去翻了好多的相关文章，发现一篇很有趣的漫画，可以帮助大家很快了解红黑树大概是怎样的一种数据结构，有哪些特点。 只是大概的介绍一下红黑树，详细的实现大家还是请参考相关的算法书籍。
以下内容转自： 漫画算法：什么是红黑树？
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
下图中这棵树，就是一颗典型的二叉查找树：
1.查看根节点9：
3.由于10 < 13，因此查看左孩子11：
假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12：
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下图中这棵树，就是一颗典型的红黑树：
什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子：
1.向原红黑树插入值为14的新节点：
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：
但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图：
图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图：
图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。
首先，我们需要做的是变色，把节点25及其下方的节点变色：
这时候我们需要把节点13看做X，节点8看做Y，像刚才的示意图那样进行右旋转：
如果想要详细了解红黑树算法，可以参考这篇文章： Java数据结构和算法（十一）——红黑树
㈡ 红黑树(Red-black tree)
树 是一种 抽象数据类型 ，或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的 数据集合 。
红黑树 是一种自平衡二叉查找树，典型的用途是实现 关联数组 ，它是复杂的，但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的 O(log n ) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。
一个由n个节点随机构成的二叉查找树的高度为(log n ).证明如下：
而时间复杂度是以某个基础数据操作的重复次数作为量度。红黑树的是二叉搜索树，左子树上所有节点的值均小于他的根节点的值，右子树上所有节点均大于根节点的值，左右子节树相对根节点按大小分布。如果把每次节点值的比较看成基础数据操作，那么最差的查找情况是一直查找到高度最大的根节点，那么查找的时间复杂度即与高度成正比，可表示成 O(log n ) 。
简单了解了红黑树的字面定义，下面动手感受下红黑树的相关操作。当你插入或者删除一个节点时，可能会破坏红黑树的性质，所以需要对树节点进行重新着色或者旋转，来保持红黑树的结构。首先看下二叉树的旋转。
假设pivot节点不为空，其右子树不为空，那么左旋即是：使pivot的右孩子Y为子树的根，pivot节点为子树根节点的左孩子，pivot左孩子、Y节点的右孩子不改变，Y节点左孩子变为pivot节点右孩子。
假设pivot节点不为空，其左子树不为空，那么右旋：使pivot的左孩子Y为子树的根，pivot节点为子树根节点的右孩子，pivot的右孩子、Y节点的左孩子不变，Y节点的右孩子变为pivot节点的左孩子。
实战演练之增加、删除节点时，如何保证红黑树的性质不被破坏。
往一个空的红黑树中，依次插入数据：12 1 9 2 0 11 7 19 4
节点为根节点，所以为黑色，两个null节点为黑色节点。
按照二叉搜索树的逻辑，9小于12、大于1，应该是1节点的右孩子。但，新增的两个NIL节点已经使得12，1，9，NI这条路径的黑色节点至少为两个，而12，NIL这条路径的黑色节点只有两个。所以要对1节点进行左旋，9节点变为12节点的左孩子，发现问题还是存在。继续，对12节点进行右旋，9节点为根节点，1、12分别为9节点的左右孩子。尝试着色，9节点必须为黑色，而1，12节点可以为红色，也可以为黑色。
0节点直接作为1节点的左孩子，保持跟2节点相同的颜色即可。左右子树依旧保持平衡。
从二叉查找树的性质看，7节点作为2节点的右孩子即可。这时来分析着色问题，我们先看最短路径的黑色分布，9，12，NIL这条路径，有三个黑色节点，以此为参考，尝试改变9节点左子树的着色。目前最长的路径是9，1，2，7，NIL这条路径。保持三个黑色节点的话，9跟NIL已经为黑色节点，而红色节点又不能挨着，所以只能是1为红色节点，2为黑色节点，7为红色节点。那么9，1，0，NIIL这条路径，0就要为黑色节点。调整完毕。
19节点作为12节点的右孩子，与左孩子保持一样的红色即可。
4节点应该作为7节点的左子树，无论着什么颜色，以1节点为根节点的子树，都要破坏红黑性质。所以应该进行旋转。先以7为根节点进行一次右旋，再以2为根节点进行一次左旋。尝试着色即可。
类似插入节点的分析、总结，删除节点也可以针对每种场景找到固定的着色方法，就像玩一个游戏，有自己的推理跟玩法。我先做个PPT，这块稍后补充。
所有的插入、删除都是有限个情况，基于插入、删除的情况分析，即可编写算法生成红黑树，使其在固定的业务场景中发挥红黑树稳定操作效率的特色了。
在 计算机科学 中， AVL树 是最先发明的 自平衡二叉查找树 。在AVL树中任何节点的两个 子树 的高度最大差别为一，所以它也被称为 高度平衡树 。查找、插入和删除在平均和最坏情况下都是 O （log n ）。增加和删除可能需要通过一次或多次 树旋转 来重新平衡这个树。
节点的 平衡因子 是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
不提问题的码农不是好程序员。自己写完了红黑树的简单剖析，感觉还是只懂皮毛，没有从触碰到算法的核心内容。所以，不妨留几个小问题，担心自己脑子生锈或者没事想玩手机的时候，再提笔研究下红黑树。
教你初步了解红黑树
算法的时间复杂度和空间复杂度-总结
红黑树从头至尾插入和删除
AVL树
红黑树C源码实现与剖析
Echo
8 Nov，2016
㈢ 求红黑树应用实例，谢谢！
红黑树用在关联数组、字典的实现上。需要的空间比散列表小。
任何键值对应，需要随机存储和键有序的情况都可以用。
实例中
内存中比如缓存的(区块-数据)，编号对应内容，引索号对应数据项
日期对应日程。价格对应商品。
应用遍及，在内存中使用效率比较高
㈣ HashMap与SparseArray简单总结
HashMap：
1、hashMap采用了数组+链表+红黑树来存储数据。
2、每一个键值对封装为一个节点Node<K,V>,存在一个数组Node<K,V>[] table，其元素为Node节点。其次，数组中每个元素也都有一个链表结构，此链表用来存储下标位置相同但内容不同的节点，每有一个这样的节点就插入到链表尾部。
3、put操作时，使用key的hashcode值计算其在table中的数组索引，遍历数组，找到该索引元素，如果为空，则直接将node插入到当前数组位置。
4、若不为空，判断两个key的hashcode值和内容是否相等，相等则直接替换value，插入完成。
5、若两个节点不是同一个，那么开始遍历节点所在的链表，在链表中查找比较key，没有查找到则插入到链表尾部。若链表size大于8，则将其转为红黑树，将节点插入到树中。为什么是8呢，可以看下源码里的解释，
``
``
设为8其实是一个保底策略。因为链表的长度分布满足泊松分布，长度为8的概率为千万分之六，可以说接近于0了。这么设置的用意在于，保证在极端情况下，链表不会无限制增长，否则查找消耗会非常大。此时将其转为红黑树，查找效率会优于链表。而只要我们哈希函数设置合理的话，链表的长度基本都达不到8，也不会出现转为红黑树的最差情况。
6、table的初始size为16，每次添加完table元素后会判断是否超出，超出就进行扩容，扩容size总为2的幂。还有一个关键的属性，负载因子loadFactor，初始值为0.75。这个负载因子表示table的存储空间利用率，我们知道，table不是所有位置都会存储元素的。为什么要设为0.75，首先，如果这个负载因子越大，表明空间利用率越高，扩容的次数相对就少，但是这样在插入新元素时发生位置碰撞的几率就越大，进而就会增加对应链表的长度，那么链表变长了，查询效率相应地就变低了；而若负载因子越小，那么空间利用率越低，table中空闲位置越多，同样的表的长度相对地只能存储更少的元素，因此插入元素时发生扩容操作的机会就越大，元素更多的是存在table数组中，而不是发生冲突存到链表中，查找效率会比较快。
总结起来，上述两种情况各有优劣。综合考虑空间开销和查找效率，负载因子既不能太大也不能太小。又因为，链表的长度满足泊松分布，大于8的几率微乎其微，把负载因子设为0.75，链表长度基本不可能超过8，同时更不可能转化为红黑树了。所以设为0.75是在通常情况下，综合考虑了查找效率和空间开销的折衷选择。
7、关于红黑树，它也是一种二叉搜索树，红黑树的查找效率优于二叉搜索树，增删的效率优于平衡二叉树。可以认为是结合了两者的优点。
SparseArray：
1、sparsearray采用了int[] mKeys 和 Object[] mValues两个数组来分别存储key和value。
2、对于某个key值，先查找其在mKeys中的索引i，直接mValues[i]获取key对应的value，也就是说key与其对应的value存储下标是一样的。
且看sparsearray的put方法，非常易懂，
``
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
``
3.sparsearray对mKeys数组做了正序排列，因此，在进行遍历查找key时，使用的是二分查找法，一切为了效率。
4.sparsearray使用int类型，不同与hashmap使用Integer，省去了自动装箱过程，消耗更少内存。
总的来说，sparseArray内存性能优于hashMap，一般适用于key为整型值，数据量较少的应用场景。也是考虑内存优化时替代Hash Map的首选。
㈤ 什么是红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
树的旋转
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。
㈥ 红黑树的用途
红黑树用在关联数组、字典的实现上。需要的空间比散列表小。 任何键值对应,需要随机存储和键有序的情况都可以用。
㈦ 红黑树和平衡二叉树 区别
红黑树和平衡二叉树的主要区别如下：
平衡二叉树（AVL）树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而的英文旋转非常耗时的。所以平衡二叉树（AVL）适合用于插入与删除次数比较少，但查找多的情况。
红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log
n)。所以红黑树适用于搜索，插入，删除操作较多的情况。
(7)红黑树主要用来存储有序的数据扩展阅读：
平衡二叉树在Windows
NT内核中广泛存在。
红黑树的应用：
1、在C
++的STL中，地图和集都是用红黑树实现的；
2、着名的Linux的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
3、IO多路复用的epoll的的的实现采用红黑树组织管理的sockfd，以支持快速的增删改查；
4、Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
5、Java中的TreeMap中的实现。
参考资料：
网络-平衡二叉树
网络-红黑树
㈧ 红黑树的术语
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当起始位置的功能，它不是任何节点的儿子，我们称之为根节点或根。它有最多两个儿子，都是它连接到的其他节点。所有这些儿子都可以有自己的儿子，以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。
如果一个节点没有儿子，我们称之为叶子节点，因为在直觉上它是在树的边缘上。子树是从特定节点可以延伸到的树的某一部分，其自身被当作一个树。在红黑树中，叶子被假定为 null 或空。
由于红黑树也是二叉查找树，它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
㈨ 红黑树-算法导论
这个周看算法导论，看到红黑树，看的我云里雾里绕啊。虽然最后看懂了，据我估计，要是过一个星期不看保证忘干净，因此决定写篇博客记录下红黑树。
红黑树是二叉树的一种，所以学习红黑树必须先搞懂二叉树。
如图，一颗二叉树是按照结点（二叉树结构）组成的。每个结点可以用链表结构标示。每个结点都应该有left right p ，他们分别指向左儿子，右儿子和父结点。每个结点还应该有个关键字key。如果某个儿子结点不存在，则相应位置就是nil。跟结点是树中唯一的父结点值是nil的节点。
设x为二叉树中的一个结点，如果y是x的左子树中的一个结点，则key[y]<=key[x]。如果y是x的右子树中的一个结点，则key[x]<=key[y]
我们有很多结点，如何将他组合成符合二叉树性质的二叉树呢？
我们一般通过下面两种方式遍历二叉树中的key
树根的关键字（key）在左子树和右子树的关键字之间输出就是 中序遍历算法
树根的关键字（key）在左子树和右子树的关键字之前输出就是 前序遍历算法
从图中我们能看出只要沿着各个结点的left指针查找下去，知道遇见nil 时候为止，就是最小值，最大值正好相反。
如图，3的前趋是2， 后继是6。
前趋后继的规律是什么呢?
前趋：如果结点x的左子树为非空，则x的前趋就是做子树中的最右结点。要是x的左子树为nil ，并且有前趋y（key是最最小值对应的x是没有前趋的），那么y是x的最低祖先，并且y的右儿子也是x的祖先。（x必须出现在y的右儿子的分支中，并且y是最低祖先）
后继：如果结点x的右子树为非空，则x的后继就是右子树中的最左结点。要是x的右子树为nil ，并且有后继y（key是最大值对应的x是没有后继的），那么y是x的最低祖先，并且y的左儿子也是x的祖先。（x必须出现在y的左儿子的分支中，并且y是最低祖先）
这里一定要搞明白，因为这里是红黑树删除的基础部分。
二叉树结点的删除分三种情况。
这里针对第三种情况的删除，我们不是删除z，而是删除的是z的后继y，把y的值赋值给z，这样不破坏树中的结构。变成了只是删除了一个叶子，这个叶子的特点是 左儿子是nil 。
红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或者Black。通过对任何一条从跟到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
树中每个结点包含五个域：color，key ，left，right 和p。如果某结点没有一个子结点或者父结点，则该结点相应的指针为nil。
从图中我们能看出每个叶子节点都是nil。nil对象都是一样的。干嘛不用一个nil 代替呢。因此如下结构。
旋转应该是二叉树的性质，只是普通二叉树没必要旋转。红黑树需要旋转来平衡树结构。
结果如下。
右旋的过程只是相反而已。
左旋的作用是将右儿子变成父结点。
右旋的作用是将左儿子变成父结点。
这样变化有什么用处呢？
我们知道，红黑树就是二叉树，因此向二叉树中插入数据没有啥区别。只是不过，当我们插入结点的某些时候就破坏了红黑树性质。因此，我们需要对二叉树进行调整让其适合红黑树的特性。
下面我们应该分析什么情况下插入结点能破坏红黑树。
假如我们插入的结点是黑色的，肯定是破坏了二叉树的性质5。（除非是根节点不破坏。）
但是我们插入的结点是红色的，不一定破坏二叉树的五条性质，为了方便，我们还是将二叉树插入的结点染成红色的比较好。(情况变少)
当我们插入一个红色结点可能破坏那些性质呢？第一条和第三条肯定是不会被破坏的，恒成立的。第五条因为插入的结点是红色的肯定也是成立的。这里可能不成立的是第二条（跟结点是黑的，要是插入的结点就是根结点）和第四条（如果一个结点是红的，它的两个儿子是黑的，因为要是插入的结点的父结点是红的话，那么父父结点就不符合要求了）。
因此，红黑树的结构被破坏就两种情况，不是性质2就是性质4.
性质2好解决，将结点染成黑色的就行了。不做分析。
我们重点分析性质4破坏，我们如何修正。
我们知道性质4被破坏的条件是父节点是红色的。
如图
这里我们分情况讨论 s 的颜色。
第一种情况 ： s的结点是红色。
这个情况，我们从根到左边的黑色结点数是2 ，右边的黑色结点数是2。
那么我们如何将其变成从跟到叶子的所有路线的结点数是2还不破坏红黑树呢？
只有下面一种变化才能符合红黑树，这样从根向下就符合红黑树了。
将祖父结点（跟结点）变成红色，p 和s 结点都变成 黑节点。
从上面的结果图我们能看出来， 根父 的颜色不定，可能是红色的，也可能是黑色的，那么我们就应该让 根 当做被插入的新节点，遍历根父 的兄弟的结点的颜色情况情况。这其实就是递归了。
要是每个根父的兄弟结点都是红色的话，那么遍历到根就结束了。将根染成黑色即可。要是根父的兄弟不是红色，那么就应该进入到第二种情况了。
第二种情况：s结点是黑色的。
这种情况不管如何变化，让总结点数不变的情况下，单纯染色根本没有办法让所有结点符合红黑树特性。让从根到叶子的路径含有相同的黑色结点。 那么怎么办呢？
我们知道，二叉树可以旋转，旋转可以改变树的结构。
这里我们用根做旋转（左旋或者右旋），结果如下
我们看看旋转结果，结果1，根变成p儿子的一边黑色结点树没有变化。而x的一边黑色结点数量减少了1。那我们如何让x一边增加1呢？只有如下一种情况，将p染成黑色，根染成红色。
结果2是无法达到我们的要求的，因此我们需要抛弃掉这种情况，让s是黑的时候只能变成结果1。
结果1所有的情况下都满足红黑树，不需要进行递归了。
这里我们需要看看什么情况下，x结点是p结点的儿子而不是根结点的儿子。这里我们需要看左旋右旋逻辑图了。
因此这里我们总结下结果1 的条件
结果2 就是剩下的。那么要是结果2的情况，我们应该如何处理呢。
那么结果2 在右旋的结构图就很清晰了。如下。p的右儿子是插入的结点x。
这种情况如何解决呢？
因为x是p的右儿子，所以旋转只能是左旋转。我们以p为根节点旋转。
结果如下
这样就变成了结果1 准备右旋转的的情况了。
同理，情况2的左旋图就变成了结果1准备左旋图的情况了。
总结
这里上面的方法是算法导论给出的，下面的是自己实现的。
删除操作和二叉树的操作一样，同样的只不过是删除的时候，可能引起对红黑树性质的破坏。
这里把删除二叉树的总结搬过来
这里我们罗列下这三种情况各个删除结点的结构。
二叉树第一种情况：没有儿子的情况。
二叉树第二种情况：只有一个儿子。左儿子或者右儿子。有四种情况
二叉树第三种情况：最多有一个右儿子
我们看出来，第三种情况不是第一种情况，就是第二种情况。因此这里我们只需要研究第一种情况和第二种情况就行了。
当x是红色的时候
将x删除，我们发现红黑树的黑色结点的数量不会发生任何变化。红黑树结构正常
我们发现不管什么条件下，删除红色结点红黑树不会发生任何变化。
这里我们需要讨论下 p 和 s的颜色，我们知道p 和s 分别只有红色和黑色，并且p 和s 不能同时为红色。那么p 和s的组合情况只有三种了。
我们发现不管哪一种情况都删除x的那一支都缺少一个黑色结点。
组合1
组合一通过染色是不可能达到树的平衡的。（有人好说了，把p染成黑色，s染成红色不就行了？我刚开始也犯了这个错误，要是s的两个儿子是红色怎么办呢？红色是不参与节点数计算的。）
因此我们这里直能通过旋转来改变树的结构来看看能不能达到我们的要求。我们以p旋转看看结果如下。
这貌似也不行，因为SL 可能是红色的，违反性质4。因此我们可以看出来，p是红色的情况下，旋转一次想让红黑树平衡依赖S的两个结点的颜色。
要是p左旋，那么s的左孩子是黑色的就可以。要是p右旋，那么s的右孩子是黑色的就可以了。
因此这里讨论下s的两个孩子的颜色情况。
如果SL 和SR 都是红色怎么处理呢？
单纯的旋转根本不可能让红黑树成立。只能先改变颜色在旋转了。
颜色改变如下
要是SL 和SR都是黑色的情况下
结构图如下
这种结构图 SL SR 都是nil。这种情况下旋转一下 p就行了。
SR SL只有一个颜色是红色的。如果p的删除分支是左儿子。那么SL 是红色，只能以s先右旋转。这样就变成了 SL SR都是黑色，但是s是红色的情况。是SL ,SR变化成平衡树的中间过程
最后这种情况，和SL SR 都是黑色一样的处理。
组合2
这里我们单纯靠染色是不可能实现树平衡的。因为删除x的结点的一支的结点都是黑色的。没有可以改变的红色结点存在。怎么办呢？我们只能通过旋转将删除的节点的一支上面增加红色结点才行。这里有个s是红色的，我们需要让其到删除结点分支上。
旋转结果
这样组合2删除结点的分支上有红色结点了。到这里我们发现这个地方的树可能违反红黑树了。
违反1：根是红色的话，s是红色违反性质4.
违反2：p结点黑节点数量还是对不上。违反性质5
不过没关系，要是我们能通过染色让树平衡的话，不用再调整树的结构的话，那么组合2也就算是解决了。
貌似通过染色也解决不了这个树平衡的问题，不过违反的红黑树的地方可以减少，我们将s染成黑色，p染成红色。
这里我们发现只有 p删除结点的一支，黑色结点数量少一。正好是组合一的情况。按照组合一的情况做一次旋转就可以解决问题
组合三
这种情况是最复杂的了。我们知道S要是红色，这就是组合2的情况，要是p是红色，那么就是组合1了。那我们想办法怎么让s或者p变成红色的呢？我们先从叶子节点找红色结点，看能不能让s或者p变成红色的。肯定是可以的。不过有一定条件。这里需要依赖SL,SR的颜色了。
当SL,SR都是红色，这种变化只通过改变颜色就可以让s变成红色，变成组合2的情况。
当SL,SR 只有一个红色的时候，通过改变颜色是不能达到要求的。因此我们就需要做旋转来达到要求。
当SL SR 都是黑色。没有红色，p结点一下是不能解决这个问题的。那怎么办呢？这样只能依赖p的父类了。不过这里需要注意的是p本身不平衡，我们这里依赖p的父类的时候，p需要是平衡的。如何平衡p呢？
我们只需要将s变成红色就可以了。p就平衡了。
不过这里注意，p的这一整支的所有分支都是少黑色结点1 的。
这里我们注意到p只有一个儿子。这里我们需要把p当成删除结点x的一个儿子。这样就转换成了x带一个儿子的情况了。这种情况如何平衡树。下面讨论一个孩子的时候包含，暂时不在这里讲解。
先拿一种情况分析 x是p的左儿子，x有一个左儿子
分析L 如果L是黑色的话，肯定是nil。因此可以将这种只有一个儿子的情况转换成没有儿子的情况。也可以这么说，要是x有儿子，儿子的颜色一定不是黑色。而是红色。如图
㈩ TreeMap理解
jdk:1.8
本文将介绍java中集合框架中实现 Map 接口 TreeMap ， TreeMap 实现 map 接口提供根据元素 key 自然排序或使用自定义排序规则来存储元素，之前文章有介绍 HashMap 和 LinkedHashMap ，可以对比来查看有些地方是相似，建议查看本文之前阅读之前介绍文章
TreeMap 元素默认排序是按照自然排序，对于 Integer 是按照升序，对于字符按照字母顺序，下面例子：
上面增加key是无序，但是返回key的 set 是有升序，同时使用字符串，存储是自然序-字母顺序
下面是例子：
TreeMap 不像 hash map 和linked hash map，不需要hash来定位元素位置，因为没有使用数组来存储元素
如果自然排序不能满足需求，初始化时候可以自定义排序规则，下面例子使用 Integer 降序排列：
hashMap 不能保证key排序存储和出现相同排序，但是 TreeMap 可以保证key总是有序性存储
现在已经知道TreeMap存储元素是有序，因为 TreeMap 属性，可以查询最大，最小，查找key小于或者大于固定值，等等，下面介绍小部分情况例子：
TreeMap 实现 NavigableMap 接口和内部工作规则使用红黑树：
红黑树超过了本文介绍访问，然而这些key存储是有序
首先：红黑数保证元素数据结构一致性，可以想象是棵芒果树在天空下，树上分支向下成长，树的根节点元素是第一个节点，从根节点出发，任何元素左节点小于中间节点，右节点大于中间节点，定义大于或者小于自然排序或者自定义排序初始化时候，这个规则保证 TreeMap 元素总是有序和可以预测顺序
第二：红黑树是自平衡树，以上属性保证基本操作，例如：搜索 、获取、增加、和删除时间复杂度是O(log n),在增加和删除过程中，会改变树形状，树的长分支搜索需要时间比较长，短分支需要时间短， TreeMap 自平衡保证红黑树特性，不会使上面情况发生，因此考虑到使用红黑树设计，对每次删除和插入，最大树高度被维持需要时间复杂度O(log n)，例如 树自平衡，
上面hash map 和linked hash map，tree map不是线程安全，因此多线程环境处理方式和之前讲相似
之前介绍 HashMap 和 LinkedHashMap 实现，现在是 TreeMap ，很重要概况下它们三者之区别：
HashMap 适合一般场景，实现提供存储和 获取操作，缺点是存放元素是无序和，在排序场景 性能低下，需要遍历所有元素来进行排序
TreeMap 完全自己控制key` 排序，在另一方面，性能会比其他性能差
TreeMap 在没有引起性能问题情况下，linked hash map提高hash map排序问题
本文讨论 java 中 TreeMap 和内部实现,因此最后一系列文章中讨论共同 map 接口实现，简单讨论
之间优缺点使用情况