数一数: 一共 4+3+3+2 = 12种情况, 换句话说, 只要我们处理好了这12种情况, 我们就完成了添加节点的逻辑
情况1, 就是假设我们添加进去的是红色的节点, 并且这个红色节点的父节点是黑色节点时, 直接添加进行,不需要其他任何变换, 就想下图这样, 直接简单粗暴的添加就行
除去第一种情况外, 还剩下8中情况出现了红红节点相邻, 于是继续往下看, 我们对他进行一次修复
情况2: 如下图
插入的node57, node64, 什么情况呢? 就是当前节点是node5556, 首先这个节点中现存两个元素, 并且是往这个黑色的节点的左侧的左侧插入, 或者是右侧的右侧插入一个红色节点
看上图出现了两个红色节点相邻,于是我们第一件事就是进行重新染色,
将插入节点的父节点染成黑色
将插入节点的祖父节点染成红色
将祖父节点进行旋转, 如果这个新节点被插入在父节点的右侧. 左旋转它的祖父节点
经过上面的变换后, 我们重新得到标准的红黑树如下
情况3: 新添加的节点的叔叔节点不是红色
第三种情况和第二种情况相似, 还是插入 node57和node64. 判断的条件是 插入节点的叔叔节点(父节点的兄弟节点)不是红节点,
简称 LR , 或者是RL , 需要进行如下的调整
染色: 将自己染成黑色,祖节点染成红色
LR: 父节点左旋转, 祖父节点右旋转
RL: 祖父点右旋转, 父节点左旋转
LR举例:
经过上面的变化,我们重新得到平衡的红黑树
接着往下看剩下的四种情况
情况4: 新添加的节点的叔叔节点是红色, 其实就是需要上溢的情况, 也很好处理
像上图这样, 新添加的红色节点 node15, 它本身的父节点是node20, 父节点的叔叔节点是红色的node25, 我们比较node15和node20的大小, 发现node15本来是应该放在node20的左边的, 但是对于一颗2-3-4树来说, 单个节点最多就有3个元素, 如果再加上node15 就会出现上溢的情况, 怎么办呢? 我们上溢调整, 选择这个节点中间位置的元素向上和父节点合并, 选择node20, node30其实都是可以的, 为了方便我们选择node30
好,下面开始修复这个红黑树
将插入的节点的父节点和它的叔叔节点染成黑色
发生了上溢, 将他的父节点的染成红色, 递归插入到根节点上, 这时候根节点可能又会发生上溢
然后上溢