红黑树技术问题：带单红子节点的黑节点数量及树高求解

问题1 #

给定一棵包含n个内部节点（n为偶数）的红黑树，其中最多有多少个是带有一个红色子节点的黑色节点？
选项：A. n/2；B. n；C. ⌊lg(n+1)⌋-1；D. ⌊lg(n+1)⌋；E. 以上均不对。

解答 #

根据红黑树的核心性质：从任意节点到其所有后代叶子节点的路径上，黑节点的数量必须相同。若一个黑色节点带有一个红色子节点，其另一个子节点无论是NIL还是黑色节点，都会受到黑高一致性的限制：

• 若另一个子节点是NIL，会导致两条路径的黑节点数不一致，违反红黑树性质；
• 若另一个子节点是黑色节点，则该黑色节点的黑高需与红色子节点的黑高匹配，这极大限制了带红子节点的黑色节点的数量。

实际上，符合条件的黑色节点最大数量无法用选项A-D中的表达式表示，因此答案选E。

问题2 #

在满足上述问题最优解的含26个节点的红黑树中，树的最大高度是多少？假设单个节点的树高度为1。
选项：A. 5；B. 6；C. 7；D. 8；E. 9。

解答 #

要构造满足最优解的最大高度红黑树，需在符合红黑树性质的前提下，尽可能让树的结构“伸展”。红黑树的高度受黑高限制，对于26个节点的红黑树，通过合理排列黑节点与红节点，保证所有路径黑高一致的同时最大化高度，最终可得到的最大高度为7。因此答案选C。

内容的提问来源于stack exchange，提问作者Chichi