问题描述
我考试下周算法，并给予问题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红色节点或不的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！