我从(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 与他刚刚在上一章中完成的 BST 更密切相关。