c - 二分木のルートと葉のパスを比較する方法

Question

特定の赤黒木内のすべての根から葉へのパスを検索しようとしています。特に、rbt が与えられた場合に、すべてのパスに同じ数のブラック ノードがあることをアサートするテストを書きたいと考えていました。

私は2つのグローバル変数でこのようなことを試みていました:

static int count = 0, path = -1;

int check_paths(tree_node t)
{
    if (t == NULL)
    {
        if (path == -1)
            path = count;
        else
            return (path == count);

        return 1;
    }

    if (t->black == 1) ++count;
    int x,y;
    x = check_paths(t->left);
    if (t->black == 1) --count;
    y = check_paths(t->right);

    return (x&&y);
}

ただし、左の枝の黒いノードの右側に赤いノードがある場合、これはカウントが必要以上に減少したことを意味するため、問題がありました。

ルートからリーフへのパスを検索し、特定の値の頻度をカウントしてから、カウントを比較するより良い方法はありますか? あるいは、rbt のバランスをテストするためのまったく別の方法がありますか (つまり、既に作成されていますが、その正確性は不明です)。

Answer 1

(サブ) ツリーを受け取る関数を作成する方法を検討し、(a) バランスが取れている場合は黒の高さを返すか、(b) そうでない場合は負の数を返します。

基本ケースは空の (サブ) ツリーです。単に 0 を返します。

帰納的なケース:

• lh は、左側のサブツリーでの再帰呼び出しの結果です
• lr は、右側のサブツリーでの再帰呼び出しの結果です

lh == lr で、それらが正の場合、黒の場合は lh + 1 を返します

テストされていないコードを次に示します。

int check_paths (tree_node t)
{
    if (t == NULL)
    {
        return 0;
    }
    int lh = check_paths(t->left);
    int rh = check_paths(t->right);

    if (lh != rh || lh < 0)
    {
        return -1;
    }
    else if (t->black == 1)
    {
        return (lh + 1);
    }
    else
    {
        return (lh)
    }
}