再帰的なスプレー ツリーをボトムアップで実装しようとしています。展開する必要があるノードまで再帰的に下に移動し、そのノードの親と祖父母を見つけます。その後、状況に応じてジグザグまたはジグジグのいずれかをうまく実行できます。問題は、これが完了した後、一度表示されたノードを前の再帰呼び出しに戻すことです。以前の再帰呼び出しは、現在そのノードの子であるノードの親を参照しています。上に行くにつれてノードを上に再帰するにはどうすればよいですか?
1437 次
2 に答える
1
私が正しく思い出せば、ターゲットノードに戻るときに左右のツリーを構築します。ターゲットを見つけたら、ターゲットの（元の）子を使用して最終的な左右のツリーを構築し、結果のツリーをターゲットの新しい子としてアタッチし、結果を末尾再帰的に返します（つまり、すべてのさらに変更せずにスタックをバックアップします）。
于 2010-03-04T08:07:13.037 に答える
0
ツリーが完全に「不均衡」になり、非常に大きくなると（たとえば、100000 intキーなど）、再帰的アルゴリズムによってスタックオーバーフロー例外がスローされる場合があります。親または祖父母を取得するには、各ノードで親ポインターを使用することをお勧めします。これはそれを行う1つの方法です。私のためにうまくいった。
ランタイムの結果は、ここで明らかです。スプレーツリーランタイムプロファイリング
于 2012-01-18T03:49:03.030 に答える