0

Red Black Tree を Java で実装するように依頼されましたが、これがどのように行われるのか正確にはわかりません。r/b ツリーの実装について、私のノード クラスについて誰かがコメントしてくれると本当にうれしいです。どうぞ：

public class RBTnode {

public RBTnode(int key, RBTnode left, RBTnode right) {
    /* this is the constructor for a root node */
    color = 0;
    parent = null;
    key = this.key;
    left = this.left;
    right = this.right;
}

public RBTnode(int key, RBTnode left, RBTnode right, RBTnode parent, int color ) {
    key = this.key;
    color = this.color;
    left = this.left;
    right = this.right;
    parent = this.parent;

}

int color; // 0 black, 1 red
int key;
RBTnode parent;
RBTnode left;
RBTnode right;

}

4

1 に答える 1

1

私は自分で RB ツリーを作成したことはありませんが、現在それらについて学んでいます。聞いたところによると、調整が必要なようです。

RB ツリーを RB ツリーにするためには、次の規則に従う必要があります。

  • すべてのノードが赤または黒
  • ルート ノードは常に BLACK です
  • 新しいノードは常に赤です
  • RED ノードの両方の子は BLACK です。
  • ルートからリーフ、または null の子へのすべてのパスには、同じ数の黒いノードが含まれている必要があります。

そうは言っても、2 番目のコンストラクターは必要ないと思います。なぜなら、常に新しいノードを RED に初期化するからです。

于 2012-04-17T18:35:27.860 に答える