问题描述
我考试下周算法,并给予问题prepare它。其中的一个问题是,虽然我难住了。
I have an exam next week in algorithms, and was given questions to prepare for it. One of these questions has me stumped though.
我们可以得出一个红黑树有7黑色节点和10个红色节点?为什么?
"Can we draw a red-black tree with 7 black nodes and 10 red nodes? why?"
这听起来像它可以很快地回答,但我不能让周围我的脑海里。
It sounds like it could be answered quickly, but I can't get my mind around it.
的CRLS给我们一个RB树具有n个内部节点的最大高度:2 * LG(N + 1)
The CRLS gives us the maximum height of a RB tree with n internal nodes: 2*lg(n+1).
我认为这个问题可以单独使用这个引理得到解决,但我不知道。
I think the problem could be solved using this lemma alone, but am not sure.
任何提示?
推荐答案
由于这是考试preparation,我不想给你一个直接的答案,但我认为你需要考虑的是属性管理你如何建立一个红黑树:
Since this is exam preparation, I don't want to give you a direct answer, but I think what you need to consider is the properties that govern how you build a Red-Black Tree:
- 节点是红色或黑色。
- 根是黑色的。 (此规则有时与其他定义省略了。因为根总是可以从红色到黑色的改变,但并不一定反之亦然这个规则对分析影响不大。)
- 所有的叶子都是黑色的。
- 在每个红色节点的两个孩子都是黑色的。
- 从给定节点到其任何后代留下每简单的路径中包含的黑色结点相同。
(从维基百科的页面披肩这些: http://en.wikipedia.org/wiki/红black_tree )
(Stole these from the wikipedia page: http://en.wikipedia.org/wiki/Red-black_tree)
由于节点的计数,你上市,你能满足所有这些属性?
Given the count of nodes you listed, can you meet all of these properties?
这篇关于如何判断一个红黑树是否能有×黑色节点和Y红色节点或不的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!