红黑树

B树

n阶B树的性质：

1. 1<= 根结点元素数量 <= n-1

2. ceil(n/2)-1 <= 非根结点元素数量 <= n-1

3. A节点的子节点个数 = A结点内元素数量+1（A为任意节点）

由3得出：

1. 2 <= 根节点的子节点个数 <= n

2. ceil(n/2) <= 非根节点的子节点个数 <= n

所以为了一目了然，一般3阶B树也叫（2，3）树，4阶B树也叫（2，4）树，5阶B树也叫（3，5）树。其中的数字代表子节点数量范围。

B树添加元素：

找到添加元素的叶子节点，直接添加。添加元素可能导致上溢。

上溢：当A节点数量 == n-1，触发上溢。将中间元素与父节点合并，并将A节点拆为两个节点。上溢可能导致B树高度增加。

下面三张图片展示了5阶B树循环上溢的过程：

B树删除元素：

若删除元素位于叶子节点，直接删除。若为非叶子节点，找到该元素的前驱或后继元素，覆盖所需删除的元素，然后将前驱或后继元素删除。

两种删除元素情况都可能会导致下溢。

前驱：该元素的左节点的循环最右元素，必定在叶子节点。

后继：该元素的右节点的循环最左元素，必定在叶子节点。

下溢：当非根节点的元素数量 == ceil(n/2)-2，或根节点的元素数量 == 0，触发下溢。

下溢首先判断能否向临近的兄弟节点借元素。若临近的兄弟节点元素数量 >= ceil(n/2)，代表可借，则触发旋转。

下图展示了旋转的过程，其中m代表几阶B树。

如果临近的兄弟节点元素数量 == ceil(n/2) - 1，代表没有元素可借，则触发合并。

下图展示合并的过程。

红黑树

红黑树中，若某个节点没有左或右节点，会默认认为其左或右节点为外部节点（空节点），如下图：

红黑树性质：

1. 节点是RED或者BLACK

2. 根节点是BLACK

3. 叶子节点（外部节点，空节点）都是 BLACK

4. RED节点的子节点都是BLACK

5. 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

这5条性质中，其中1，2，3都很容易实现，重点关注4和5性质。

红黑树可以看做与4阶B树等价，如下图，若以红黑树中每个黑色节点作为B树中的节点，并将子节点中的红色节点合并，可得到等价的4阶B树。

红黑树添加节点：

以B树展示，合并后的节点分四种情况：分别是红黑红，黑红，红黑，黑，如下图：

那么添加元素的位置有12种情况，分别是：

17的左节点，17的右节点；33的左节点，33的右节点；46的左节点；50的左节点，50的右节点；72的左节点，72的右节点；76的右节点；88的左节点，88的右节点。

默认新增节点都是RED，这样满足性质5。然后我们将12种情况分为3类：

1. 父节点为BLACK（对应上面4种情况）

直接添加即可，同时满足性质4与5。

2. 父节点为RED，叔父节点为BLACK或nil（对应上面4种情况）

如下图添加52和60，触发旋转（左旋或右旋），然后将父节点染BLACK，兄弟节点染红，这样的到的红黑树则同时满足性质4与5。

旋转染色前 旋转染色后

3. 父节点为RED，叔父节点为RED（对应上面4种情况）

比如添加节点10：

先将父节点17和叔父节点33染黑，祖父节点25染红。祖父节点因为染RED上溢（因为对应B树节点一定为黑色）。得到下图，不考虑上溢的祖父节点25，其它节点此时性质4，5满足。

上溢的祖父节点25等同于添加一个新元素到B树（38，55）节点中。递归调用添加新节点，将25作为新节点进行1-3条件判断。

若最终添加的元素溢到了根节点，则强制改成黑色。

红黑树删除节点：

像上图，若删除节点为对应B树的非叶子节点，38，55，80。则和B树一样处理，找到该节点的前驱或后继节点，覆盖所需删除的节点，然后将前驱或后继节点删除（删除步骤与下面相同）。

若删除节点为对应B树的叶子节点，则删除分为11种情况，分别是：

38，55，80，17，25，33，46，50，72，76，88。

以下为伪代码：

if  若删除节点存在子节点（6种情况），则找到该节点的前驱或后继节点，覆盖所需删除的节点，然后将前驱或后继节点删除（这里可能触发递归）。

比如删除38，找到后继46，代替38的位置；然后删除46，46找到后继50，代替46的位置，删除旧的50。

else if 删除节点为RED（4种情况），则直接删除。

else {

 // 删除节点没有子节点（一种情况，88），且为BLACK

// 因为删除节点为BLACK，所以会导致性质5不满足。

进入递归函数 删除并借节点

}

删除并借节点：

先看兄弟节点是否存在子节点（子节点必为RED），存在的话说明可以借节点，则将整体旋转进行借节点。

若兄弟节点没有子节点，则代表不可借节点：

若父节点80为RED，将父节点染BLACK，兄弟节点染RED，满足性质5；若父节点80为BLACK，则不满足性质5，将父节点染BLACK，兄弟节点染RED，然后对父节点80进行递归函数 删除并借节点。