查找树-- 2-3-4树原理图解及与红黑树的关系_红黑树比2-3-4树好在哪

2-3-4 树

概念

2-3-4 树 是一棵4阶的B树。
大体上同B树一样，2-3-4 树是可以用做字典的一种自平衡数据结构。
它可以在O（logⁿ）时间内查找、插入和删除，这里的n是树中元素的数目。

2-3-4树和红黑树是完全等价的，且性能上并不比红黑树好，由于绝大多数编程语言直接实现2-3-4树会非常繁琐，所以一般是通过实现红黑树来实现替代2-3-4树，而红黑树本也同样保证在O(lgn)的时间内完成查找、插入和删除操作。

主要性质

• 所有叶子节点都拥有相同的深度。
• 节点只能是 2-节点、3-节点、4-节点之一。
  • 2-节点：包含 1 个元素的节点，有 2 个子节点；
  • 3-节点：包含 2 个元素的节点，有 3 个子节点；
  • 4-节点：包含 3 个元素的节点，有 4 个子节点；
• 元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点；而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。

2-3-4树示例如下：

树的操作

2-3-4树的操作请参见：234树到红黑树，本文的演示图是基于此文的图片整合而来。

插入

• 步骤1 按二分法查找插入key的位置
  • 如果插入的key在树中已经存在，则更新此key的值
  • 如果不存在，则最终一定是在叶子节点中进行插入操作
• 步骤2 如果待插入的节点不是4节点，那么直接插入
• 步骤3 如果待插入的节点是个4节点，那么先分裂这个4节点然后再插入。
  • 一个4节点可以分裂成一个根节点和两个子节点（这三个节点各含一个key）
  • 然后在子节点中插入
  • 把分裂形成的根节点中的key看成向上层插入的key，然后重复步骤2-3。
    

删除

2-3-4树的删除比较复杂，示例如下：

2-3-4树与红黑树的关系

与红黑树的关系

2-3-4树与红黑树是多叉树与二叉树的关系，2-3-4树和红黑树是完全等价的！
看上去完全不同，但是在某种意义上它们又是完全相同的
一个可以通过应用一些简单的规则变成另一个，而且使他们保持平衡的操作也是一样，数学上称他们为同构。

应用如下三条规则可以将2-3-4树转化为红黑树：

• 把2-3-4树中的每个2-节点转化为红黑树的黑色节点。
• 把每个3-节点转化为一个子节点和一个父节点，子节点有两个自己的子节点：W和X或X和Y。父节点有另一个子节点：Y或W。哪个节点变成子节点或父节点都无所谓。子节点涂成红色，父节点涂成黑色。
• 把每个4-节点转化为一个父节点和两个子节点。第一个子节点有它自己的子节点W和X；第二个子节点拥有子节点Y和Z。和 前面一样，子节点涂成红色，父节点涂成黑色。

转化为需要进行树的平衡操作。

图解如下：

性能对比

红黑树的层数大约是log₂^(N+1)，而2-3-4树每个节点可以最多有4个数据项，如果节点都是满的，那么高度为log₄^N。因此在所有节点都满的情况下，2-3-4树的高度大致是红黑树的一半。

实际情况是节点不可能都是满的，所以2-3-4树的高度是：log₂^(N+1) ~ log₂^(N+1)/2。减少2-3-4树的高度可以使它的查找时间比红黑树的短一些。

但是每个节点要要比较的元素变多，这会增加查找时间。因为节点中用线性搜索来查找比较数据项，使得查找时间的倍数和M成正比，即每个节点数据项的平均数量，总的查找时间和M*log₄^N成正比。