哪一种更容易实现: 2-3-4树还是红黑树？

Question

我正在学习的教科书(拉弗尔)首先介绍了红黑树，不包括任何伪代码，尽管相关的算法看起来相当复杂，有许多独特的例子。

接下来，他展示了2-3-4棵树，在我看来，这些树更容易理解，我猜，也是要实现的。他包含了一些实际的Java代码，这是非常清楚的。他似乎暗示2-3-4更容易实现，基于我迄今所见，我会同意这一点。

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

树

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

具体来说，关于“更多的特例”的部分对我来说似乎是很落后的(我认为是RB有大量的特例，而不是2-3-4)。但是，我仍然在学习(老实说，我还没有把头完全裹在红黑树上)，所以我很想听听别人的意见。

作为一个副手..。虽然我同意拉弗尔说的大多数话，但我认为有趣的是，与维基百科所说的普通(RB之前的2-3-4)相比，他把它们按相反的顺序呈现出来。我确实认为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

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