algorithm - 子孫の葉へのすべてのパスのノードの黒の高さを確認する方法は?

Question

赤黒の木が与えられた場合、各ノードについて、ノードから子孫の葉までのすべてのパスに同じ数の黒ノードが含まれているかどうかをチェックする効率的なアルゴリズムを作成する必要があります。つまり、プロパティが true の場合、アルゴリズムはブール値を返す必要があります。それ以外の場合は false。

Answer 1

RB ツリーの黒の高さを返します。高さが 0 の場合、ツリーは無効な赤黒ツリーです。

int BlackHeight(NodePtr root)
{
    if (root == NULL) 
        return 1;

    int leftBlackHeight = BlackHeight(root->left);
    if (leftBlackHeight == 0)
        return leftBlackHeight;

    int rightBlackHeight = BlackHeight(root->right);
    if (rightBlackHeight == 0)
        return rightBlackHeight;

    if (leftBlackHeight != rightBlackHeight)
        return 0;
    else
        return leftBlackHeight + root->IsBlack() ? 1 : 0;
}

Answer 2

以下のコードは、任意のパスに沿った黒いノードの数が同じかどうかを検証します

#define RED 0
#define BLACK 1

struct rbt {
    int data;
    struct rbt *left;
    struct rbt *right;
    int parent_color; // parent link color
    uint64_t nodes_count; // to store number of nodes present including self
    int level; // to store level of each node
};
typedef struct rbt rbt_t;

int check_rbt_black_height(rbt_t *root)
{
    if(!root) return 1;
    else {
        int left_height  = check_black_violation(root->left);
        int right_height = check_black_violation(root->right);
        if (left_height && right_height && left_height != right_height) {
            printf("Error: Black nodes are not same @level=%d\n", root->level);
            exit(1);
        }
        if (left_height && right_height) 
                   // do not increment count for red
            return is_color_red(root) ? left_height : left_height + 1; 
        else
            return 0;
    }
}

int is_color_red(rbt_t *root)
{
    if(root && root->parent_color == RED) return 1;
    return 0;
}