- 1SpringBoot详细整合MQTT消息_springboot集成mqtt
- 2元图：通过元学习进行小样本的链接预测_元图meta-gragh
- 3SCAU 8579 链式线性表的基本操作_scau数据结构链式表
- 4市场需求驱使下的开源与闭源战争：是谁主导了大模型的未来？_开源 闭源 市场竞争
- 5Python编程高级技巧和最佳实践----一网打尽_python最高境界
- 6Nginx使用SSL加密并隐藏真实地址详细教程_nginx 隐藏真实的url
- 7【代码集合】深度强化学习Pytorch实现集锦
- 8C++ 11新特性详解_c++11新特性
- 9Redhat7.7安装docker_finished dependency resolution error: package: doc
- 10发散阅读、拓宽思路【PageRank、Tf-Idf、协同过滤、分布式训练、StyleTransfer、Node2vec】_pagerank和tfidf
数据结构—红黑树(RedBlackTree)的实现原理以及Java代码的实现【两万字】_redblacknode
赞
踩
详细介绍了红黑树的概念和实现原理，并且提供了Java代码的完全实现。本文内容较多，欢迎收藏。
文章目录
1 红黑树的概述
- 二叉排序树的详解以及Java代码的完全实现，其中有关于插入和删除的详细原理解释，这是必须掌握的前置知识。
- 平衡二叉树(AVL树)的详解以及Java代码的完全实现，其中有关于节点旋转的详细原理解释，这是必须掌握的前置知识。
- 多路查找树中的2-3树、2-3-4树、B树、B+树的详解，很多人说可以利用2-3树来理解红黑树，或许可以，但实际上2-3树不是必须掌握的前置知识。
1.1 AVL树与红黑树
AVL树是一种自平衡的二叉查找树，又称平衡二叉树。AVL用平衡因子判断是否平衡并通过旋转来实现平衡，它的平衡的要求是：所有节点的左右子树高度差不超过1。AVL树是一种高平衡度的二叉树，执行插入或者删除操作之后，只要不满足上面的平衡条件，就要通过旋转来保持平衡，并且由于旋转比较耗时，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况。
由于维护这种高度平衡所付出的代价可能比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。
红黑树(Red Black Tree)，它一种特殊的二叉查找树，是AVL树的特化变种，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树的平衡的要求是：从根到叶子的最长的路径不会比于最短的路径的长超过两倍。 因此，红黑树是一种弱平衡二叉树，在相同的节点情况下，AVL树的高度<=红黑树。
红黑树是用弱平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，降低了对旋转的要求，从而提高了性能，所以对于查询，插入，删除操作都较多的情况下，用红黑树。
1.2 红黑树的定义
AVL树的定义如下：
- 它一定是一棵二叉排序树。
- 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，递归定义。
相对于AVL树，红黑树的定义明显更加复杂：
- 它一定是一棵二叉排序树。
- 每个节点或者为黑色或者为红色。
- 根节点一定为黑色。
- 如果一个节点是红色的，那么它的子节点要么是null要么是黑色的（也就是说，不能有两个相邻的红色节点，即红色节点的父、左子、右子节点只能是黑色节点）。
- 对于每个节点，从该节点到其所有叶子节点的路径中都包含相同数量的黑色节点。
根据上面的定义，可以推算出：
- 因为黑色节点数量要一样，红色不能连着来，从而路径全黑时最短，红黑交替时最长。因此可以推算出：红黑树从根到叶子节点的最长的路径不会比于最短的路径的长超过两倍。红黑树是一种弱平衡二叉树，在相同的节点情况下，AVL树的高度<=红黑树。
- 红黑树的高度最坏情况下为2log(N+1)。因此它也可以在O(log n)时间内做查找，插入和删除。
有一些红黑树定义还有一个性质：“红黑树中叶子节点为最后的空节点，并且每个叶子节点是黑色的”。该定义并不会对之前的定义产生影响，其目的更多是为了简化平衡操作的情况，平衡时可以认为：null就是黑色节点。此时只需要考虑红和黑这两种情况就行，而不用考虑非红非黑的null。如下图：
1.3 红黑树的应用
红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
实际上，Robert Sedgewick在《算法（第4版）》 中说过，红黑树等价于2-3树。其中2-节点等价于普通平衡二叉树的节点，3-节点本质上是非平衡性的缓存。
也就是说在添加、删除节点之后需要重平衡时，相当于2-节点 与3-节点间的转换，由于3-节点的缓存作用，能够吸收一部分不平衡性，从而减少旋转次数，减少重平衡时间。
尽管由于红黑树的最大高度高于AVL树导致此查询时稍慢，但是差距不大，而添加、删除数据时红黑树快于AVL树，红黑树的旋转次数为O(1)，即最多旋转3次；而AVL的旋转次数为O(logN)，即最多向上旋转至根节点。整体来看，红黑树的综合效率高于AVL树，红黑树比AVL树的应用范围更广泛！
AVL的应用：
- Windows NT内核
红黑树的应用：
- JDK1.8及之后版本的Map实现，比如HashMap、TreeMap、ConcurrentHashMap。
- 广泛用于C++的STL中，map和set都是用红黑树实现的。
- 著名的linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间。
- IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查。
- ngnix中，用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器。
2 自底向上实现原理
和AVL树一样，在插入和删除之后，可能需要重平衡。红黑树的重平衡除了旋转之外，还有改变着色。在下面的实现原理中，我们就会将null节点当成黑色节点，主要是为了方便理解。
下面主要讲解红黑树的插入和删除操作，理解了这两个操作，那么其他操作比如求最值就非常简单了。
要想理解红黑树的实现原理，必须先理解二叉排序树的和平衡二叉树的实现原理，其中红黑树的插入、删除操作依赖于二叉排序树的插入、删除操作，插入、删除之后的重平衡中的“旋转”操作依赖于平衡二叉树中的“旋转”操作，同时红黑二叉树的重平衡中还增加了“变色”的操作。
本文中，对于基础的插入操作和旋转操作并没有详细讲解，没有掌握的的应该先看看下列文章：
- 二叉排序树的详解以及Java代码的完全实现，其中有关于插入和删除的详细原理解释，这是必须掌握的前置知识。
- 平衡二叉树(AVL树)的详解以及Java代码的完全实现，其中有关于节点旋转的详细原理解释，这是必须掌握的前置知识。
- 多路查找树中的2-3树、2-3-4树、B树、B+树的详解，很多人说可以利用2-3树来理解红黑树，或许可以，但实际上2-3树不是必须掌握的前置知识。
2.1 插入操作
由于红黑树是一颗二叉排序树，插入时通常是把新的节点作为树叶放到树中。
如果我们把该节点涂成黑色，那么肯定违反条件5，因为将会建立一条更长的黑节点的路径。因此，新节点必须涂成红色。
如果它的父节点是黑色的，则插入完成。如果它的父节点已经是红色的，那么得到连续红色的节点，这就违反了条件4。在这种情况下，我们必须调整该树以确保满足条件5且又不引起条件4被破坏。用于完成这项任务的基本操作是节点颜色的改变和节点的旋转。
插入步骤大概分为两步：
- 使用二叉查找树的插入方法，将红色节点插入。
- 如果此时树结构不符合红黑树的要求，那么通过旋转和重新着色等一系列操作使之重新成为一颗红黑树。
第一步插入就是使用的二叉排序树的插入的方法，比较简单。下面主要来看看插入节点之后是如何调整树结构的！为了方便，我们规定所有null节点都是黑色的！
插入过程中可能会用的关键节点如下：
插入之后的情况总结起来分为如下几种：
- 新插入节点N作为根基点，简称“新根”；
- 新插入节点N的父节点为黑色，简称“父黑”；
- 新插入节点N的父节点为红色，叔节点为黑色，简称“父红叔黑”；
- 新插入节点N的父节点为红色，叔节点为红色，简称“父红叔红”；
2.1.1 新根
新节点N作为根节点，为了满足条件3，此时直接将N节点涂黑即可。
2.1.2 父黑
父节点为黑色时，此时是天然的平衡。不需要任何调整。
2.1.3 父红叔黑
若是叔节点是null节点则同样默认为黑色。父红叔黑的情况又分为四种情况：
- 在祖父节点G的左孩子节点P的左子树中插入节点N，简称“LL”；
- 在祖父节点G的左孩子节点P的右子树中插入节点N，简称“LR”；
- 在祖父节点G的右孩子节点P的左子树中插入节点N，简称“RL”；
- 在祖父节点G的右孩子节点P的右子树中插入节点N，简称“RR”。
其中第1种情况和第4种情况是对称的，被称为发生“外边”的情况或者称为外侧插入，可以通过单旋转来解决，而第2种情况和第3种情况是对称的，被称为发生在“内边”的情况或者称为内测插入，需要双旋转来解决。
如果了解AVL树，那么对上面的四种情况肯定不会陌生，因为这就是AVL树需要调整平衡的四种情况。 AVL树对这四种情况的调整方法是：情况1采用单右旋、情况4采用单左旋即可解决问题。情况2需要采用左-右双旋、情况3需要采用右-左双旋。
红黑树的平衡也是采用同样的方式旋转，但是多了一个调整颜色的步骤。
2.1.3.1 LL
在节点G的左孩子节点P的左子树中插入元素N，简称LL，即情况1，此时将G右旋，然后P涂黑，G涂红；
2.1.3.2 RR
在节点G的右孩子节点P的右子树中插入元素N，简称RR，即情况4，此时将G左旋，然后P涂黑，G涂红；
2.1.3.3 LR
在节点G的左孩子节点P的右子树中插入元素N，简称LR，即情况2，此时先将P左旋，实际上是转换为LL的情况，然后将G右旋；然后N涂黑，G涂红。
2.1.3.4 RL
在节点G的右孩子节点P的左子树中插入元素N，简称RL，即情况3，此时先将P右旋，实际上是转换为RR的情况，然后将G左旋；然后N涂黑，G涂红。
2.1.3.5 总结
在上面4种情况中，旋转后的新根节点最后均被涂成了黑色，这样无论曾祖父节点（原祖父节点的父节点，即新根节点的父节点）是什么颜色都能兼容。并且旋转变色的结果对于原来通向各个子树的黑色节点个数保持不变。
2.1.4 父红叔红
父节点和叔节点为红色时，此时就不能直接采用上面方法处理了。
此时可以将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
该递归操作借助栈结构来保存路径，Java的实现直接使用方法递归就行了，因为方法的啊递归就是借用的栈结构！
2.2 删除操作
如同其他的二叉树一样，红黑树的删除操作难于插入操作。红黑树的删除操作任然和二叉排序树的删除类似，只不过加上旋转和颜色属性。
操作的步骤大概分为两步为：
- 通过二叉排序树的删除方法，将该节点从红黑树中删除；
- 如果此时树结构不符合红黑树的要求，那么通过旋转和重新着色等一系列手段使之重新成为一棵红黑树。
删除操作的第一步就是根据二叉排序树的规则寻找最终被删除节点，对于真正需要被删除的节点，二叉排序树的寻找过程如下：
- 没有子节点，那么就是找到的节点。
- 要么只有一个左或右子节点，那么同样就是找到的节点。
- 对于具有两个子节点的节点，这里采用寻找被删除节点的右子树的最小节点，然后交换该节点和右子树最小节点值，这样真正被删除的节点还是转换成为了1或者2的情况（二叉排序树的右子树的最小节点只可能是“没有子节点”或者“只有右子节点”的情况）。
因此，最终被删除节点只能是没有子节点，或者只有一个左或右子节点的情况。在下面的介绍中，“被删除的节点“均是指“真正被删除的节点”。
在删除操作中，可能会用到的关键节点如下：
单独的删除过程比较简单，我们主要看在删除之后是如何重新调整平衡成为红黑树的。为了方便，同样将null节点看成黑色！
根据最终被删除节点的情况，可以分为以下几种情况：
- 被删除的节点N为红色，简称“删红”；
- 被删除的节点N为黑色，子节点C为红色，简称“删黑子红”；
- 被删除的节点N为黑色，子节点C为黑色（null算黑色），简称“删黑子黑”；
2.2.1 删红
如果被删除节点N是红色的，那么一切好办，由于是N红色节点，删除N后不会影响红黑树的平衡性，与其他节点的颜色无关，因此不需要做任何调整。
上图的二叉树中，如果要删除BR，那么直接删除该节点就行了，很简单；
如果要删除P，实际上真正应该被删除的节点是BL节点，那么实际上也被转换成“删红”的情况，只需要在删除BL之前交换P和BL的key、value值。
2.2.2 删黑子红
如果被删除节点N为黑色，则该节点所在的路径上的黑色节点总数将会减少1，红黑树失去平衡，需要调整。
如果被删除节点N的子节点C（无论左右）为红色，那么C肯定存在并且C是N路径上的唯一后继，如果把C的颜色设置为黑色，那么就能恢复N之前所在路径的黑色节点的总数，与其他节点的颜色无关，平衡调整完成。
2.2.3 删黑子黑
如果被删除节点N为黑色，子节点C也为黑色(null也看成黑色)，因为子节点本身就是黑色，那么就不能简单的后继子节点C涂黑来补充黑色这么简单了，那么需要分三种情况考虑：
- 被删除节点N是根节点，简称“删根”；
- 被删除节点N的兄弟节点B为红色，简称“删兄红”；
- 被删除节点N的兄弟节点B为黑色(null也看成黑色)，简称“删兄黑”；
2.2.3.1 删根
被删除节点N是根节点，那好办，直接删除就行了，任何无需平衡操作。
2.2.3.2 删兄红
如果不是根节点，并且被删除节点N的兄弟节点B为红色。
这里如果子节点C为null也看成黑色节点，并且由于红黑树的定义，我们可以断定B的子节点一定都是黑色（null也看成黑色），P一定是黑色。
删除节点N之后，C代替了N的位置，继续判定原兄弟节点B是左兄弟还是右兄弟，又分两种情况讨论：
- B在右边，简称“右兄弟”；
- B在左边，简称“左兄弟”；
2.2.3.2.1 右兄弟
如果B是右兄弟，则以父节点P为基点左旋，然后B涂黑、P涂红，最后将BL看成新的兄弟节点newB；
2.2.3.2.2 左兄弟
如果B是左兄弟，则以父节点P为基点右旋，然后B涂黑、P涂红，最后将BR看成新的兄弟节点newB；
2.2.3.2.3 总结
我们发现，实际上情况2的处理就是先转变成情况3-“删兄黑”，然后统一处理。
2.2.3.3 删兄黑
如果不是根节点，并且被删除节点的兄弟节点为黑色（null也当成黑色），这里又分为两种情况：
- 兄节点B的子节点全是黑色节点，简称“兄子全黑”；
- 兄节点B的子节点不全是黑色节点，简称“兄子非全黑”；
2.2.3.3.1 兄子全黑
兄弟节点的子节点全是黑色（null节点当成黑色节点，如果兄弟节点也是null节点，也，兄子节点同样算黑色节点）；此时，不用区分左右，但根据父节点又分为两种情况：
- 父节点P是黑色，简称“父黑”；
- 父节点P是红色，简称“父红”；
2.2.3.3.1.1 父黑
父节点P是黑色。
将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到 删黑子黑的 情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
2.2.3.3.1.2 父红
父节点P是红色。
将兄弟节点B涂红，父节点P涂黑即可。此时原本删除黑色节点的路径补充了黑色节点，即可达到平衡。
2.2.3.3.2 兄子非全黑
兄弟节点的子节点不全是黑色，那么可以分为左红右黑、左黑右红、左红右红；此时分为以下几种情况：
- 兄弟节点B在右边，且兄右子节点BR为黑色，简称“兄右，右子黑”；
- 兄弟节点B在右边，且兄右子节点BR为红色，简称“兄右，右子红”；
- 兄弟节点B在左边，且兄左子节点BL为黑色，简称“兄左，左子黑”；
- 兄弟节点B在左边，且兄左子节点BL为红色，简称“兄左，左子红”；
2.2.3.3.2.1 兄右，右子黑
兄弟节点B在右边，且兄右子节点BR为黑色。
此时兄左子节点BL肯定为红色，以兄弟节点B为基点右旋，然后BL涂黑，B涂红，然后将BL当成新B，B当成新BR，这样就转换成了情况2-“兄右，右子红”。
2.2.3.3.2.2 兄右，右子红
兄弟节点B在右边，且兄右子节点BR为红色；
此时兄左子节点BL可红可黑，父节点P可红可黑。以父节点P为基点左旋，然后交换P和B的颜色（实际上就是兄弟节点的颜色设置为父节点的颜色，父节点涂黑，因为兄弟节点肯定是黑色的），BR涂黑，平衡完毕！
2.2.3.3.2.3 兄左，左子黑
兄弟节点B在左边，且兄左子节点BL为黑色。
该情况是情况1的对称情况。此时兄右子节点肯定为红色，以兄弟节点B为基点左旋，然后BR涂黑，B涂红，然后将BR当成新B，B当成新BL，这样就转换成了情况4-“兄左，左子红”。
2.2.3.3.2.4 兄左，左子红
兄弟节点B在左边，且兄左子节点BL为红色。
该情况是情况2的对称情况。此时兄右子节点BR可红可黑，父节点P可红可黑。以父节点P为基点右旋，然后交换P和B的颜色（实际上就是兄弟节点的颜色设置为父节点的颜色，父节点涂黑，因为兄弟节点肯定是黑色的），BL涂黑，平衡完毕！
2.2.3.3.2.5 总结
实际上情况1、3是对称的，情况2、4是对称的。上面的步骤的实质是利用旋转恢复被删除节点N路径上的黑色节点总数，最后P和B虽然交换了颜色，但它们最后都作为N路径的祖先节点，因此n路径上的黑色节点数增加1，恢复了N路径的黑色节点数量。同时红色子节点最终涂黑，保证了该条路径的黑色节点数目。
2.3 总结
上面的只是理论原理，在下面的实现中，提供了根据实际案例进行插入和删除的执行流程详尽分析！
2.3.1 插入
2.3.2 删除
3 红黑树的实现
3.1 实现代码
key-value形式的红黑树的简单实现，该实现并没有借助NIL哨兵节点，因此额外处理了节点为null的情况，增加了代码量，实际上借助NIL的实现更加简单和易懂，如果看懂了没有借助NIL的实现，那么借助NIL的实现应该很容易改该写出来。
本实现的注释非常详尽，如果了解了上面讲的原理应该很容易看懂！
/**
* key-value形式的红黑树的简单实现,该实现并没有借助NIL哨兵节点
* 主要方法:
* =====public=====
* {@link RedBlackTree#RedBlackTree()} 构建红黑树对象，使用自然比较器
* {@link RedBlackTree#RedBlackTree(Comparator)} 构建红黑树对象，使用自定义比较器
* {@link RedBlackTree#put(Object, Object)} 存放k-v键值对，将按照key的大小排序
* {@link RedBlackTree#remove(Object)} 根据key尝试查找并尝试删除对应的键值对
* {@link RedBlackTree#toInorderTraversalString()} 中序遍历红黑树（顺序输出）
* {@link RedBlackTree#minKey()} 获取最小的key
* {@link RedBlackTree#maxKey()} 获取最大的key
* {@link RedBlackTree#get(Object)} 根据key获取value
* =====private=====
* {@link RedBlackTree#binaryTreePut(RedBlackNode, RedBlackNode)} 使用二叉排序树的方式尝试插入节点
* {@link RedBlackTree#rebalanceAfterPut(RedBlackNode)} 插入节点之后进行重平衡
* {@link RedBlackTree#searchRemoveNode(Object, RedBlackNode)} 使用二叉排序树的方式尝试寻找真正需要被删除的节点
* {@link RedBlackTree#removeNode(RedBlackNode)} 使用二叉排序的方式删除节点,并对部分简单情况进行重平衡
* {@link RedBlackTree#rebalanceAfterRemove(RedBlackNode, RedBlackNode)} 对复杂情况进行重平衡
* {@link RedBlackTree#rotateLeft(RedBlackNode)} 左旋
* {@link RedBlackTree#rotateRight(RedBlackNode)} 右旋
* {@link RedBlackTree#rotateLeftAndRight(RedBlackNode)} 左-右双旋
* {@link RedBlackTree#rotateRightAndLeft(RedBlackNode)} 右-左双旋
*
* @author lx
*/
public class RedBlackTree<K, V> {
/**
* 自定义比较器
*/
private Comparator<? super K> cmp;
/**
* 树节点的数量
*/
private int size;
/**
* 红黑树的根节点，默认为null
*/
private RedBlackNode<K, V> root;
/**
* 红黑树节点对象
*
* @param <K> key类型
* @param <V> value类型
*/
private static final class RedBlackNode<K, V> {
/**
* 节点颜色，true 红色 false 黑色
*/
boolean red;
/**
* 关键字
*/
K key;
/**
* 值
*/
V value;
/**
* 左子节点
*/
RedBlackNode<K, V> left;
/**
* 左子节点
*/
RedBlackNode<K, V> right;
/**
* 父节点
*/
RedBlackNode<K, V> parent;
public RedBlackNode(boolean red, K key, V value, RedBlackNode<K, V> left, RedBlackNode<K, V> right) {
this.red = red;
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
public RedBlackNode(boolean red, K key, V value) {
this.red = red;
this.key = key;
this.value = value;
}
public RedBlackNode(K key, V value) {
this.key = key;
this.value = value;
}
public RedBlackNode() {
}
public RedBlackNode(RedBlackNode<K, V> parent) {
this.parent = parent;
}
@Override
public String toString() {
return "{" +
"key=" + key +
", value=" + value +
'}';
}
}
/**
* 空的构造器,使用自然顺序比较
*/
public RedBlackTree() {
}
/**
* 指定比较器
*
* @param cmp 指定比较器
*/
public RedBlackTree(Comparator<? super K> cmp) {
this.cmp = cmp;
}
/**
* 插入,开放给外部使用的api
* 插入步骤大概分为两步：
* 1) 使用二叉查找树的插入方法，将红色节点插入；
* 2) 如果此时树结构不符合红黑树的要求，那么通过旋转和重新着色等一系列操作使之重新成为一颗红黑树。
*
* @param key 插入的key
* @param value 插入的value
*/
public void put(K key, V value) {
/*0检查key*/
checkKey(key);
/*1二叉排序树的插入，需要增加的步骤是记录父节点*/
//创建被插入的节点,默认红色
RedBlackNode<K, V> kvRedBlackNode = new RedBlackNode<>(true, key, value, null, null);
//返回root,但此时新的节点可能已经被插入进去了
int oldSize = size;
root = binaryTreePut(kvRedBlackNode, root);
/*2如果确实插入了节点元素,那么调整平衡*/
if (size > oldSize) {
rebalanceAfterPut(kvRedBlackNode);
}
}
/**
* 根据key删除键值对，大概分为两步：
* 1) 通过二叉排序树的删除方法，将该节点从红黑树中删除；
* 2) 如果此时树结构不符合红黑树的要求，那么通过旋转和重新着色等一系列手段使之重新成为一棵红黑树。
* <p>
* 该实现实际上分为三步:
* searchRemoveNode: 使用二叉排序的删除方法,尝试寻找需要真正被删除的Node节点，没有进行删除
* removeNode: 用二叉排序的方法删除节点,并进行部分调整,对于复杂的情况,返回需要进行重平衡的c节点
* rebalanceAfterRemove: 如果c不等于null,说明被删除节点N是黑色节点且需要进行进一步的重平衡
*
* @param key 需要删除的key
* @return 被删除的key对应的value
*/
public V remove(K key) {
checkKey(key);
/*1使用二叉排序的删除方法,尝试寻找需要真正被删除的Node节点，没有进行删除*/
RedBlackNode<K, V> removeNode = searchRemoveNode(key, root);
if (removeNode == null) {
return null;
}
V value = removeNode.value;
/*2、用二叉排序的方法删除节点,并进行部分调整,对于复杂的情况,返回需要进行重平衡的c节点*/
RedBlackNode<K, V> n = removeNode(removeNode);
/*3、如果c不等于null,说明被删除节点N是黑色节点且需要进行进一步的重平衡*/
if (n != null) {
rebalanceAfterRemove(n.right, n.parent);
}
return value;
}
/**
* 用于删除节点并且进行部分重平衡：对于“删红”，“删黑子红”，“删黑子黑-删根”这三种简单的情况进行了判断和重平衡
*
* @param n 真正需要被删除的节点,该节点要么没有子节点,要么只有一个左或者右子节点
* @return 还需要进一步被重平衡操作的节点，或者null-表示不需要进一步重平衡操作
*/
private RedBlackNode<K, V> removeNode(RedBlackNode<K, V> n) {
/*首先删除子节点*/
RedBlackNode<K, V> left = n.left;
RedBlackNode<K, V> right = n.right;
RedBlackNode<K, V> parent = n.parent;
//n的子节点
RedBlackNode<K, V> child = null;
/*如果父节点不为null*/
if (parent != null) {
//如果n是父节点的左子节点
if (parent.left == n) {
//如果n的左右子节点都为null
if (left == null && right == null) {
parent.left = null;
child = null;
}
//如果n的左子节点不为null
else if (left != null) {
parent.left = left;
left.parent = parent;
child = left;
}
//如果n的右子节点不为null
else {
parent.left = right;
right.parent = parent;
child = right;
}
}
//如果n是父节点的右子节点
if (parent.right == n) {
//如果n的左右子节点都为null
if (left == null && right == null) {
parent.right = null;
child = null;
}
//如果n的左子节点不为null
else if (left != null) {
parent.right = left;
left.parent = parent;
child = left;
}
//如果n的右子节点不为null
else {
parent.right = right;
right.parent = parent;
child = right;
}
}
}
/*如果父节点为null,则说明要删除的节点是根节点*/
else {
//如果n的左右子节点都为null
if (left == null && right == null) {
root = null;
child = null;
}
//如果n的左子节点不为null
else if (left != null) {
left.parent = null;
root = left;
child = left;
}
//如果n的右子节点不为null
else {
right.parent = null;
root = right;
child = right;
}
}
/*1 被删除的节点为红色，这里处理了；*/
if (n.red) {
/*1.2由于是N红色节点，删除N后不会影响红黑树的平衡性，与其他节点的颜色无关，因此不需要做任何调整。*/
return null;
}
/*2 被删除的节点为黑色，子节点为红色，这里处理了；*/
else if (child != null && child.red) {
/*2.1首先删除节点*/
/*2.2将后继C涂黑，平衡调整完成。*/
child.red = false;
return null;
}
/*3 被删除的节点为黑色，子节点为黑色；
* 这里又要分为多种情况：
* 1) 被删除节点N是根节点，简称“删根”，这里处理了；
* 2) 被删除节点N的兄弟节点B为红色，简称“删兄红”，这里没有处理，在rebalanceAfterRemove方法中处理；
* 3) 被删除节点N的兄弟节点B为黑色(null也看成黑色)，简称“删兄黑”，这里没有处理，在rebalanceAfterRemove方法中处理；
* */
else {
/*3.1 被删除节点N是根节点，简称“删根”*/
/*那好办，任何无需平衡操作*/
if (n.parent == null) {
return null;
}
/*剩下两种复杂情况,此时需要进一步进行复杂的平衡操作*/
//将n的子节点(null或左子节点或右子节点)设置为右子节点,方便后面调整的时候取出来
n.right = child;
return n;
}
}
/**
* 删除节点之后进行重平衡,用于处理下面两种复杂的情况
* 2) 被删除节点N的兄弟节点B为红色，简称“删兄红”；
* 3) 被删除节点N的兄弟节点B为黑色(null也看成黑色)，简称“删兄黑”；
*
* @param c 需要进行平衡的节点
* @param p 需要进行平衡的节点的父节点
*/
private void rebalanceAfterRemove(RedBlackNode<K, V> c, RedBlackNode<K, V> p) {
//获取兄弟节点
RedBlackNode<K, V> brother;
/*如果c是左子节点,那么brother就是右兄弟*/
if (c == p.left) {
brother = p.right;
/*3.2 被删除节点N的兄弟节点为红色，简称删兄红； 且是右兄弟*/
if (brother != null && brother.red) {
/*以父节点P为基点左旋*/
rotateLeft(p);
/*然后B涂黑P涂红（交换颜色）*/
brother.red = false;
p.red = true;
/*最后将BL看成新的兄弟节点newB；将情况二转换为情况三*/
brother = p.right;
}
/*3.3 如果被删除节点N的兄弟节点为黑色，简称删兄黑；且是右兄弟*/
/*3.3.1 兄节点的子节点不全是黑色节点，简称兄子非全黑；下面针对右兄弟分为两种情况*/
if (brother != null) {
//排除都为null
if (!(brother.right == null && brother.left == null)) {
//排除都为黑色
if (!(brother.right != null && !brother.right.red && brother.left != null && !brother.left.red)) {
/*3.3.1.1 兄弟节点在右边，且兄右子节点为黑色；*/
if (brother.right == null || !brother.right.red) {
if (brother.left != null) {
brother.left.red = false;
}
brother.red = true;
/*以兄弟节点B为基点右旋*/
rotateRight(brother);
/*将BL当成新B，B当成新BR，这样就转换成了情况2。*/
brother = p.right;
}
/*3.3.1.2 兄弟节点在右边，且兄右子节点为红色；*/
if (brother.right != null && brother.right.red) {
/*交换P和B的颜色*/
boolean color = p.red;
p.red = brother.red;
brother.red = color;
/*BR涂黑*/
brother.right.red = false;
/*以父节点P为基点左旋*/
rotateLeft(p);
return;
}
}
}
}
}
/*如果c是右子节点,那么brother就是左兄弟*/
else {
brother = p.left;
/*3.2 被删除节点N的兄弟节点为红色，简称删兄红；且是左兄弟*/
if (brother != null && brother.red) {
/*以父节点P为基点右旋，然后B涂黑P涂红（交换颜色），最后将BR看成新的兄弟节点newB；
* 将情况二转换为情况三*/
/*以父节点P为基点右旋*/
rotateRight(p);
/*然后B涂黑P涂红（交换颜色）*/
brother.red = false;
p.red = true;
/*最后将BR看成新的兄弟节点newB；将情况二转换为情况三*/
brother = p.left;
}
/*3.3 如果被删除节点N的兄弟节点为黑色，简称删兄黑；且是左兄弟*/
/*3.3.1 兄节点的子节点不全是黑色节点，简称兄子非全黑；下面针对左兄弟分为两种情况*/
if (brother != null) {
//排除都为null
if (!(brother.right == null && brother.left == null)) {
//排除都为黑色
if (!(brother.right != null && !brother.right.red && brother.left != null && !brother.left.red)) {
/*3.3.1.3 兄弟节点在左边，且兄左子节点为黑色；*/
if (brother.left == null || !brother.left.red) {
if (brother.right != null) {
brother.right.red = false;
}
brother.red = true;
/*以兄弟节点B为基点左旋*/
rotateLeft(brother);
/*将BR当成新B，B当成新BL，这样就转换成了情况4。*/
brother = p.left;
}
/*3.3.1.4 兄弟节点在左边，且兄左子节点为红色；*/
if (brother.left != null && brother.left.red) {
/*交换P和B的颜色*/
boolean color = p.red;
p.red = brother.red;
brother.red = color;
/*BL涂黑*/
brother.left.red = false;
/*以父节点P为基点右旋*/
rotateRight(p);
return;
}
}
}
}
}
/*3.3.2 兄节点的子节点全是黑色节点，简称兄子全黑；*/
/*如果兄弟节点为null，也算全黑*/
if (brother == null) {
/*3.3.2.1 父节点P是黑色；*/
/*如果父节点还有父节点，那么进行递归，否则没有意义*/
if (p.parent != null && !p.red) {
rebalanceAfterRemove(p, p.parent);
}
/*3.3.2.2 父节点P是红色；*/
else {
p.red = false;
}
} else {
//都为null
if (brother.left == null && brother.right == null) {
/*3.3.2.1 父节点P是黑色；*/
/*如果父节点还有父节点，那么进行递归，否则没有意义*/
if (p.parent != null && !p.red) {
/*将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，
回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。*/
brother.red = true;
rebalanceAfterRemove(p, p.parent);
}
/*3.3.2.2 父节点P是红色；*/
else {
brother.red = true;
p.red = false;
}
}
//都为黑色
else if (brother.left != null && brother.right != null && !brother.left.red && !brother.right.red) {
/*3.3.2.1 父节点P是黑色；*/
/*如果父节点还有父节点，那么进行递归，否则没有意义*/
if (p.parent != null && !p.red) {
/*将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，
回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。*/
brother.red = true;
rebalanceAfterRemove(p, p.parent);
}
/*3.3.2.2 父节点P是红色；*/
else {
brother.red = true;
p.red = false;
}
}
}
}
/**
* 尝试寻找需要真正被删除的Node节点
*
* @param key 匹配的key
* @param root 从根节点开始递归查找
* @return 找到的节点, 或者为null, 表示没找到
*/
private RedBlackNode<K, V> searchRemoveNode(K key, RedBlackNode<K, V> root) {
if (root == null) {
return null;
}
/*调用比较的方法*/
int i = compare(key, root.key);
/*如果大于0，则说明e>root.data 继续查询右子树*/
if (i > 0) {
return searchRemoveNode(key, root.right);
}
/*如果小于0，则说明e<root.data 继续查询左子树*/
else if (i < 0) {
return searchRemoveNode(key, root.left);
} else {
/*如果等于0，则说明key=root 即查询成功 开始做好删除的准备,返回真正需要被删除的节点*/
size--;
/*如果两个子节点都不为null*/
if (root.left != null && root.right != null) {
/*递归查找最小的节点*/
RedBlackNode<K, V> min = findMin(root.right);
/*然后交换元素值*/
K tempKey = min.key;
min.key = root.key;
root.key = tempKey;
V tempValue = min.value;
min.value = root.value;
root.value = tempValue;
/*返回真正需要被删除的节点,即在右子树中找到的大于root的最小节点*/
return min;
} else {
/*如果一个子节点不为null，则返回该子节点；或者两个子节点都为null，则返回该节点*/
return root;
}
}
}
/**
* 查找真正被删除的最小的节点
*
* @param root 根节点
* @return 最小的节点
*/
private RedBlackNode<K, V> findMin(RedBlackNode<K, V> root) {
/*如果该节点没有左子节点，那么该节点就是最小的节点，返回*/
if (root.left == null) {
return root;
}
/*如果该节点存在左子节点，那么继续向左递归查找*/
return findMin(root.left);
}
/**
* 查找最小的key
*
* @return 最小的节点的key
*/
public K minKey() {
if (root == null) {
return null;
}
/*如果该节点存在左子节点，那么继续向左递归查找*/
return findMin(root).key;
}
private RedBlackNode<K, V> findMax(RedBlackNode<K, V> root) {
/*如果该节点没有右子节点，那么该节点就是最小的节点，返回*/
if (root.right == null) {
return root;
}
/*如果该节点存在左子节点，那么继续向左递归查找*/
return findMax(root.right);
}
/**
* 查找最大的key
*
* @return 最大的节点的key
*/
public K maxKey() {
if (root == null) {
return null;
}
/*如果该节点存在左子节点，那么继续向左递归查找*/
return findMax(root).key;
}
/**
* 根据key,查找value
*
* @return 最大的节点的key
*/
public V get(K Key) {
/*如果该节点存在左子节点，那么继续向左递归查找*/
RedBlackNode<K, V> kvRedBlackNode = searchRemoveNode(Key, root);
if (kvRedBlackNode != null) {
return kvRedBlackNode.value;
}
return null;
}
/**
* 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口
*
* @param k1 被比较的第一个对象
* @param k2 被比较的第二个对象
* @return 0 相等 ;小于0 k1 < k2 ;大于0 k1 > k2
*/
private int compare(K k1, K k2) {
if (cmp != null) {
return cmp.compare(k1, k2);
} else {
return ((Comparable<K>) k1).compareTo(k2);
}
}
/**
* 添加节点之后再平衡，需要分多种情况讨论:
* 1) 新插入节点N作为根基点，简称“新根”；
* 2) 新插入节点N的父节点为黑色，简称“父黑”；
* 3) 新插入节点N的父节点为红色，叔节点为黑色，简称“父红叔黑”；
* 4) 新插入节点N的父节点为红色，叔节点为红色，简称“父红叔红”；
*
* @param newNode 新增加的节点
*/
private void rebalanceAfterPut(RedBlackNode<K, V> newNode) {
//获取父节点
RedBlackNode<K, V> parent = newNode.parent;
/*1 新插入节点N作为根基点，简称“新根”*/
if (parent == null) {
//直接涂黑即可
newNode.red = false;
return;
}
/*2 新插入节点N的父节点为黑色，简称“父黑”*/
else if (!parent.red) {
//无需调整
return;
}
/*3 新插入节点N的父节点为红色 下面需要分情况讨论*/
/*3.1首先获取一系列与新节点相关的的节点*/
//获取祖父节点
RedBlackNode<K, V> grandParent = parent.parent;
//获取叔节点
RedBlackNode<K, V> uncle = parent == grandParent.left ? grandParent.right : grandParent.left;
/*3.2 叔节点为红色，简称“父红叔红”*/
if (uncle != null && uncle.red) {
/*将newNode节点的父节点叔节点颜色染成黑色，祖父节点染成红色。*/
parent.red = false;
uncle.red = false;
grandParent.red = true;
/*此时祖父节点可能与其父节点颜色冲突，因此需要递归的解决*/
rebalanceAfterPut(grandParent);
}
/*3.3 如果叔节点为黑色,，简称“父红叔黑” 需要分四种情况讨论
* 1) 在祖父节点G的左孩子节点P的左子树中插入节点N，简称“LL”； 右旋,换色
* 2) 在祖父节点G的左孩子节点P的右子树中插入节点N，简称“LR”； 左旋+右旋,换色
* 3) 在祖父节点G的右孩子节点P的左子树中插入节点N，简称“RL”； 右旋+左旋,换色
* 4) 在祖父节点G的右孩子节点P的右子树中插入节点N，简称“RR”。 左旋,换色
* */
else {
/*3.3.1 在祖父节点G的左孩子节点P的左子树中插入节点N，简称“LL”； 右旋,换色*/
if (grandParent.left == parent && parent.left == newNode) {
/*P涂黑，G涂红*/
parent.red = false;
grandParent.red = true;
/*以G为基点右旋*/
rotateRight(grandParent);
}
/*3.3.2 在祖父节点G的左孩子节点P的右子树中插入节点N，简称“LR”； 左旋+右旋,换色*/
else if (grandParent.left == parent && parent.right == newNode) {
/*N涂黑，G涂红*/
newNode.red = false;
grandParent.red = true;
/*左-右双旋*/
rotateLeftAndRight(grandParent);
}
/*3.3.3 在祖父节点G的右孩子节点P的左子树中插入节点N，简称“RL”； 右旋+左旋,换色*/
else if (grandParent.right == parent && parent.left == newNode) {
/*N涂黑，G涂红*/
newNode.red = false;
grandParent.red = true;
/*右-左双旋*/
rotateRightAndLeft(grandParent);
}
/*3.3.4 在祖父节点G的右孩子节点P的右子树中插入节点N，简称“RR”。 左旋,换色*/
else {
/*P涂黑，G涂红*/
parent.red = false;
grandParent.red = true;
/*以G为基点左旋*/
rotateLeft(grandParent);
}
}
}
/**
* LL,右旋,类似于AVL树的右旋操作,但是需要更新父节点,并且不需要返回值,因为这并不是递归的再平衡
* 这里的k1k2对应着右旋模型中的点位
* 通解:右旋之后，k2成为根节点，k1成为k2的右子节点，k2的右子树2成为k1的左子树
*
* @param k1 右旋的基点
*/
private void rotateRight(RedBlackNode<K, V> k1) {
//获取基点的父节点
RedBlackNode<K, V> parent = k1.parent;
//获取k2,k2是k1的左子节点
RedBlackNode<K, V> k2 = k1.left;
//k2的右子树成为k1的左子树
k1.left = k2.right;
//如果k2的右子树不是null树，则更新右子树的父节点的引用
if (k2.right != null) {
k2.right.parent = k1;
}
//k1成为k2的右子节点
k2.right = k1;
//更新k1的父节点的引用
k1.parent = k2;
//如果k1之前是根节点,则k2成为根节点,更新根节点的引用
if (parent == null) {
this.root = k2;
//如果k1是父节点的左子节点,那么更新父节点的左子节点的引用
} else if (k1 == parent.left) {
parent.left = k2;
} else {
//如果k1是父节点的右子节点,那么更新父节点的右子节点的引用
parent.right = k2;
}
//最后更新k2的父节点的引用
k2.parent = parent;
}
/**
* RR,左旋,类似于AVL树的左旋操作,属于右旋的镜像，但是需要更新父节点,并且不需要返回值,因为这并不是递归的再平衡
* 这里的k1k2对应着左旋模型中的点位
* 通解:左旋之后，k2成为根节点，k1成为k2的左子节点，k2的左子树2成为k1的右子树
*
* @param k1 左旋的基点
*/
private void rotateLeft(RedBlackNode<K, V> k1) {
//获取基点的父节点
RedBlackNode<K, V> parent = k1.parent;
//获取k2,k2是k1的右子节点
RedBlackNode<K, V> k2 = k1.right;
//k2的左子树成为k1的右子树
k1.right = k2.left;
//如果k2的左子树不是null树，则更新左子树的父节点的引用
if (k2.left != null) {
k2.left.parent = k1;
}
//k1成为k2的左子节点
k2.left = k1;
//更新k1的父节点的引用
k1.parent = k2;
//如果k1之前是根节点,则k2成为根节点,更新根节点的引用
if (parent == null) {
this.root = k2;
//如果k1是父节点的左子节点,那么更新父节点的左子节点的引用
} else if (k1 == parent.left) {
parent.left = k2;
} else {
//如果k1是父节点的右子节点,那么更新父节点的右子节点的引用
parent.right = k2;
}
//最后更新k2的父节点的引用
k2.parent = parent;
}
/**
* RL,右-左双旋，类似于AVL树的右-左双旋
* 通解：将k3当作新的根节点，并且先使得k2右旋成为k3的右子树，然后k1左旋成为k3的左子树，并且左子树2成为k1的右子树，右子树2成为k2的左子树
*
* @param k1 需要旋转的最小不平衡树根节点
*/
private void rotateRightAndLeft(RedBlackNode<K, V> k1) {
/*1先对k1的右子节点k2进行右旋,然后使得成为k3成为的k1的左子树*/
rotateRight(k1.right);
/*2然后对k1进行左旋,成为k3的左子树,返回的根节点就是k3,即返回旋转之后的根节点*/
rotateLeft(k1);
}
/**
* LR，左-右双旋，类似于AVL树的左-右双旋，很简单,实际上就是右-左双旋的镜像
* 通解: 将k3当作新的根节点，并且先使得k2左旋成为k3的左子树，然后k1右旋成为k3的右子树，并且左子树2成为k2的右子树，右子树2成为k1的左子树
*
* @param k1 需要旋转的最小不平衡树根节点
*/
private void rotateLeftAndRight(RedBlackNode<K, V> k1) {
/*1先对k1的左子节点k2进行左旋,使得k3成为的k1的左子树*/
rotateLeft(k1.left);
/*2然后对k1进行右旋,成为k3的右子树,此时根节点就变成了k3*/
rotateRight(k1);
}
/**
* 检查key
*
* @param key key
*/
private void checkKey(K key) {
if (key == null) {
throw new NullPointerException("key为null");
}
}
/**
* 二叉排序树的方式插入节点，同时记录父节点
*
* @param kvRedBlackNode 需要被插入的节点
* @param root 根节点
*/
private RedBlackNode<K, V> binaryTreePut(RedBlackNode<K, V> kvRedBlackNode, RedBlackNode<K, V> root) {
/*没有查找到,那么直接构建新的节点返回,将会在上一层方法中被赋值给其父节点的某个引用,这个插入的位置肯定是该遍历路径上的最后一点
* 即插入的元素节点肯定是属于叶子节点*/
if (root == null) {
size++;
return kvRedBlackNode;
}
/*调用比较的方法*/
int i = compare(kvRedBlackNode.key, root.key);
/*如果大于0，则说明kvRedBlackNode>root 继续查询右子树*/
if (i > 0) {
//增加更新父节点的操作
kvRedBlackNode.parent = root;
root.right = binaryTreePut(kvRedBlackNode, root.right);
/*如果小于0，则说明kvRedBlackNode<root 继续查询左子树*/
} else if (i < 0) {
//增加更新父节点的操作
kvRedBlackNode.parent = root;
root.left = binaryTreePut(kvRedBlackNode, root.left);
} else {
/*如果等于0，则说明kvRedBlackNode=root 即已经存在节点 替换value*/
root.value = kvRedBlackNode.value;
}
//没查询到最底层,则返回该节点
return root;
}
/**
* 保存遍历出来的节点数据
*/
List<RedBlackNode<K, V>> str = new ArrayList<>();
/**
* 中序遍历,提供给外部使用的api
*
* @return 遍历的数据
*/
public String toInorderTraversalString() {
//如果是空树,直接返回空
if (root == null) {
return null;
}
//从根节点开始递归
inorderTraversal(root);
//获取遍历结果
String s = str.toString();
str.clear();
return s;
}
/**
* 中序遍历 内部使用的递归遍历方法,借用了栈的结构
*
* @param root 节点,从根节点开始
*/
private void inorderTraversal(RedBlackNode<K, V> root) {
RedBlackNode<K, V> left = getLeft(root);
if (left != null) {
//如果左子节点不为null,则继续递归遍历该左子节点
inorderTraversal(left);
}
//添加数据节点
str.add(root);
//获取节点的右子节点
RedBlackNode<K, V> right = getRight(root);
if (right != null) {
//如果右子节点不为null,则继续递归遍历该右子节点
inorderTraversal(right);
}
}
/**
* 获取左子节点
*
* @param parent 父节点引用
* @return 左子节点或者null--表示没有左子节点
*/
private RedBlackNode<K, V> getLeft(RedBlackNode<K, V> parent) {
return parent == null ? null : parent.left;
}
/**
* 获取右子节点
*
* @param parent 父节点引用
* @return 右子节点或者null--表示没有右子节点
*/
private RedBlackNode<K, V> getRight(RedBlackNode<K, V> parent) {
return parent == null ? null : parent.right;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
- 444
- 445
- 446
- 447
- 448
- 449
- 450
- 451
- 452
- 453
- 454
- 455
- 456
- 457
- 458
- 459
- 460
- 461
- 462
- 463
- 464
- 465
- 466
- 467
- 468
- 469
- 470
- 471
- 472
- 473
- 474
- 475
- 476
- 477
- 478
- 479
- 480
- 481
- 482
- 483
- 484
- 485
- 486
- 487
- 488
- 489
- 490
- 491
- 492
- 493
- 494
- 495
- 496
- 497
- 498
- 499
- 500
- 501
- 502
- 503
- 504
- 505
- 506
- 507
- 508
- 509
- 510
- 511
- 512
- 513
- 514
- 515
- 516
- 517
- 518
- 519
- 520
- 521
- 522
- 523
- 524
- 525
- 526
- 527
- 528
- 529
- 530
- 531
- 532
- 533
- 534
- 535
- 536
- 537
- 538
- 539
- 540
- 541
- 542
- 543
- 544
- 545
- 546
- 547
- 548
- 549
- 550
- 551
- 552
- 553
- 554
- 555
- 556
- 557
- 558
- 559
- 560
- 561
- 562
- 563
- 564
- 565
- 566
- 567
- 568
- 569
- 570
- 571
- 572
- 573
- 574
- 575
- 576
- 577
- 578
- 579
- 580
- 581
- 582
- 583
- 584
- 585
- 586
- 587
- 588
- 589
- 590
- 591
- 592
- 593
- 594
- 595
- 596
- 597
- 598
- 599
- 600
- 601
- 602
- 603
- 604
- 605
- 606
- 607
- 608
- 609
- 610
- 611
- 612
- 613
- 614
- 615
- 616
- 617
- 618
- 619
- 620
- 621
- 622
- 623
- 624
- 625
- 626
- 627
- 628
- 629
- 630
- 631
- 632
- 633
- 634
- 635
- 636
- 637
- 638
- 639
- 640
- 641
- 642
- 643
- 644
- 645
- 646
- 647
- 648
- 649
- 650
- 651
- 652
- 653
- 654
- 655
- 656
- 657
- 658
- 659
- 660
- 661
- 662
- 663
- 664
- 665
- 666
- 667
- 668
- 669
- 670
- 671
- 672
- 673
- 674
- 675
- 676
- 677
- 678
- 679
- 680
- 681
- 682
- 683
- 684
- 685
- 686
- 687
- 688
- 689
- 690
- 691
- 692
- 693
- 694
- 695
- 696
- 697
- 698
- 699
- 700
- 701
- 702
- 703
- 704
- 705
- 706
- 707
- 708
- 709
- 710
- 711
- 712
- 713
- 714
- 715
- 716
- 717
- 718
- 719
- 720
- 721
- 722
- 723
- 724
- 725
- 726
- 727
- 728
- 729
- 730
- 731
- 732
- 733
- 734
- 735
- 736
- 737
- 738
- 739
- 740
- 741
- 742
- 743
- 744
- 745
- 746
- 747
- 748
- 749
- 750
- 751
- 752
- 753
- 754
- 755
- 756
- 757
- 758
- 759
- 760
- 761
- 762
- 763
- 764
- 765
- 766
- 767
- 768
- 769
- 770
- 771
- 772
- 773
- 774
- 775
- 776
- 777
- 778
- 779
- 780
- 781
- 782
- 783
- 784
- 785
- 786
- 787
- 788
- 789
- 790
- 791
- 792
- 793
- 794
- 795
- 796
- 797
- 798
- 799
- 800
- 801
- 802
- 803
- 804
- 805
- 806
- 807
- 808
- 809
- 810
- 811
- 812
- 813
- 814
- 815
- 816
- 817
- 818
- 819
- 820
- 821
- 822
- 823
- 824
- 825
- 826
- 827
- 828
- 829
- 830
- 831
- 832
- 833
- 834
- 835
- 836
- 837
- 838
- 839
- 840
- 841
- 842
- 843
- 844
- 845
- 846
- 847
- 848
- 849
- 850
- 851
- 852
- 853
- 854
- 855
- 856
- 857
- 858
- 859
- 860
- 861
- 862
- 863
- 864
- 865
- 866
- 867
- 868
- 869
- 870
3.2 测试代码
public class RedBlackTreeTest<E> {
@Test
public void test3() {
RedBlackTree<Integer, Integer> integerIntegerRedBlackTree = new RedBlackTree<>();
integerIntegerRedBlackTree.put(3, 47);
integerIntegerRedBlackTree.put(2, 16);
integerIntegerRedBlackTree.put(1, 73);
integerIntegerRedBlackTree.put(4, 1);
integerIntegerRedBlackTree.put(5, 24);
integerIntegerRedBlackTree.put(6, 59);
integerIntegerRedBlackTree.put(7, 59);
integerIntegerRedBlackTree.put(16, 59);
integerIntegerRedBlackTree.put(15, 59);
integerIntegerRedBlackTree.put(14, 11);
integerIntegerRedBlackTree.put(13, 59);
integerIntegerRedBlackTree.put(12, 59);
integerIntegerRedBlackTree.put(11, 12);
integerIntegerRedBlackTree.put(10, 59);
integerIntegerRedBlackTree.put(8, 59);
integerIntegerRedBlackTree.put(9, 59);
/*中序遍历输出,即根据排序顺序从小到大输出*/
System.out.println(integerIntegerRedBlackTree.toInorderTraversalString());
System.out.println(integerIntegerRedBlackTree.remove(2));
System.out.println(integerIntegerRedBlackTree.remove(4));
System.out.println(integerIntegerRedBlackTree.remove(5));
System.out.println(integerIntegerRedBlackTree.remove(12));
System.out.println(integerIntegerRedBlackTree.remove(7));
System.out.println(integerIntegerRedBlackTree.remove(13));
System.out.println(integerIntegerRedBlackTree.remove(8));
System.out.println(integerIntegerRedBlackTree.remove(16));
System.out.println(integerIntegerRedBlackTree.remove(11));
System.out.println(integerIntegerRedBlackTree.remove(10));
System.out.println(integerIntegerRedBlackTree.remove(14));
System.out.println(integerIntegerRedBlackTree.remove(3));
System.out.println(integerIntegerRedBlackTree.remove(9));
System.out.println(integerIntegerRedBlackTree.remove(6));
System.out.println(integerIntegerRedBlackTree.remove(15));
System.out.println(integerIntegerRedBlackTree.remove(1));
System.out.println(integerIntegerRedBlackTree.toInorderTraversalString());
}
@Test
public void test1() {
RedBlackTree<Integer, Integer> integerIntegerRedBlackTree = new RedBlackTree<>();
integerIntegerRedBlackTree.put(47, 47);
integerIntegerRedBlackTree.put(16, 16);
integerIntegerRedBlackTree.put(73, 73);
integerIntegerRedBlackTree.put(1, 1);
integerIntegerRedBlackTree.put(24, 24);
integerIntegerRedBlackTree.put(59, 59);
integerIntegerRedBlackTree.put(20, 20);
integerIntegerRedBlackTree.put(35, 35);
integerIntegerRedBlackTree.put(62, 62);
integerIntegerRedBlackTree.put(77, 77);
integerIntegerRedBlackTree.put(77, 101);
/*中序遍历输出,即根据排序顺序从小到大输出*/
System.out.println(integerIntegerRedBlackTree.toInorderTraversalString());
System.out.println(integerIntegerRedBlackTree.remove(47));
System.out.println(integerIntegerRedBlackTree.remove(62));
System.out.println(integerIntegerRedBlackTree.remove(77));
System.out.println(integerIntegerRedBlackTree.remove(16));
System.out.println(integerIntegerRedBlackTree.remove(20));
System.out.println(integerIntegerRedBlackTree.remove(59));
System.out.println(integerIntegerRedBlackTree.remove(1));
System.out.println(integerIntegerRedBlackTree.remove(24));
System.out.println(integerIntegerRedBlackTree.remove(35));
System.out.println(integerIntegerRedBlackTree.remove(73));
System.out.println(integerIntegerRedBlackTree.toInorderTraversalString());
}
@Test
public void test2() {
RedBlackTree<Integer, Integer> integerIntegerRedBlackTree = new RedBlackTree<>();
integerIntegerRedBlackTree.put(1, 47);
integerIntegerRedBlackTree.put(2, 16);
integerIntegerRedBlackTree.put(4, 73);
integerIntegerRedBlackTree.put(9, 1);
integerIntegerRedBlackTree.put(5, 24);
integerIntegerRedBlackTree.put(7, 59);
integerIntegerRedBlackTree.put(6, 59);
/*中序遍历输出,即根据排序顺序从小到大输出*/
System.out.println(integerIntegerRedBlackTree.toInorderTraversalString());
System.out.println(integerIntegerRedBlackTree.remove(2));
System.out.println(integerIntegerRedBlackTree.remove(4));
System.out.println(integerIntegerRedBlackTree.remove(1));
System.out.println(integerIntegerRedBlackTree.remove(6));
System.out.println(integerIntegerRedBlackTree.remove(7));
System.out.println(integerIntegerRedBlackTree.remove(5));
System.out.println(integerIntegerRedBlackTree.remove(9));
System.out.println(integerIntegerRedBlackTree.toInorderTraversalString());
}
@Test
public void test4() {
RedBlackTree<Integer, Integer> integerIntegerRedBlackTree = new RedBlackTree<>();
integerIntegerRedBlackTree.put(1, 47);
integerIntegerRedBlackTree.put(2, 16);
integerIntegerRedBlackTree.put(4, 73);
integerIntegerRedBlackTree.put(9, 1);
integerIntegerRedBlackTree.put(5, 24);
integerIntegerRedBlackTree.put(7, 59);
integerIntegerRedBlackTree.put(6, 59);
/*中序遍历输出,即根据排序顺序从小到大输出*/
System.out.println(integerIntegerRedBlackTree.toInorderTraversalString());
System.out.println("maxkey=====>" + integerIntegerRedBlackTree.maxKey());
System.out.println(integerIntegerRedBlackTree.remove(9));
System.out.println("maxkey=====>" + integerIntegerRedBlackTree.maxKey());
System.out.println("minkey=====>" + integerIntegerRedBlackTree.minKey());
System.out.println(integerIntegerRedBlackTree.remove(1));
System.out.println(integerIntegerRedBlackTree.remove(1));
System.out.println("minkey=====>" + integerIntegerRedBlackTree.minKey());
System.out.println("get 2=====>" + integerIntegerRedBlackTree.get(2));
System.out.println(integerIntegerRedBlackTree.remove(2));
System.out.println("get 2=====>" + integerIntegerRedBlackTree.get(2));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
3.3 执行流程
3.3.1 插入
针对上面的测试案例详细说明执行流程！我对需要对下面一批数据构建红黑树！
(3, 47);
(2, 16);
(1, 73);
(4, 1);
(5, 24);
(6, 59);
(7, 59);
(16, 59);
(15, 59);
(14, 59);
(13, 59);
(12, 59);
(11, 59);
(10, 59);
(8, 59);
(9, 59);
首先建立红黑树类对象。注意：在我们的实现原理的讲解过程中，null节点使用一个特殊哨兵节点NIL来代替，那样方便理解，而在具体的实现代码中，并没有NIL哨兵节点，对于null节点，我们知道他作为黑色节点并且注意不要造成空指针异常即可，还能节省空间。
使用无参构造器，新建红黑树类之后，此时该类的结构为：
可以看到，自定义比较器为null，说明会使用自然比较器比较；
节点数量size为0；
根节点引用指向null，说明还没有节点。
3.3.1.1 插入3
首先插入(3, 47)，默认创建红色节点，插入之后，判断该节点明显是根节点，那么该节点涂黑：
3.3.1.2 插入2
然后插入(2, 16)，默认创建红色节点，插入之后符合红黑树的规定义，不用调整平衡；
3.3.1.3 插入1
然后插入(1, 73)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔黑（null算黑色）-LL”的情况，按照LL的要求来进行调整：将G右旋，然后P涂黑，G涂红。
3.3.1.4 插入4
然后插入(4, 1)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
3.3.1.5 插入5
然后插入(5, 24)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔黑（null算黑色）-RR”的情况，按照要求来进行调整：将G左旋，然后P涂黑，G涂红。
3.3.1.6 插入6
然后插入(6, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
3.3.1.7 插入7
然后插入(7, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔黑（null算黑色）-RR”的情况，按照要求来进行调整：将G左旋，然后P涂黑，G涂红。
3.3.1.8 插入16
然后插入(16, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
上图可以看到，一次调整之后，成为了“父红叔黑-RR”的情况，按照要求来进行调整：将G左旋，然后P涂黑，G涂红。
3.3.1.9 插入15
然后插入(15, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔黑（null算黑色）-RL”的情况，按照要求来进行调整：先将P右旋，然后将G左旋；然后N涂黑，G涂红。
P右旋：
G左旋：
N涂黑，G涂红：
3.3.1.10 插入14
然后插入(14, 11)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
递归之后，这里明显又是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
之后发现N属于节点，此时只需要将N涂黑即可：
3.3.1.11 插入13
然后插入(13, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔黑（null算黑色）-RL”的情况，按照要求来进行调整：先将P右旋，然后将G左旋；然后N涂黑，G涂红。
P右旋：
G左旋：
N涂黑，G涂红：
3.3.1.12 插入12
然后插入(12, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
递归之后，这里明显属于“父红叔黑-RL”的情况，按照要求来进行调整：先将P右旋，然后将G左旋；然后N涂黑，G涂红。
P右旋：
G左旋：
N涂黑，G涂红：
3.3.1.13 插入11
然后插入(11, 12)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔黑（null算黑色）-RL”的情况，按照要求来进行调整：先将P右旋，然后将G左旋；然后N涂黑，G涂红。
P右旋：
G左旋:
N涂黑，G涂红：
3.3.1.14 插入10
然后插入(10, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
第一次递归时，还是属于“父红叔红”，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
13作为红色“插入”之后，这次就很幸运了，父节点为黑色，不需要调整了，平衡完成。
3.3.1.15 插入8
然后插入(8, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔黑（null算黑色）-RL”的情况，按照要求来进行调整：先将P右旋，然后将G左旋；然后N涂黑，G涂红。
P右旋：
G左旋：
N涂黑，G涂红：
3.3.1.16 插入9
然后插入(9, 59)，默认创建红色节点，插入之后违反了红黑树的定义4，即不能有相连的红色节点。
这里明显是属于“父红叔红”的情况，按照要求来进行调整：将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。
第一次递归时，是属于 “父红叔黑-RL”的情况，按照要求来进行调整：先将P右旋，然后将G左旋；然后N涂黑，G涂红。
P右旋：
G左旋：
N涂黑，G涂红：
到此，插入完毕！
3.3.2 删除
删除操作在代码中共分为三步，首先searchRemoveNode寻找真正应该被删除的节点，然后removeNode对该节点进行删除，并且调整部分情况下的节点的平衡，对于复杂的节点的平衡，比如涉及到递归操作的，我们在最后单独的rebalanceAfterRemove方法中处理！
3.3.2.1 删除2
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于2具有左右子树，因此寻找右子树的最小值，很快找到了3，它是右子树的最小节点，这就是真正需要被删除的节点，然后对2节点和3节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为null（null节点看成黑色节点），简称“删黑子黑”；
然后继续划分，被删除节点的兄弟节点1为黑色，并且属于“兄子全黑（null算黑色）-父黑”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
最后调用rebalanceAfterRemove方法进行平衡，使用“兄子全黑-父黑”的调整方法：将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
第一次递归时，明显是“删黑子黑-删兄红-右兄弟”的情况，使用对应的删除方法：以父节点P为基点左旋，然后B涂黑、P涂红，最后将BL看成新的兄弟节点newB，转换为“删兄黑”的情况！
以父节点P为基点左旋：
B涂黑、P涂红，最后将BL看成新的兄弟节点newB，转换为“删兄黑”的情况！
转换之后，根据上图可以知道，具体是属于“删兄黑-兄子非全黑-兄右，右子红”的情况，使用对应的删除方法：以父节点P为基点左旋，然后交换P和B的颜色，BR涂黑，平衡完毕！
以父节点P为基点左旋：
交换P和B的颜色，BR涂黑，平衡完毕！
3.3.2.2 删除4
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于4具有左右子树，因此寻找右子树的最小值，很快找到了5，它是右子树的最小节点，这就是真正需要被删除的节点，然后对4节点和5节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为黑色，简称“删黑子黑”；
然后继续划分，被删除节点4的兄弟节点7黑色，并且属于“删兄黑-兄子全黑-父红”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
对于“兄子全黑-父红”的情况，使用对应的调整方法：将兄弟节点B涂红，父节点P涂黑即可。此时原本删除黑色节点的路径补充了黑色节点，即可达到平衡。
此时因为删除4而损失的黑色节点通过父节点6变黑补充回来了，同时兄弟节点路径中的黑色节的数量点因为7节点的变红也没变。
3.3.2.3 删除5
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于5具有左右子树，因此寻找右子树的最小值，很快找到了6，它是右子树的最小节点，这就是真正需要被删除的节点，然后对5节点和6节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的右子节点为红色，简称**“删黑子红**”；
对于这种简单的情况，在removeNode方法中已经处理了，使用“删黑子红”的调整方法：删除5之后，把后继C的颜色涂黑，即将失去的黑色补充回来，即可达到平衡！
3.3.2.4 删除12
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于12没有左右子树，因此12就是真正需要被删除的节点，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为null（null节点看成黑色节点），简称“删黑子黑”。
然后继续划分，被删除节点12的兄弟节点10为黑色，并且属于“兄子非全黑-兄左，左子红”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“兄子非全黑-兄左，左子红”的调整方法：以父节点P为基点右旋，然后交换P和B的颜色，BL涂黑，平衡完毕！
以父节点P为基点右旋：
交换P和B的颜色，BL涂黑，平衡完毕！
3.3.2.5 删除7
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于7没有左右子树，因此7就是真正需要被删除的节点，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为null（null节点看成黑色节点），简称“删黑子黑”；
然后继续划分，被删除节点12的兄弟节点10为黑色，并且属于“兄子非全黑-兄左，左子红”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“兄子非全黑-兄左，左子红”的调整方法：以父节点P为基点右旋，然后交换P和B的颜色，BL涂黑，平衡完毕！
以父节点P为基点右旋：
交换P和B的颜色，BL涂黑，平衡完毕！
3.3.2.6 删除13
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于13具有左右子树，因此寻找右子树的最小值，很快找到了14，它是右子树的最小节点，这就是真正需要被删除的节点，然后对13节点和14节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为null（null节点看成黑色节点），简称“删黑子黑”；
然后继续划分，被删除节点的兄弟节点16为黑色，并且属于“兄子全黑（null算黑色）-父黑”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“兄子全黑-父黑”的调整方法：将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
继续使用“删兄红-左兄弟”的调整方法：以父节点P为基点右旋，然后B涂黑、P涂红，最后将BR看成新的兄弟节点newB，即变成“删兄黑”的情况。
以父节点P为基点右旋：
B涂黑、P涂红，最后将BR看成新的兄弟节点newB，即变成“删兄黑”的情况。
从图上可以看出来，这是属于“删兄黑-兄子全黑-父红”的情况，使用对应的调整方法：将兄弟节点B涂红，父节点P涂黑即可达到平衡。
3.3.2.7 删除8
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于8具有左右子树，因此寻找右子树的最小值，很快找到了9，它是右子树的最小节点，这就是真正需要被删除的节点，然后对8节点和9节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为null（null节点看成黑色节点），简称“删黑子黑”；
然后继续划分，被删除节点的兄弟节点11为黑色，并且属于“兄子全黑（null算黑色）-父红”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“兄子全黑（null算黑色）-父红”的调整方法：将兄弟节点B涂红，父节点P涂黑即可达到平衡！
3.3.2.8 删除16
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于16没有左右子树，因此16就是真正需要被删除的节点，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是红色节点，这是最简单的删除了，简称“删红”；删除N后不会影响红黑树的平衡性，与其他节点的颜色无关，因此不需要做任何调整。
对于这种简单情况，在removeNode中已经处理好了。
3.3.2.9 删除11
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于11没有左右子树，因此11就是真正需要被删除的节点，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是红色节点，这是最简单的删除了，简称“删红”；删除N后不会影响红黑树的平衡性，与其他节点的颜色无关，因此不需要做任何调整。
对于这种简单情况，在removeNode中已经处理好了。
3.3.2.10 删除10
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于10没有左右子树，因此10就是真正需要被删除的节点，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为黑色，简称“删黑子黑”；
然后继续划分，被删除节点10的兄弟节点15黑色，并且属于“删兄黑-兄子全黑-父黑”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“删兄黑-兄子全黑-父黑”的情况的调整方法：将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
继续，使用“删兄黑-兄子全黑-父黑”的情况的调整方法：将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
3.3.2.11 删除14
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于14没有左右子树，因此14就是真正需要被删除的节点，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为红色，简称“删黑子红”；
对于这种简单的情况，在removeNode中已经处理了：把子节点C的颜色涂黑，那么就能恢复N之前所在路径的黑色节点的总数，与其他节点的颜色无关，平衡调整完成。
3.3.2.12 删除3
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于3具有左右子树，因此寻找右子树的最小值，很快找到了6，它是右子树的最小节点，这就是真正需要被删除的节点，然后对3节点和6节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为黑色，简称“删黑子黑”；
然后继续划分，被删除节点3的兄弟节点1为黑色，并且属于“删兄黑-兄子全黑-父红”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“删兄黑-兄子全黑-父红”相应的调整方法：将兄弟节点B涂红，父节点P涂黑即可达到平衡。
3.3.2.13 删除9
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于9具有左右子树，因此寻找右子树的最小值，很快找到了15，它是右子树的最小节点，这就是真正需要被删除的节点，然后对9节点和15节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为黑色（null），简称“删黑子黑”；
然后继续划分，被删除节点9的兄弟节点6黑色，并且属于“删兄黑-兄子非全黑-兄左，左子红”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“删兄黑-兄子非全黑-兄左，左子红”的调整方法：以父节点P为基点右旋，然后交换P和B的颜色，BL涂黑，平衡完毕！
3.3.2.14 删除6
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于6具有左右子树，因此寻找右子树的最小值，很快找到了15，它是右子树的最小节点，这就是真正需要被删除的节点，然后对6节点和15节点交换key和vaue的值，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为黑色（null），简称“删黑子黑”；
然后继续划分，被删除节点6的兄弟节点1黑色，并且属于“删兄黑-兄子全黑-父黑”的情况！
对于这种复杂情况，在removeNode中没有处理，删除该节点，并且改变引用，然后然后返回原来被删除的节点，然后继续进行复杂的平衡操作。
使用“删兄黑-兄子全黑-父黑”的调整方法：将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
3.3.2.15 删除15
首先searchRemoveNode根据二叉排序树的删除原理查找需要真正被删除的节点，由于15没有左右子树，因此15就是真正需要被删除的节点，返回该需要被删除的节点！
然后调用removeNode对该节点进行删除，同时对部分情况进行调整平衡！这里被删除的节点是黑色节点，它的子节点为红色，简称“删黑子红”；
对于这种简单的情况，在removeNode中已经处理了：把子节点C的颜色涂黑，那么就能恢复N之前所在路径的黑色节点的总数，与其他节点的颜色无关，平衡调整完成。
3.3.2.16 删除1
很明显，这里属于“删黑子黑-删根”的情况，直接删除该节点，任何无需平衡操作。此时所有元素已经全部删除完毕！红黑树对象又回到了初始的状态：
4 总结
红黑树具有非常复杂的原理、超高的实现难度、以及良好的使用性能。如果理解了红黑树，那么对其他高级的数据结构的理解比如伸展树、Treap、跳跃表、k-d 树 等应该是比较简单的事。
从上面的实现可以看出来，红黑树的实现结构不唯一。比如删除的时候，上面的实现是查找右子树的最小节点，也可以是查找左子树的最大节点，这样红黑树的结构会有所改变。
最后提供一个在线演示各种数据结构的网站：Data Structure Visualizations，做的非常不错。
相关参考：
- 《算法》
- 《数据结构与算法分析 Java语言描述 原书第3版 》
- 百度百科
如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！
