从B 树理解红黑树

B树

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现。
“阶”是指一个节点包含的最多子节点的个数。
m阶B树的性质（m≥2），这里假设一个节点存储的元素个数为x。
注意区分是说的节点还是说节点中存储的元素。

• 根节点存储元素个数： 1≤ x ≤ m-1，因此3阶B树根节点存储的元素个数为1个或者2个。
• 非根节点存储元素个数：⌈m/2⌉ - 1 ≤ x ≤ m-1 (注：⌈m/2⌉为向上取整)，为什么是⌈m/2⌉ -1 呢，因为假设m阶的B树某个节点存储的元素个数达到m个后，就需要分裂。首先将包含m个节点的元素分裂成差值不超过1的两个阶段，之后在从多的那个(如果相同就从任一)节点中拿出一个，作为这两个节点的父节点。
• 如果某节点有子节点，则子节点的个数y = x + 1，也就是当前节点包含元素个数+1。从而会出现下面两条性质

1. 根节点子节点的个数 y = 2≤ x ≤ m
2. 非根节点子节点的个数 y = ⌈m/2⌉ ≤ x ≤ m

B树的添加过程

下图展示一个3阶B树插入1至12的过程，3阶B树其实也就是2-3树。

3阶B树添加过程

• 新添加的元素必定是添加到叶子节点
• 添加元素个数超过节点允许保存的个数就会发生上溢

B树的查找过程

比如查找元素7

3阶B树查找元素

B树的删除过程

比如删除节点8

3阶B树删除元素

• 如果删除的节点是叶子节点则直接删除
• 如果删除的节点是非叶子节点
  1. 先找到前驱或者后继元素，覆盖所需要删除元素的值
  2. 再把前驱或者后继元素删除
  3. 但是如图所示，删除后，节点保存元素的个数变成0，不符合⌈m/2⌉ - 1 ≤ x ≤ m-1，出现下溢。
• 出现下溢后的解决办法

  1. 如果兄弟节点的元素个数≥⌈m/2⌉个，则向其借用一个元素。并将父节点的元素插入到下溢节点的0位置(最小位置)

     
     4阶B树模拟下溢

  2. 如果兄弟节点的元素个数正好为⌈m/2⌉ - 1个，那只能合并，但是合并后有可能导致父节点下溢，则需要按照上述方法解决

     
     4阶B树模拟下溢

红黑树

红黑树的性质

1、节点都是RED或BLACK
2、根节点是BLACK
3、叶子节点都是BLACK (叶子节点这里是指假想出来的null节点)
4、RED节点的子节点都是BLACK
5、从任一节点到叶子节点的宿友路径都包含相同数目的BLACK 节点
由于性质的约束：插入点不能为黑节点，应插入红节点，这样只会破坏性质4

红黑树和4阶B树

1. 红黑树和4阶B树（2-3-4树）具有等价性
2. BLACK 节点与它的RED子节点融合在一起，形成1个B树节点
3. 红黑树的BLACK节点个数与4阶B树的节点总个数相等
4. 综上所述红黑树节点转换成4阶B树后，节点之间的组合关系存在如下四种情况：
   • 红黑红
   • 黑红
   • 红黑
   • 黑

红黑树与4阶B树的等价转换

红黑树添加

• 如果是空树
  添加节点为根节点，染成 BLACK即可。
• 如果不是空树
  根据红黑树节点转换成4阶B树后，节点之间的组合关系，会出现如图所示的12种情况。
  非空红黑树添加节点情况.png
  • 情况一添加节点的父节点为BLACK(占12种情况种的4种)
    不需要处理，添加就好。比如：添加节点的父节点为上图中的46、76、88
  • 情况二添加节点的叔叔节点非RED(占12种情况中的4种，叔叔节点没有或者为黑色，比如：父节点为50、72)

    • 情况二中的第一种(添加节点所在位置同父节点相对祖父节点的位置，如50的左边添加、72的右边添加)
      

      新插入节点位置与父节点位置相同
      当添加完节点后，你会发现50、72节点的组合变成了黑红红、红红黑，不符合上面我们总结的情况。所以这个时候要将父节点(50、72)变为黑色，祖父节点(46、72)变为红色，最终变成红黑红的组合。但是变成红黑红的组合后，38的子节点46就是红色的，不符合性质4，所以这里还缺一步操作，就是将38指向变黑的父节点50(也就是对祖父节点进行左旋或右旋)。

    • 情况二中的第二种(添加节点所在位置相反于父节点相对祖父节点的位置，如果50的右边添加、72的左边添加)
      

      新插入节点位置与父节点位置相反
      当添加完节点后，你会发现50、72节点的组合变成了黑红红、红红黑，不符合上面我们总结的情况。所以这个时候对父节点进行旋转，新节点变成父节点，变成上面的情况二中的第一种。
  • 情况三添加节点的叔叔节点为RED(占12种情况中的4种，比如：父节点为17、33)

    • 情况三中的第一种(添加节点所在位置同父节点相对祖父节点的位置，如17的左边添加、33的右边添加)
      

      新插入节点位置与父节点位置相同并且叔叔节点为红色
      如果在17的左边添加或33的右边添加节点后，将导致对等的4阶树发生上溢现象。我们可以将25进行左右分裂。分裂后形成两个新的组合。但是新的组合中要有黑节点，所以我们需要将新插入节点的父节点、叔叔节点变成黑色。然后将祖父节点25染成红色，作为新节点，插入到上层中，继续按情况处理就行了。

    • 情况三中的第二种(添加节点所在位置相反于父节点相对祖父节点的位置，如17的左边添加、33的右边添加)
      如果在17的右边添加或33的左边添加节点后，将导致对等的4阶树发生上溢现象。我们可以将25进行左右分裂。分裂后形成两个新的组合。但是新的组合中要有黑节点，所以我们需要将新插入节点的父节点、叔叔节点变成黑色。然后将祖父节点25染成红色，作为新节点，插入到上层中，继续按情况处理就行了。
      

      新插入节点位置相反于父节点位置并且叔叔节点为红色

红黑树删除

切记B树中的删除，最后都是删除叶子节点。
由于红黑树和4阶B树转换后，至存在四种情况。所以删除也就在这四种情况当中。

• 如果只有一个节点
  删除即可，没啥说的。
• 如果不止一个节点
  根据红黑树节点转换成4阶B树后，节点之间的组合关系，会出现如图所示的8种情况。
  非空红黑树删除节点情况
  • 情况一删除节点为红色节点(占8种情况中的4种)
    不需处理，直接删除。比如：删除上图中的17、33、50、72
  • 情况二删除节点为黑色节点(占8种情况中的4种)
    • 情况二中的第一种(拥有两个红色子节点的节点，如图中25节点)
      这种情况不存在，因为找的是替代节点，这个节点还存在替代节点，删除的还是红色节点。
    • 情况二中的第二种(拥有一个红色子节点的节点，如图中46、76节点)
      用红色子节点替代黑色节点并染黑
    • 情况二中的第三种(没有子节点)
      替代节点不存在，这个时候删除节点就会出现下溢现象。
      • 情况二中的第三种的第一种(兄弟节点为黑色可以借一个红节点，也就是兄弟节点至少包含一个红节点)
        兄弟节点可以借一个节点
        此时需要进行旋转，借用的节点替换到父节点并修改为父节点颜色，父节点下来替换掉带删除节点并修改颜色。
        兄弟节点可以借一个节点后的
        • 情况二中的第三种的第二种(兄弟节点为黑色不能借一个红节点，也就是兄弟节点不包含红节点)
          兄弟节点不能借一个红节点.png
          此时需要父节点下来，和兄弟节点合并，兄弟节点变为红色，父节点变为黑色。注意这种情况可能会导致父节点之前所在的组合出现下溢现象。再根据具体情况，具体分析。
        • 情况二中的第三种的第三种(兄弟节点为红节点)
          兄弟节点为红色.png
          当兄弟节点为黑色且至少包含一个红色节点时，我们可以借用一个节点。但是现在这种情况，我们也借一个节点，但是借过来的是黑色节点。这时候整体操作如下：兄弟节点染黑，父节点染红，父节点右旋，此时就是借兄弟节点的子节点过来变成兄弟节点，然后回到了兄弟节点是黑节点的情况。