data-structures - 哪个更容易实现 : 2-3-4 Tree or Red-Black Tree?

Question

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

接下来，他展示了 2-3-4 棵树，在我看来，这些树更容易理解，我猜想实现。他包含了一些非常清晰的实际 Java 代码。他似乎暗示 2-3-4 更容易实现，根据我目前所见，我同意。

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

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

2-3-4 trees are an isometry of red-black trees, meaning that they are equivalent data structures. In other words, for every 2-3-4 tree, there exists at least one red-black tree with data elements in the same order. Moreover, insertion and deletion operations on 2-3-4 trees that cause node expansions, splits and merges are equivalent to the color-flipping and rotations in red-black trees. Introductions to red-black trees usually introduce 2-3-4 trees first, because they are conceptually simpler. 2-3-4 trees, however, can be difficult to implement in most programming languages because of the large number of special cases involved in operations on the tree. Red-black trees are simpler to implement, so tend to be used instead.

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

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

Answer 1

the part about the "larger number of special cases" seems quite backward to me (I think it is the RB which have the large number of special cases, not the 2-3-4)

RB Trees 可以用十几行代码实现，如果你的语言有模式匹配的话:

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

这个著名的定义 from Okasaki's paper