Skip to content

1007 Red-black Tree

Statement

Metadata

  • 作者: CAO, Peng
  • 单位: Google
  • 代码长度限制: 16 KB
  • 时间限制: 150 ms
  • 内存限制: 64 MB

There is a kind of binary tree named red-black tree in the data structure. It has the following 5 properties:

  • (1) Every node is either red or black.
  • (2) The root is black.
  • (3) All the leaves are NULL nodes and are colored black.
  • (4) Each red node must have 2 black descends (may be NULL).
  • (5) All simple paths from any node x to a descendant leaf have the same number of black nodes.

We call a non-NULL node an internal node. From property (5) we can define the black-height of a red-black tree as the number of nodes on the simple path from the root (excluding the root itself) to any NULL leaf (including the NULL leaf). And we can derive that a red-black tree with black height H has at least 2^H-1 internal nodes.

Here comes the question: given a positive N, how many distinct red-black trees are there that consist of exactly N internal nodes?

Input Specification

Each input file contains one test case which gives a positive integer N (\le 500).

Output Specification

For each case, print in a line the number of distinct red-black tees with N internal nodes. Since the answer may be very large, output the remainder of it divided by 1000000007 please.

Sample Input 

5

Sample Output 

8

Tutorial

题意：

红黑树的属性如下：

  • 每个结点为黑色或者红色。
  • 根是黑色。
  • 所有的叶子结点都是 NULL，并且都是黑色结点。
  • 每个红色结点都必有两个黑孩子，这两个黑孩子可以是NULL。
  • 从任一结点出发，到其子树的任一叶子结点上，黑色结点的数量必须相同。

定义非 NULL 结点为 internal node，black-height 为根到任一叶子结点的简单路径中的黑色结点数量(不包括根节点，但是包括叶子结点)。

然后就能得出 black-height 为 H 的红黑树，至少有 2^H - 1 个 internal node。

为什么？

  • 因为每个非NULL结点都有两个孩子，而且一个红色结点对高度没有贡献，但是对internal node有贡献。
  • 直接考虑全黑的一棵红黑树就是高度为 H 的满二叉树，此时结点数量为 2^H - 1，也就是下界。

给出 n(1 \leq n \leq 500)，求有多少棵红黑树，使得其internal node数量恰好为 n。

思路：

考虑：

  • r_{i, j} 表示以红色结点为根，black-height 为 i，internal node 为 j 的方案数。
  • b_{i, j} 表示以红色结点为根，black-height 为 i，internal node 为 j 的方案数。

那么显然有：r_{1, 1} = 1, b_{1, 1} = 1, b_{1, 2} = 2，转移有：

\begin{eqnarray*} r_{x, y} &=& b_{x - 1, i} \cdot b_{x - 1, y - i - 1} \\ b_{x, y} &=& (b_{x - 1, i} + r_{x, i}) \cdot (b_{x - 1, y - i - 1} + r_{x, y - i - 1}) \end{eqnarray*}
  • 因为对于红色结点来说，它的两个孩子必定是黑孩子，至于为什么是从 b_{x - 1, *} 转移过来，回顾定义，我们知道以黑结点为根节点的子树，它的这个黑色的根节点，是不会对black-height作出贡献的，但是当它接在一个红色结点下之后，这个原本是根的黑色结点就会作出贡献。
  • 那么对黑色结点来说，自然它的两个孩子是红是黑无所谓，只要black-height满足即可。

Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 10;
const int mod = 1e9 + 7;
int n, r[N][N], b[N][N];

void chadd(int &x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
}
int gaoR(int x, int y);
int gaoB(int x, int y);

// height x internal node y
int gaoR(int x, int y) {
    if (r[x][y] != -1)
        return r[x][y];
    if (x < 0)
        return 0;
    r[x][y] = 0;
    for (int i = 1; i < y - 1; ++i) {
        chadd(r[x][y], 1ll * gaoB(x - 1, i) * gaoB(x - 1, y - i - 1) % mod);
    }
    //	if (x == 0 && r[x][y]) cout << x << " " << y << " " << r[x][y] << endl;
    return r[x][y];
}

int gaoB(int x, int y) {
    if (b[x][y] != -1)
        return b[x][y];
    if (x <= 0)
        return 0;
    b[x][y] = 0;
    for (int i = 1; i < y - 1; ++i) {
        chadd(b[x][y], 1ll * (gaoB(x - 1, i) + gaoR(x, i)) * (gaoB(x - 1, y - i - 1) + gaoR(x, y - i - 1)) % mod);
    }
    return b[x][y];
}

int main() {
    scanf("%d", &n);
    memset(r, -1, sizeof r);
    memset(b, -1, sizeof b);
    b[1][1] = 1;
    b[1][2] = 2;
    r[1][1] = 1;
    int res = 0;
    for (int i = 10; i >= 0; --i) {
        chadd(res, gaoB(i, n));
    }
    printf("%d\n", res);
    return 0;
}
Last update: May 4, 2022
Back to top