哪个更容易实现：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）。但是，我仍在学习中（并且还没有完全理解红黑树），所以我很想听听其他人的意见。

作为一个附注……虽然我同意Lafore所说的大部分内容，但我认为有趣的是他将它们呈现的顺序与维基百科所说的常见顺序相反（RB之前是2-3-4）。我认为先学习2-3-4再学习RB更有意义，因为RB更难以概念化。也许他选择这个顺序是因为RB与他在前一章刚刚完成的BST更密切相关。

- The111

---

我不确定哪种更容易实现，但是 这个 可能会有所帮助。 - Lazer

这似乎相当主观，也许您可以编辑问题，更具体地说明什么构成了“更容易”。也许只需要考虑的特殊情况数量？ - Michael J. Barber

我理解你的意思，但是维基百科和我提到的教材都使用了同样的概括方式...即仅从“易用性”或“简单性”的角度比较两个独立算法的实现。我想衡量这种模糊词汇的一种指标可能是SLOC。另一个指标是“易于理解”，这确实是主观的...但我认为在大多数情况下，指标是正确的：更少的SLOC = 更容易理解。 - The111

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

这个著名的定义来自于Okasaki的论文from Okasaki's paper

- Don Stewart