在145个节点的红黑树中，可能的最小和最大红色节点数是多少？

Question

请告诉我是否有任何公式可以计算红黑树中的最小/最大红色节点？

Answer 1

红黑树是二叉搜索树被附加地通过4条规则

1. 每个节点是红色或黑色的约束
2. 根是黑色
3. 每红色节点必须具有0或2黑人儿童
4. 每根空路径必须有相同数量的黑色节点

的最小数目的的红色节点只是0.没有要求强迫红黑树有任何红色节点。

如果我们在每条路径上交错红色和黑色节点，并尽可能多地使真实红色叶子的数量达到，我们可以获得最大数量的红色节点。在这种情况下，每个红色节点有两个黑色子节点，根节点应该是黑色的。 因此=> n_black = 2 * n_red + 1 我们也知道，n_black + n_red = n（n为我们的节点总数）

这里有一些链接，如果你需要进一步的帮助：http://doctrina.org/maximum-height-of-red-black-tree.html，https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13b.pdf