有多少个节点可以是一个红色子节点的黑色节点？
提问于 2022-10-09 02:32:54
考虑一个有n个内部节点的红黑树，其中n是偶数.最多有多少人可以是一个带一个红色孩子的黑色节点？
A. n/2 B. C. lg(n+1-1 D. lg(n+1 E. )
在达到上述问题解决方案的26个节点的红黑树中，树的最大高度是多少？一个节点的树被假定有高度1。
A. 5 B. 6 C. 7 D. 8 E. 9
回答 1
Stack Overflow用户
发布于 2022-10-12 08:21:40
正确的答案是A，但这只是因为它问“最多”，而不是一个更明确的“多少可以是红色”。
有些树具有均匀的内部节点计数，在这些树中，每个黑色节点都不可能有一个红色子节点。这方面的一个例子是N是4。然而，在N为2或8的情况下，这是可能的。
在N为2的情况下，以下树工作: 1B 2R
而对于N=8：
6B
3R 7B2B4B8R1R5R
基本上，它可以工作在任何树上，其中最极端的内部节点(也就是任何给定路径上最远离根的节点)都是黑色的，任何其他的黑色节点都有一个红色子节点，方法是在这些最极端的节点中添加一个红色子节点。
我的意思是将下面的5节点树从上面转换为8节点树: 6B 3R7B2B4B。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74003991
复制
腾讯云开发者
