Question

100分悬赏!! 恳求资料结构"2-3-4 tree"新增和删除的演算法!!

各位大哥大姊们大家好!!

我有一个有关於"资料结构"方面的问题想要请教各位。

我想要请问各位，资料结构"2-3-4 tree"新增和删除的演算法为何??

用"中文解说"或"程式码"来回答都可以噢!!

希望各位能够替我解答，回答得愈详细愈好噢!!

那麼就万事拜托了!! 谢谢各位!!
P.S. 可以的话，请举例说明。因为这样我才比较容易了解!!

Answer 1

定义
一棵 2-3 树必须符合下列几项定义：

(1) 2-3 tree 中的节点可以存放一笔或两笔资料。
(2) 若节点中存放了一笔资料 Ldata.key ，其必须存在两个子节点-左子节点与中子节点。
假设资料 Ldata 的键值为 Ldata.key ，则：
(a) 左子节点所存放的资料键值必须小於 Ldata.key 。
(b) 中子节点存放的资料键值必须大於 Ldata.key 。

(3) 若节点中存放了两笔资料 Ldata 与 Rdata ，则会存在三个子节点-左子节点、中子节点与右
子节点。
假设资料 Ldata 、Rdata 的键值分别为 Ldata.key 与 Rdata.key，则：
(a) Ldata.key < Rdata.key 。
(b) 左子节点所存放的资料键值必须小於 Ldata.key 。
(c) 中子节点所存放的资料键值必须大於 Ldata.key 和小於 Rdata.key 。
(d) 右子节点所存放的资料键值必须大於 Rdata.key 。

(4) 树中的所有树叶节点必须为同一阶度 ( Level ) 。

特性
(1) 有 n 个元素的 2-3 tree 之高度介於 [ log3( n+1 ) ] 和 [ log2( n+1 ) ]。
(2) 在高度为 h 的 2-3 tree 中，元素的个数介於 2h - 1 到 3h - 1 。
(3) 在 n 个元素的 2-3 tree 中，插入和删除需要时间为 O( log n ) 。

2-3 tree 加入的方法

由 2-3 tree 中开始搜寻，假如加入的资料键值在 2-3 tree 中找不到，则加入 2-3 tree 中，假设
加入的节点
1、该节点只有一笔资料，则直接加入。如下例

2、该节点已存在资料，则将此节点一分为二。如下例

2-3 tree 的删除方法

2-3 tree 的删除分为两个部份：一为树叶节点 ( leaf node ) ，另一为非树叶节点 ( non-leaf node
) 。
(1) 若删除的节点是树叶节点

(a) 若节点的键值删除后，还有其它的键值存在，则直接删除。如下例：

(b) 若节点的键值删除后，已经没有其他的键值存在，则须调整。如下例：

(2) 若删除的节点是非树叶节点

假设欲删除的键值 x 为非树叶节点，此时须找一节点 p' ( 当 x 为节点的左边键值，p' 存在
於该节点的中子树 ; 若为右边键值，则 p' 存在於右子树 ) ，此 p' 必需是树叶点，在 p' 中找
一个最小值 y ( y 为 p' 的左边键值 ) ，将 y 值代替 x 值。

2-3-4 树 ( 2-3-4 tree )

定义
2-3-4 tree 为 2-3 tree 的观念扩充，一棵 2-3-4 tree 须符合下列定义：
(1) 2-3-4 tree 中的节点可以存放一笔、两笔或三笔资料。
(2) 若节点中存放了一笔资料 Ldata ，其必须存在两个子节点-左子节点与左中子节点。
假设资料 Ldata 的键值为 Ldata.key 则
(a) 左子节点所存放的资料键值必须小於 Ldata.key 。
(b) 左中子节点所存放的资料键值必须大於 Ldata.key 。

(3) 若节点中存放二笔资料键值 Ldata 和 Mdata ，则会存在三个子节点-左子节点、左中子节
点与右中子节点。
假设资料 Ldata 的键值为 Ldata.key , Mdata 的键值为 Mdata.key 则
(a) Ldata.key < Mdata.key。
(b) 左子节点所存放的资料键值必须小於 Ldata.key 。
(c) 左中子节点所存放的资料键值必须大於 Ldata.key , 小於 Mdata.key。
(d) 右中子节点所存放的资料键值必须大於 Mdata.key 。

(4) 若节点中存放三笔资料键值 Ldata 、 Mdata 与 Rdata ，则会存在四个子节点 - 左子节点、
左中子节点、右中子节点与右子节点。
假设资料 Ldata 、Mdata 与 Rdata 的键值分别为 Ldata.key 、Mdata.key 与 Rdata.key 则
(a) Ldata.key < Mdata.key < Rdata.key 。
(b) 左子节点所存放的资料键值必须小於 Ldata.key 。
(c) 左中子节点所存放的资料键值必须大於 Ldata.key , 小於 Mdata.key。
(d) 右中子节点所存放的资料键值必须大於 Mdata.key ,小於 Rdata.key。
(e) 右子节点所存放的资料键值必须大於 Rdata.key 。

(5) 所有的叶节点必须在同一阶度 ( Level ) 。

特性
(1) 有 n 个元素的 2-3-4 tree ，其高度介於 ┌ log4(n+1) ┐和 ┌ log2(n+1) ┐。
(2) 在 n 个元素的 2-3-4 tree 中，插入和删除需要时间为 O( logn ) 。

红-黑树 ( Red-Black tree )

红-黑树 ( Red-Black tree ) 是 2-3-4 tree 的一种二元树表示法。

定义
(1) 红-黑树为一棵二元搜寻树 ( binary search tree ) 。
(2) 由树根节点到任何一个树叶节点，其所经过的黑色链结数目都是相同的。
(3) 由树根节点到任何一个树叶节点，其所经过的路径不会连续出现两条红色的链结。

特性
(1) 在红-黑树中有一个很重要的特性-子节点分为黑与红两种，黑色代表实际的链结，红色代表
原本不存在的链结。

简而言之，在 Red-Black tree 中，红线链结的节点，在 2-3-4 tree 中为同一节点。如上图所示
。

(2) 每一个有 n 个(内部)节点的红-黑树RB满足下列各式：
(a) hight(RB) <= 2┌ log2(n+1) ┐
(b) hight(RB) <= 2 rank(RB)
(c) rank(RB) <= ┌ log2(n+1) ┐
(3) 资料的插入，其所需的时间复杂度为 O( log n ) 。