2

私の課題は、2-3 ツリーを作成することです。必要なクラスとメソッドをすべて実行しましたが、分割メソッドに問題があります。私はおそらくこのように考えすぎており、頭がぐるぐる回っていて、自分が陥った一連の思考から抜け出すことができないようです.

リーフ ノードを分割するだけでよいのであれば、問題はありません。私の心が行き詰まっているように見えるのは、リーフノードを分割してから、上の親を分割する必要がある場所です。私が理解していることから、子の切断、分割、および子の接続は、最初にどの子が分割されているかによってすべて異なります。

つまり、次のツリーがある場合、最初の分割はリーフ ノードで発生します (たとえば、ルート 13 |14 の 2 番目の子の 3 番目の子)。この分割プロセスは、ルートの 3 番目の子の最初の子 (19 | 20) とは異なります。

                                            9 |18
           3 |  6                          12 | 15                          21 | 24
 1 |  2    4 |  5    7 |  8      10 | 11   13 | 14   16 | 17      19 | 20   22 | 23   25 |26

私が問題を抱えている分割方法の部分は次のとおりです。

    if (upperRight != null)
    {
        if (childIndex == 0)
        {
            parent.connectChild(1, newRight);
            newRight.connectChild(0, child1);
            newRight.connectChild(1, child2);
        }
        else if (childIndex == 1)
        {
            upperRight.connectChild(0, newRight);
        }
        else if (childIndex == 2)
        {
            upperRight.connectChild(0, newRight);
        }
    }
    else
    {
        Node temp = parent.disconnectChild(1);
        parent.connectChild(1, newRight);
        parent.connectChild(2, temp);

        if (childIndex == 0)
        {
            temp = newRight.disconnectChild(0);
            newRight.connectChild(0, child1);
            newRight.connectChild(1, child2);
            newRight.connectChild(2, temp);
        }
        else if (childIndex == 1)
        {
            thisNode.connectChild(1, child1);
            newRight.connectChild(1, child2);
        }
        else if (childIndex == 2)
        {
            temp = newRight.disconnectChild(0);
            thisNode.connectChild(1, child1);
            newRight.connectChild(0, child2);
            newRight.connectChild(1, temp);
        }
    }
    return newRight;

これについて別の考え方をする方法について誰かが私に指示するのを助けることができれば、私はそれを感謝します. 私が受け取っている出力には、子供が間違った順序であるか、どこかで一部の子供を上書きしている、またはその両方があります。

4

1 に答える 1

0

分割を行うのに役立つ 4 つのノードを使用する手法については、Robert Sedgwich による Balancing Search Trees of Algorithms で説明されています。

于 2013-06-06T00:35:58.693 に答える