从B 树理解红黑树

作者: 快点给我想个名 | 来源:发表于2020-02-14 21:34 被阅读0次

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。从而会出现下面两条性质

根节点子节点的个数 y = 2≤ x ≤ m
非根节点子节点的个数 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树

红黑树和4阶B树（2-3-4树）具有等价性
BLACK 节点与它的RED子节点融合在一起，形成1个B树节点
红黑树的BLACK节点个数与4阶B树的节点总个数相等
综上所述红黑树节点转换成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
        当兄弟节点为黑色且至少包含一个红色节点时，我们可以借用一个节点。但是现在这种情况，我们也借一个节点，但是借过来的是黑色节点。这时候整体操作如下：兄弟节点染黑，父节点染红，父节点右旋，此时就是借兄弟节点的子节点过来变成兄弟节点，然后回到了兄弟节点是黑节点的情况。