红黑树 Red-Black Tree

红黑树 - 可视化

介绍

1972年，鲁道夫贝尔最先发明，但是他称之为“对称二叉B树”，真正的称之为“红黑树”是在1978年Leo J. Guibas 和 Robert Sedgewick的一篇论文开始的。

红黑树的命名和Xerox PARC也有关系，当时Robert Sedgewick在施乐做访问学者的时候，施乐正好发明出激光彩色打印机，然后觉得这个打印机打出的红色很好看，就用了红色来区分结点的不同，于是就叫红黑树了。 （注：这个数据结构是1972 由 Rudolf Bayer 发明的，叫 "symmetric binary B-tree"）。摘自左耳朵耗子的 微博。

口诀：

左根又，根叶黑。 不红红，黑路同。