5

私は大学でアルゴリズムのコースを取っています。私のプロジェクトの 1 つで、C# で赤黒木を実装したいと考えています (実装自体はプロジェクトではありませんが、私を助けるために選択したものです)。 .

私の赤黒ツリーは文字列キーを保持する必要があり、各ノード用に作成したオブジェクトは次のようになります。

class sRbTreeNode
{
    public sRbTreeNode Parent = null;
    public sRbTreeNode Right = null;
    public sRbTreeNode Left = null;
    public String Color;
    public String Key;

    public sRbTreeNode()
    {
    }

    public sRbTreeNode(String key)
    {
        Key = key;
    }
}

ツリーの印刷、ルートの検索、最小/最大キー (アルファベット順) などの基本的なメソッドを既に追加しました...

ノードの挿入に問題があります (したがって、ツリーを構築します)。赤黒木に詳しい人なら誰でも、片側にノードを追加すると、木のバランスが変わる可能性があることを知っています。これを修正するには、ツリーのバランスを取るために、ツリーのノードを中心に「回転」する必要があります。

RightRotate メソッドと LeftRotate メソッドを疑似コードで作成し、C# で実装しようとしたときに、作成した sRbTreeNode オブジェクトで一連の参照の問題に遭遇しました。

これは、LeftRotate メソッド用に作成した疑似コードです。

LeftRotate(root, node)
    y <- node.Right;
    node.Right <- y.Left;
    if (y.Left != null)
        y.Left.Parent <- node;
    y.Parent <- node.Parent;
    if (node.Parent = null)
        root <- y;
    else
        if (node = node.Parent.Left)
            node.Parent.Left = y;
        else
            node.Parent.Right = y;
    y.Left <- node;
    node.Parent <- y

最初に試した「ref」キーワードを使用せずに、直接実装するという提案を受けました。これが私がやった方法です：

public static void LeftRotate(sRbTreeNode root, sRbTreeNode node)
    {
        sRbTreeNode y = node.Right;
        node.Right = y.Left;
        if (y.Left != null)
            y.Left.Parent = node;
        y.Parent = node.Parent;
        if (node.Parent == null)
            root = y;
        else
            if (node == node.Parent.Left)
                node.Parent.Left = y;
            else
                node.Parent.Right = y;
        y.Left = node;
        node.Parent = y;
    }

今、デバッグすると正常に動作することがわかりますが、このメソッドに渡すオブジェクトはメソッドの範囲内でのみ回転されます。このメソッドを終了すると、実際のノードには変更がないように見えます。それが、最初に「ref」キーワードを使用することを考えた理由です。

私は何を間違っていますか？

4

3 に答える 3

2

メソッドの本体でこれを行うため：

root = y;

修飾子rootで渡す必要があります。別の ndoe を指すようにそれ自体が更新されることはないため、必要ありません。.refnodenode

于 2010-02-12T14:35:55.290 に答える
1

参照で問題が発生する理由がわかりません。左/右/親ノードは、この疑似コードのようにコピーできます。

「ref」キーワードを使用していない限り、大騒ぎせずに C# に展開できるはずです。その場合、予測できない結果が生じる可能性があります。

おそらく、これまでに実際に作成したコードを見せていただければ、デバッグをお手伝いできます。

于 2010-02-12T13:06:12.007 に答える
1

私の推奨事項：

  • 親ポインターを含めないでください。これらは挿入または削除アルゴリズムにとって必須ではなく、コードをより複雑にします。たとえば、LeftRotate1 つのパラメーターだけで記述でき、親ポインターを使用しない場合は約半分の長さになります。
  • ではなくプロパティにを使用enumし、コンストラクターで初期化します。Colorstring
  • まだ読んでいない場合は、この記事を読んでください。
于 2010-02-12T13:06:50.713 に答える