2037_红黑树的红色内节点问题

红黑树是一类特殊的二叉搜索树，其中每个节点被"染成"红色或黑色。若将二叉搜索树节点中的空指针看作是指向一个空节点，则称这类空节点为二叉搜索树的前端节点。并规定所有前端节点的高度为-1。

一棵红黑树是满足下面"红黑性质"染色二叉搜索树：

(1) 每个节点被染成红色或黑色；
(2) 每个前端节点为黑色节点；
(3) 任一红节点的儿子节点均为黑节点；
(4) 在从任一节点到其子孙前端节点的所有路径上具有相同的黑节点数。

从红黑树中任一节点x 出发(不包括节点x)，到达一个前端节点的任意一条路径上的黑节点个数称为节点x的黑高度，记作bh(x)。红黑树的黑高度定义为其根节点的黑高度。

图示的二叉搜索树是一棵红黑树。标在节点旁边的数字是相应节点的黑高度。

图 红黑树

给定正整数n，试设计一个算法，计算出在所有含有n个节点的红黑树中，红色内节点个数的最小值和最大值。

输入只有一行：正整数n，1 < n < 5000 。

输出红色内结点个数的最小值和最大值，第一行是最小值，第二行是最大值。

8

1
4