2-3-4树和红黑树哪个更容易实现？

Question

我正在学习的教科书（Lafore）首先介绍了红黑树，并且不包含任何伪代码，尽管所提供的相关算法似乎相当复杂，有许多独特的情况。

接下来他提出了 2-3-4 树，在我看来，它更容易理解，而且我猜也更容易实现。他包含了一些非常清晰的实际 Java 代码。他似乎暗示 2-3-4 更容易实施，根据我迄今为止所看到的情况，我同意这一点。

然而，维基百科却说相反......我认为这可能是不正确的：

http:// en.wikipedia.org/wiki/2-3-4_tree

2-3-4树是红黑树的等距树，这意味着它们是 等效的数据结构。换句话说，对于每棵 2-3-4 树， 至少存在一棵红黑树，其中包含数据元素 相同的顺序。此外，2-3-4树上的插入和删除操作 导致节点扩展、分裂和合并等价于 红黑树中的颜色翻转和旋转。简介 红黑树通常首先引入2-3-4树，因为它们是 概念上更简单。 但是，2-3-4 棵树可能很难 由于数量众多，因此可以在大多数编程语言中实现 涉及树操作的特殊情况。红黑树是 实现起来更简单，因此倾向于使用。

具体来说，关于“大量特殊情况”的部分对我来说似乎相当落后（我认为是 RB 具有大量特殊情况，而不是2-3-4）。但是，我仍在学习（而且老实说还没有完全理解红黑树），所以我很想听听其他意见。

作为旁注……虽然我确实同意拉福尔所说的大部分内容，但我认为有趣的是，与维基百科所说的常见顺序相比，他以相反的顺序呈现了它们（2-3-4 在 RB 之前）。我确实认为 2-3-4 首先会更有意义，因为 RB 很难概念化。也许他选择这个顺序是因为 RB 与他在上一章中刚刚完成的 BST 关系更密切。

Answer 1

关于“大量特殊情况”的部分对我来说似乎相当落后（我认为是RB具有大量特殊情况，而不是2-3-4）

RB 树可以在十几个左右实现行，如果您的语言中有模式匹配：

data Color = R | B
data Tree a = E | T Color (Tree a) a (Tree a)

balance :: Color -> Tree a -> a -> Tree a -> Tree a
balance B (T R (T R a x b) y c          ) z d                               = T R (T B a x b) y (T B c z d)
balance B (T R a           x (T R b y c)) z d                               = T R (T B a x b) y (T B c z d)
balance B a                               x (T R (T R b y c) z d          ) = T R (T B a x b) y (T B c z d)
balance B a                               x (T R b           y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance col a x b = T col a x b

insert :: Ord a => a -> Tree a -> Tree a
insert x s = T B a y b where
  ins E          =  T R E x E
  ins s@(T col a y b) 
    | x < y      =  balance col (ins a) y b
    | x > y      =  balance col a y (ins b)
    | otherwise  =  s
  T _ a y b = ins s

这个著名的定义 来自冈崎的论文