红黑树那一堆规则是怎么想到的?

Question

所有讲红黑树的文章都认为自己把红黑树讲清楚了透彻了,比如本站的一堆文章:

https://segmentfault.com/a/11...

所有这些文章都会讲解红黑树规则，配上示例图片，怎么旋转,改变节点颜色。

但是，几乎没有文章会说，人们是怎么想到红黑树的，为什么要给树的节点染上红黑两种颜色呢？毕竟，现实中没有树有两种颜色，人们无法从现实世界的树想到红黑树；即使要上颜色，为什么是红黑两种，而不是三种、4种、和5种呢？

为什么的问题不解决，所有关于红黑树的讲解，说明，都是空中楼阁，地基不稳，他们都是毫无道理的，即使所谓的红黑树在实际运行中观测到的效率好比其他的平衡树、AVL树效率好高，但是，并没有理论证明所有情况下都是这样。

为什么红黑树的规则是这样的，为什么会想到，人们是怎么想到红黑树规则的？希望有同学能想清楚这个问题，大做一篇文章，我想对所有的辛辛学子都会有帮助。

Answer 1

我终于找到一篇文章很好的讲述红黑树的原理了：

https://www.cnblogs.com/zhenb...

其实就是一句话，红黑树其实是由234树变化而来的，把红黑树所有的红节点与父节点合并，就能得到一颗234树；反之，将234树中有2个以上数据的节点拆分开来，子节点染红，其余节点染黑就能得到红黑树。

希望那些早期不懂还冷嘲热讽的垃圾自觉点，不要学这些知识，你们配不上。

还要一些人，不懂就多看，多学，少讲废话。我想，多数人可能和我一样，宁愿帖子无人回复，也不愿看到垃圾跑进来发表多余的废话。

这是给那些真心求学的学子们看的，垃圾们看到了也看不懂。

Answer 2

二叉搜索树只有（接近）平衡了才可以保证查找效率。

为了可以再保证平衡的情况下实现快速的插入与删除，就得再节点上记录额外的信息。否则每次操作得把数遍历一遍才可以知道树的状态。

红黑树只需要将节点分成两类，就可以了。它当然可以把这两类叫做“用于计算高度的节点”(黑)跟“不用于计算高度的节点”(红)，但是这个名字太长了。（红黑树通过保证每条路上的“用于计算高度的”节点数量相等，来保证树是近似平衡的）于是用两个颜色吧。（开始由人这么叫了，于是大家就都这么叫了，约定俗称而已）

为啥是两个颜色不是更多呢？因为这个算法只需要两个状态啊。还有一些算法，会需要更多的状态，不过人家也不用颜色的叫法了。（同样，这也是约定俗称而已）。

Answer 3

哈哈，奇葩问题无处不在。
别纠结名字，你可以叫黑白树，甚至牛马树，为什么是树？因为看起来像而已。
另外它是怎么想到的？？？ excuse me？ 数学里面算法、公式一大堆，不是每一种都能说出一个阿基米德的故事。很多就是自己思考更优解推算得来的，而不是需要一个原因去想到。
还大做文章，吃饱了没事做。。。