考虑一个有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
发布于 2022-10-12 08:21:40
正确的答案是A,但这只是因为它问“最多”,而不是一个更明确的“多少可以是红色”。
有些树具有均匀的内部节点计数,在这些树中,每个黑色节点都不可能有一个红色子节点。这方面的一个例子是N是4。然而,在N为2或8的情况下,这是可能的。
在N为2的情况下,以下树工作: 1B 2R
而对于N=8:
6B
3R 7B
2B4B8R1R5R
基本上,它可以工作在任何树上,其中最极端的内部节点(也就是任何给定路径上最远离根的节点)都是黑色的,任何其他的黑色节点都有一个红色子节点,方法是在这些最极端的节点中添加一个红色子节点。
我的意思是将下面的5节点树从上面转换为8节点树: 6B 3R7B2B4B。
https://stackoverflow.com/questions/74003991
复制相似问题