2-3-4树的分析
2-3-4树在大部分资料中都简单带过，也很少会去实现。但是对于理解红黑树和B树来说，2-3-4树有非常重要的作用。
我被红黑树的算法折磨了几天，终于转到2-3-4树的学习，才搞明白了红黑树的来由。虽然一般2-3-4树不必实现，但是了解其原理还是很重要的。
2-3-4树是阶为4的B树，同时2-3-4树与红黑树等效。
2-3-4树的名称意味着树的每个节点带着2，3或4个孩子节点。
-
2节点有1个数据元素，有2个子节点
-
3节点有2个数据元素，有3个子节点
-
4节点有3个数据元素，有4个子节点
2-3-4树的特性
-
每个节点（叶节点或内部节点）是2节点，3节点或4节点。
-
所有叶子节点的深度相同。
-
数据始终保持排序顺序
插入操作
插入节点时，从2-3-4树的根节点开始执行以下操作
-
如果当前节点是4度节点:
- 如果当前节点是根节点，则中间的值被设置为新的根节点，该根节点是2度节点，树的高度增加1
- 否则，将中间值加入父节点中
- 将当前节点左右两边的值分裂成2个2度节点
-
查找子节点可以包含被插入值的区间
-
如果找到一个节点是叶子节点，则将被插入值放入该节点中，插入操作结束
- 否则，继续查找 子节点，或回到步骤1
例如，现在要将25插入到如下的2-3-4树中
从根节点开始查找，直到找到节点(22,24,29)
节点(22,24,29)是一个4度节点，所以将中间值加入父节点中，剩下的左右两个值(22,29)分裂成成2个2度节点
再次查找到节点29，该节点没有左孩子，将25直接插入到该节点中
删除操作
从2-3-4树删除节点时，执行以下操作
-
查找需要被删除的元素
- 如果元素不在叶节点，记住它的位置并从左子树(右子树)继续向下查找，直到叶节点。该叶节点应该是左子树最右边的值(右子树最左边的值)
- 交换需要删除的值和第二次查找到的值
- 最简单的是从上到下对树进行调整，使得找到的叶节点不是2度节点，这样交换之后就不是2度节点，可以直接删除
- 如果叶节点的元素是2度节点，则需要执行后面的操作
-
如果兄弟节点是3度节点或是4度节点，执行以下旋转操作
- 从兄弟节点移除一个节点替换父点节的值
- 把替换出来父节点的值合并入当前节点变成一个3度节点
-
如果父节点是2度节点且兄弟节点也是2度节点，合并三个节点变成一个新的4度节点。如果该节点是根节点，高度减1。
-
如果父节点是3度节点或是4度节点，且兄弟节点是2度节点，做以下的操作
- 合并当前节点和兄弟节点及父节点的一个值，使当前节点变成一个4度节点
-
现在，当前节点有多个值，移除需要删除的值即可
删除N从树中，N是叶子节点，且是节点中唯一的值
它的兄弟节点有至少两个值，所以移动兄弟节点的值F到父节点，移动父节点的值H到当前节点
现在有两个节点在当前叶子节点中，删除当前节点的N值
删除H从树中，H是个叶子节点，且是节点中唯一的值，且没有两个节点的兄弟节点
它的父节点有两个值，所以合并兄弟节点和父节点的一个值，当前节点带有3个值变成4节点
现在可以简单地删除H从当前叶子节点中
此时再次删除R，遍历树的时候，我们能够发现，根节点(P)和它的两个子节点(C和V)都只有一个值，这时合并这三个节点
合并后如下图所示
此时遍历到带有R的节点，可以发现其是叶子节点，该节点有两个值
简单地删除值R从当前节点中
删除与插入操作的另外一种方法
上面的插入与删除操作的方法来自wikipedia和其它互联网资料。几乎所有的资料都这样介绍2-3-4树的操作流程。
但是却还有另外的操作流程来完成2-3-4树的删除与插入。区别是：插入元素的时候，遍历过程不分裂4度节点，而是插入元素到叶子节点后，向上循环修正；删除元素的时候，遍历过程中不合并节点，删除元素后再向上循环修正。这种做法才是与现的红黑树和B树的操作流程相符合的。
我们根据这个来总结红黑树和B树的一般操作方法(在2-3-4树中)
-
插入时。先查找到叶子位置的插入节点，插入元素。循环修正：如果插入后节点元素数量大于3，分裂节点，把中间节点插入父节点，循环检查和分裂直到父节点元素数量不大于3。
-
删除时。先查找到需要删除的节点，如果该节点是内部节点，则交换到左子树的最右叶子节点或右子树最左叶子节点，删除它。循环修正：如果删除后元素数量为0，可以从兄弟节点旋转一个元素过来，如果兄弟节点只有一个，取出一个父节点和兄弟节点合并为一个新节点。循环检查父节点和合并直到父节点元素数量大于0。
转载文章请注明出处： http://mingnote.com