0

私はいくつかの個人的な調査を行っていますが、（おそらく非常に大きな）データツリー内のデータを効率的に変更する必要があることに気付きました。データは単純なデータ、整数または場合によっては小さなオブジェクトで構成されます。ツリーを解析している間、すべての同様のオブジェクトを変更する必要があります（ただし、サブツリー内のオブジェクトのみ）。これは説明が少しわかりにくいので、例として画像を追加しました。

例

上の画像では、文字はデータの値を表し（同一の文字は同一のデータを表します）、括弧内の数字は一意の値であるため、参照できます。

したがって、ツリーを解析していて、現在ノード2にいるとします。「a」の値を変更して「g」に変更する必要があると判断しましたが、現在のノードとすべての子のみを変更したいと思います。 。（したがって、2と9は「g」に変更され、1と7は「a」のままになります）。すべての子を再帰的に検索して手動で変更することはできますが、ツリーが非常に大きくなる可能性があります。aのすべての値を変更したい場合は、データをダブルポインターとして格納し、ポインターが指す値を変更するだけで済みます。だから私の質問は、おそらく一定の時間で、私が望む方法でデータを変更するための既知の方法はありますか？

4

1 に答える 1

0

私がそれをする方法は、木に挿入することです。

ノードのクラスを作成する

class node
{
    node* dataParent;
    CustomType* value;
    // put regular tree pointers here
}

次に、トラバースしながら挿入すると、dataParentは同一のデータを持つ最後の親を指します。同一の親がない場合、それはnullになり、値はnullになりません。同一の親がある場合、値はnullになり、カスタムの親に何かが含まれます。ただし、取得は一定の時間ではありません。値がnullでなくなるまでトラバースする必要があります。

これが私が考えることができる最良の方法です。少なくともlognithinkです。久しぶりです。

1つは、挿入にコストがかかることです。

于 2012-09-27T03:24:48.910 に答える