红黑树的根节点为啥要是黑的
我先来回答第二个问题，这样做是为了给搜索性能提供保证。如果你单看黑色节点，红黑树是高度平衡的，而红色节点不能互为父子，保证了红色节点层数小于等于黑色层数。这样对节点X，它到叶子最大距离为，N黑1+N红，最小距离为N黑2，已知N黑1==N黑2，且N红\u0026lt;=N黑，那么最长距离\u0026lt;=最短距离*2，而严格平衡二叉树高度肯定介于这个最短距离到最长距离之间，而有多高就最多搜索几次，所以这样保证了红黑树搜索性能最多不超过严格平衡二叉树的2倍。至于第一个问题，其实这是一个比较自然的选择，有时候确实有可能旋转着，旋转着，根节点就变为红色了。
【红黑树的根节点为啥要是黑的】
比如，如果85这个点是根节点，那么这次旋转会使根节点变为红色。这个时候我们可以令80这个点为黑色，原因是应对下面这种情况
这个旋转以后发现40和60都为红色，又要旋转，这样一级一级转上去，必须要遇到一个上面的节点是黑色才能终止，这就是随时使根节点保持黑色的好处。综合起来，条件1根节点为黑色可以保证，通过一系列旋转最终能实现条件2父子节点不同时为红色，条件3任意节点到它的任意叶子节点路径上所含黑色节点个数相等。而条件2，3又为红黑树的搜索效率提供了保证！
■网友
回答第一个问题：红黑树的根节点为什么要是黑的？
答案：因为麻烦。
假设你有一个红色的根节点，现在，你要加入一个新的节点，按照要求，这个节点必须是黑色的，因为不能有连续的红色，然后，会变成下图这样
但是这个时候，你发现问题了吗？他不符合要求，每条路径上的黑色节点的数量必须是一样的。左边的路径黑色的节点数量为0，右边的路径黑色节点数量为1.这个时候，唯一能做的就是进行变色或者旋转，把根节点变成黑色的，把子节点变成红色的。如下图
既然加入第二个节点后就会必须要把根节点变成黑色的，那为什么不一开始就要求根节点是黑色的。
第二个问题：为什么从每个叶子到根的所有路径上不能有两个连续的红色节点？
答案：为了保证树的平衡，保证最长的路径最多是最短路径的的两倍。
想象一下，由于每条路径上的黑色节点都必须相等，所以最短的路径肯定是全是黑色节点。那最长的路径呢，如果要求红色的点不能连续，那最长的路径肯定是红黑相隔，由于根节点是黑色的，所以，最长的路径应该是黑色节点和红色节点一样多，也就是黑色节点的两倍。
■网友
看《算法》里的红黑树就清楚了。
■网友
因为黑点才是关键，红点是辅助的。参见此说。
推荐阅读
- 为啥看到书柜上的藏书会有心旷神怡的感觉
- 为啥知乎上普便有一种【我在北上广深打工，所以拥有更好的视野】这样的错觉
- 为啥工商银行的用户体验如此之差
- 汽车|看了中消协4S店服务测评调查结果，终于知道法系车为啥卖不好了
- 你为啥从窝窝商城离职?
- 为啥5G和2.4G默认的BSSID是相同的
- 为啥电器实体店的价格比淘宝贵那么多
- 现在在线学习视频有很多了，为啥大部分人还是喜欢下载下来观看
- 为啥到现在你还没有女朋友 ?
- 天赐的声音|33岁张雨绮为啥总离婚？看过这些照片就明白了，都是性感惹得祸