java - RedBlackTree Mark Allen Weis Remove(x) トップ ボトム アプローチ

Question

ここにあるData Structures and Problem Solving Using Javaの元の Mark Allen Weis RedBlackTree 実装から。

ツリーからノードを削除することに頭を悩ませているようには見えません。ウィキペディアのリソースを読んだ後、「is_leaf()」関数に気付きました..これとマーク・ワイスの実装の問題は、どのノードがリーフで、どのノードがそうでないかを判断する方法がないことです

void delete_one_child(struct node *n)
{
    /*
     * Precondition: n has at most one non-null child.
     */
    struct node *child = is_leaf(n->right) ? n->left : n->right;

    replace_node(n, child);
    if (n->color == BLACK) {
            if (child->color == RED)
                    child->color = BLACK;
            else
                    delete_case1(child);
    }
    free(n);
}

Is_Leaf Java 実装

public boolean isLeaf(){
if(left == null && right == null){
return false;
}
return true;
}

コンソール出力

value=1 color=1 leaf=true left=null right=14
value=2 color=1 leaf=true left=null right=5
value=5 color=0 leaf=true left=null right=null
value=7 color=0 leaf=true left=2 right=11
value=8 color=0 leaf=true left=null right=null
value=11 color=1 leaf=true left=8 right=null
value=14 color=1 leaf=true left=7 right=15
value=15 color=1 leaf=true left=null right=null

ツリー形式 (コンソールから)

└── (1) 1
    └── (1) 14
        ├── (0) 7
        │   ├── (1) 2
        │   │   └── (0) 5
        │   └── (1) 11
        │       └── (0) 8
        └── (1) 15

ルール:

1. 根元が黒い
2. すべての赤いノードには黒い親があります
3. 赤のノードの子はすべて黒 – 赤のノードは赤の子を持つことはできません
4. ルートからリーフへのすべてのパスには、同じ数の黒いノードが含まれます

私の質問は、このRed および Back Trees の実装からの削除をどのように実装するのですか?

Answer 1

これは正しい isLeaf() コードだと思います:

public boolean isLeaf(RedBlackNode<AnyType> t ){
    if(t.left.element == null && t.right.element == null){
        return true;
    }
    return false;
}

Answer 2

isLeaf() の実装方法を尋ねていますか? その場合は、チェックするノードに isLeaf を渡す必要があります。

public boolean isLeaf(RedBlackNode<AnyType> t ){
if(t.left == null && t.right == null){
return false;
}
return true;
}

それ以外の場合、アルゴリズム自体は正しいように見えます。唯一の実際の作業は、C を Java に変換することです。これは簡単です。

Answer 3

nullnode次の代わりに確認する必要がありnullます。

public boolean isLeaf() {
    if(left == nullnode && right == nullnode) {
        return false;
    }
    return true;
}