0

RB ツリーが与えられた場合、赤のすべてのノードの子ノードが両方とも黒であることを確認するアルゴリズムを作成する必要があります。

つまり、すべての赤いノードに黒い子しかない場合は true を返し、それ以外の場合は false を返します。

これが私の試みです：

ChildCheck(x){
    if (x.color==black){
        if(x.leftChild !=null or x.leftchild!=nil)
            bool a = ChildCheck(x.leftChild)
        else  a = true
        if (x.rightChild!=null or x.leftchild!=nil){
            bool b = Childcheck(x.leftChild)
        else b = true
        return (a && b)
    }
    else
        if (x.leftChild !=null or x.leftchild!=nil)
            if(x.leftChild.color==black)
                d = true
            else d = false
        else
            d = true
        if (x.rightChild !=null or x.rightchild!=nil)
            if(x.rightChild.color==black)
                e = true
            else e = false
        else
            e = true
        return (d && e)
    }
}

これは正しい答えを返しますか？いいえの場合、何が問題なのですか?

4

1 に答える 1

2 
bool CheckRedProperty(NodePtr root)
{
    if (root == NULL) 
        return true;

    if (!CheckRedProperty(root->left))
        return false;

    if (CheckRedProperty(root->right))
        return false;

    if (root->IsRed() 
        && (root->left && root->left->IsRed() || root->right && root->right->IsRed()))
            return false;
    return true;
}
于 2012-12-12T22:17:00.593 に答える