tree - ヒープが完全な二分木になるのはいつですか?

Question

ヒープは常に完全な二分木であることを知っています。しかし、いつヒープが完全な二分木になるのだろうか? ヒープが常に完全な二分木になるためには、どのような条件が必要ですか?

Answer 1

ヒープ条件が重要ではない理由を示すために、各ノードにその高さを割り当てるだけで、ヒープ条件を満たす任意のバイナリ ツリーに簡単にラベルを付けることができると考えてください。(一意のラベルが必要な場合は、ツリーをトポロジ的に並べ替えて、ルートからカウントを開始できます。)

したがって、完全性と完全性は、ヒープの直交概念でもあります (完全、完全、両方、またはどちらでもないツリーの例については、こちらを参照してください)。

ただし、多くの場合、ヒープの実装では、結果のバイナリ ツリーが完全になるような方法でヒープの状態を確保することを選択します。通常のバイナリ ヒープを実装する標準的な方法は、配列を使用し、それを左から右に暗黙のバイナリ ヒープで埋めることです (これは通常、ヒープソートが実装される方法です)。

これが参照しているヒープの種類である場合、常に左から右に一度に 1 レベルずつツリーを埋めるため、制約が大幅に厳しくなります。そのようなツリーが完全である理由は明らかです (最後のレベルを除くすべてのレベルが常に完全に満たされています)。

また、満杯と満杯でないことを常に交互に繰り返すことも容易にわかるはずです。

• ルートしかない場合は、いっぱいです。
• 完全なツリーにノードを追加すると、必然的にその親には 1 つの (左側の) 子しかないため、ツリーは完全ではなくなります。
• ツリーが満杯ではない場合、前のステップで左の子を与えた親の (右の) 子として挿入されるため、次の挿入で再び満杯になります。