题目描述

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

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

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

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

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

输入格式

输入共一个数 $n$。

输出格式

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

8

1
4

数据规模与约定

• 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^3$

题目来源

没有写明来源