Preparing NOJ

红黑树的红色内结点问题

1000ms 65536K

Description:

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

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

(1)每个结点被染成红色或黑色;

(2)每个前端结点为黑色结点;

(3)任一红结点的儿子结点均为黑结点;

(4)在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。

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

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

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

Input:

输入的文件的第一行是正整数n1<n<5000

Output:

输出红色内结点个数的最小值和最大值。第1行是最小值,第2行是最大值。

Sample Input:

8

Sample Output:

1
4

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1248

Tags

Submitted 3

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet