当我们将新插入的节点的父节点node30染成红色时, 再插入到根节点, 实际上就是重复我们枚举出来的这12种情况中的一种. 红黑树一定会被修复, 当然这时候很可能会出现根节点也容纳不了新的元素, 需要根节点也进行上溢, 然后将根节点染黑
还有一种情况是像下面这样, 同样是在情况4下的新插入的节点的叔叔节点是红色
像下面这样调整:
将父节点和叔叔节点染成黑色
祖父节点上溢
然后就是这种情况
调整的思路和前面一样
将父节点和叔叔节点染成黑色
将祖父节点上溢
至此红黑树的添加的12种情况就全部枚举完成了
删除对于删除来说总共两大种四小种情况
第一种就是删除的节点就是红色节点, 如果真是这样的话,直接删除就ok
第二种是删除的节点是黑色节点
删除拥有1个red节点的黑色节点
删除拥有2个red节点的黑色节点,
删除黑色节点
如果一个像下面这样, 下面的黑色节点有两个子节点, 这种情况下,黑色节点肯定不会直接被删除的, 需要进行变换,让他的叶子节点去替换他,进而实现删除的目的
情况1: 删除拥有1个红节点的黑色节点,像下图这样
怎么判断这就是我们想删除的情况呢? 当我们确定用来替代这个被删除的黑节点是红色,则符合当前的情况
也就是说我们想删除 node40 和 node70, 于是我们这样做
让这个指向被删除的节点的指针指向这个被删除的节点的子节点
将替代它的节点染成黑色
于是我们接得到下图这样的结果
情况2: 删除的节点是黑色的叶子节点, 并且可向兄弟节点借
首先,如果这个叶子节点就是根节点的话,直接删除就ok
看下面的这个图, 我们就删除其中node90， 即，删除黑色叶子节点
如果想删除上图中的node90也是由窍门的，规律和2-3-4树是擦不多的
假设它就是2-3-4树， 如果我们将node90删了， 我们计算一下， 对于2-3-4树来说， 每一个节点位置上至少有 ⌈ 4/2 ⌉ -1 = 1个元素， 但是把node90删除了这个位置上的节点中没有元素， 因此产生了 下溢
出现下溢，我们首先考虑的情况就是看看可不可以向它的兄弟节点借一个，但是和B树是有取别的， 多了下面的限制
被删除的这个节点的兄弟节点必须是黑色的
被删除的这个节点的兄弟节点一定的有红色的子节点才ok， 就像上图那样， 可以在左边，右边，或者都有
直接删除掉指定的node（因为它在叶子节点的位置上）
进行旋转，旋转时注意， 两点：第一点： 比如下面的原来根节点位置上的元素88是红色的， 经过旋转上来替换它的节点的颜色必须染成红色， 如果node88是黑色， 那么经过旋转上来替换他的节点的颜色必须染成黑色 ，第二点： 旋转完成后，新的跟节点的直接左右子节点的颜色转换为黑色
怎么进行旋转呢？ 就像下图这样
情况3: 删除的节点是黑色的叶子节点, 并且它的兄弟是黑色，而且它的兄弟节点不能借给他元素
像这种情况：我像删除node99，但是没办法像他的兄弟节点借元素，于是
将父节点向下合并,父节点染成黑色
将它的兄弟节点染成红色