题18
题目
Q:下列关于红黑树的说法中, 正确的是 ( ).
A. 红黑树的红结点的数目最多和黑结点的数目相同
B. 若红黑树的所有结点都是黑色的, 则它一定是一棵满二叉树
C. 红黑树的任何一个分支结点都有两个非空孩子结点
D. 红黑树的子树也一定是红黑树
分析
A:红黑树不是要保证根结点是红色的吗，那还怎么做到所有的结点都是黑色的？我记错了！根节点是黑色的！
如果一个结点是红色的，那么它的孩子结点一定是黑色的
那么红色结点从哪里来呢，我们插入结点构造树的时候，默认都是红色，如果它违反了红黑树的性质，我们就需要对它进行调整，这就使得结点可能变成了黑色
解
B
红黑树的红结点数目最大可以是黑结点数目的 2 倍 (如一棵有 3 个结点的红黑树, 第 1 层为黑色, 第 2 层为红色), A 错误。
从根结点出发到所有叶结点的黑结点数是相同的, 若所有结点都是黑色, 则一定是满二叉树, B 正确。
考虑某个黑结点, 它可以有一个空叶结点孩子和一个非空红结点孩子, C 错误。
红黑树中可能存在红结点, 根结点为红色的子树不是红黑树, D 错误。