1

二分木で作られたヒープがあります。配列ではありません。これをどのように並べ替えればよいか、考えてみました。最後のノードを取得してルートに配置し、ダウン ヒープ バブルを実行する必要があることはわかっています。私が持っているこの部分。私が抱えている問題は、新しい最後のノードを取得する方法を知っていることです。最後のノードを見つけるアルゴリズムはありますか? 各ノードの各親ノードを追跡する必要がありますか?

ありがとう。

4

1 に答える 1

2

開始するツリーが完全なツリーであると仮定すると、各ノードの高さを追跡できるかどうかがわかります。

次に、削除する次の子を探してツリーを反復処理するときに、各ノードでチェックを行います。Lh > Rh の場合は左に進み、そうでない場合は右に進みます。このアイデアに関する唯一の注意点は、そのノードを取得するときにすべての高さを更新する必要があるということです。O（log n）のコストが追加されます。しかし、theta(log n) であるツリーをたどっているので、漸近的にはそれほど大きな問題ではありません。

于 2011-02-23T04:32:10.587 に答える