[SDOI2008]红黑树(TREE)

NC20319. [SDOI2008]红黑树(TREE)

描述

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

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

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

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

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

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

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

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

输入描述

输入共一个数N。

输出描述

输出共两行。

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

示例1

输入:

输出:

1
4

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 3ms, 内存消耗: 388K, 提交时间: 2023-07-05 11:41:04

#include<iostream>
#include<cstdio>
using namespace std;
int k,n,mn,mx;
int main(){
	scanf("%d",&n);
	k=n+1;
	while(k>1){
		if(k&1)mn++;
		k>>=1;
	}
	k=n+1;
	while(k>1){
		if(k==2)mx++,k--;
		else if(k%4==0){
			mx+=k>>1;
			k>>=2;
		}
		else if(k%4==1){
			mx+=(k-3)>>1;
			k=(k+3)>>2;
		}
		else if(k%4==2){
			mx+=(k-2)>>1;
			k=(k+2)>>2;
		}
		else {
			mx+=(k-1)>>1;
			k=(k+1)>>2;
		}
	}
	printf("%d\n%d",mn,mx);
}

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 432K, 提交时间: 2022-04-16 21:58:04

#include<cstdio>
int n,m,ans;
int main()
{
	scanf("%d",&n);
	m=n+1;
	while(m>1)
	{
		ans+=m&1;m>>=1;
	}
	printf("%d\n",ans);
	m=n+1;ans=0;
	while(m>1)
	{
		if(m==2) ans++;
		if((m&3)==1) ans+=m/4*2-1,m/=4,m++;
		else if((m&3)==2) ans+=m/4*2,m/=4,m++;
		else if((m&3)==3) ans+=m/4*2+1,m/=4,m++;
		else ans+=m/4*2,m/=4;
	}
	printf("%d\n",ans);
	return 0;
}