目录

2-3-4树与红黑树

基本介绍

2-3-4树就是阶为4的B树。根据离散数学的图论相关知识,可以证明2-3-4树和红黑树是等价的。对于m阶(m指的结点的最大分支数)B树,其结点的值的个数n:1<=n<m。因此,对于2-3-4树,其结点的值的个数1<=n<4,如下图所示 https://gitee.com/lienhui68/picStore/raw/master/null/20200630152212.png

2-3-4树与红黑树的等价性

  1. 将红黑树中的红色节点放平: https://gitee.com/lienhui68/picStore/raw/master/null/20200630152504.png
  2. 将红结点合并到与其在同一层、并直接相连的黑结点: https://gitee.com/lienhui68/picStore/raw/master/null/20200630152612.png 通过上面过程可看出任何红黑树可以转化为2-3-4树。将2-3-4树转化为红黑树就是上述过程逆向一下即可。

从2-3-4树看红黑树的旋转变色

由于插入操作可能会破坏红黑树的平衡性,因此我们在插入值后需要对红黑树进行调整,这个调整过程就是红黑树结点的颜色变换和旋转操作,这些操作都可以从2-3-4树的角度来理解。 假设我们在上图的2-3-4树中插入17,则: https://gitee.com/lienhui68/picStore/raw/master/null/20200630153034.png 将其转化为红黑树: https://gitee.com/lienhui68/picStore/raw/master/null/20200630153100.png

插入完毕,相比直接在原红黑树进行旋转变色,以2-3-4树的方式更容易简单理解。插入17后的红黑树其实是在原红黑树基础上旋转、变色得到的。

参考

经典搜索算法之2-3-4树与红黑树