“红树/黑树”这个词从何而来？

Question

红/黑树是实现平衡的二进制搜索树的一种方法。它的工作原理对我来说是有意义的，但选择的颜色却没有。为什么红和黑，而不是其他颜色或属性在一般情况下？当我听到“红色和黑色”时，首先想到的是棋盘和莱斯·米塞拉布，它们在这种情况下似乎都不适用。

Answer 1

编辑:Guibas教授的回答：

从莱昂尼达斯·吉巴斯( Leonidas Guibas guibas@cs.stanford.edu )到“红色-黑色”( red - black )这个词，通过cs.stanford.edu的“隐藏细节”( 16:16 ) (0分钟前)，我们有红笔和黑笔来画树。

我相信这个词最早出现在1978年莱昂尼达斯·J·吉巴斯和罗伯特·塞奇威克的“平衡树的二色框架”中。

Answer 2

罗伯特·塞奇威克( Robert )在“古瑟尔，红-黑BSTs (2012年)”中说：

很多人问我们为什么要用红黑这个名字。我们发明了这种数据结构，这种看待平衡树的方式，在Xerox，它是个人电脑的所在地，还有我们今天所经历的许多其他创新，包括碳化硅图形用户界面，以太网和面向对象的编程，碳化硅和其他许多东西。但是发明的东西之一是激光打印，我们非常兴奋地看到附近的彩色激光打印机可以打印出颜色和颜色的东西，红色看起来最好。所以，这就是为什么我们选择红色来区分红色链接，链接的类型，三个节点。所以，对于那些一直在问的人来说，这是一个问题的答案。

Answer 3

答案是，数据结构的创建者只有红色和黑色的笔来画红黑树的名字。维基百科在同一篇文章中还说：

颜色“红色”之所以被选中，是因为它是作者在施乐PARC公司工作时可以使用的彩色激光打印机产生的最好看的颜色。

请参考这里。