0

私は、拡張された赤黒木に挿入するコードを見ています。このツリーには「サイズ」と呼ばれる追加のフィールドがあり、ノードxをルートとするサブツリーのサイズを維持します。新しいノードを挿入するための擬似コードは次のとおりです。

AugmentedRBT_Insert(T,x){
    BST_Insert(T,x); //insert as if it is a normal BST
    x[color]=red; //insert as a red node
    size[x]=1;
    tmp=parent[x];
    while(tmp!=NULL){   //start from the node x and follow the path to root
        size[tmp]=size[tmp]+1;  //update the size of each node
        tmp=parent[tmp];
    }
}

色と回転を修正することを忘れてください、それらは別の機能で行われます。私の質問は、なぜ新しく追加されたノード「x」のサイズを1に設定するのですか？サブツリーがないことを理解しているので、サイズは1でなければなりませんが、RBTの要件の1つは、すべての赤いノードに2つの黒い子があることです。実際、すべてのリーフノードはNULLであり、ノード「x 「黒として、それでも2つの黒のNULLノードが必要であり、サイズを3に設定する必要があると思いますか？私が間違っている？

ありがとう。

4

1 に答える 1

1

ほとんどの二分木と同様に、赤黒木への挿入は葉で直接行われます。したがって、葉をルートとするサブツリーのサイズは1です。葉には常に子として「ルート」または「nil」（黒）があるため、赤いノードには2つの黒の子があります。これらのnull要素はノードではないため、カウントしません。

次に、ルートまでのすべての親のサイズを調整します（追加したノードの場合、それぞれが+1になります）。

最後に、必要に応じて、ツリーを回転させてバランスを取るときに、これらの値を修正します。実装では、サイズの更新と回転の両方を2回ではなく1回のパスで実行することをお勧めします。

于 2013-03-23T23:09:18.360 に答える