Question

数据结构：红黑树

1. 一棵红黑树的根节点的阶（根节点到外部节点路径上黑色边的数目）为2，则其节点数目（不包括外部节点）最多为 （3分）
A. 13 B.14
C. 15 D.16
求答案 最好有个计算公式什么的

Answer 1

好乱。
红黑树只有三个性质。
1：根节点和所有外部节点是黑色。
2：根至外部节点中没有两个连续的颜色是黑色
3：所有根节点至外部节点的路径上都有相同数目的黑色节点。

注1：外部节点就是叶节点指向的NULL节点，只不过这里不再指向NULL，而是一个实质性的空节点。
注2：红黑树还有另一种规则（路径指针），但是和上面的是一样的意思，所以不列举了。
以上回答你满意么？

追问

。。。我知道性质 但是推不出这个题

Answer 2

15个吧
因为根节点到外部节点上黑边的数目是2，然后不允许有连续的红边出现，但从左子树一直下去来看可以使红-黑-红-黑，一共是5层，不算外部节点（叶节点）应该就是四层，所以是2^4-1=15