ビデオ: Week 8 2024
特別な種類のツリー構造は、 バイナリヒープ であり、各ノード要素を特別な順序で配置します。検索ツリーを使用すると、データをすばやく検索できます。データ項目を取得し、ツリーにソートされた順番に並べ、ツリーを検索することは、情報を見つけるためのより速い方法の1つです。
バイナリヒープでは、ルートノードには常に最小値が格納されます。ブランチを表示すると、上位ブランチは常に下位ブランチとブランチよりも小さい値になります。その効果は、探索が非常に効率的になるように、樹木のバランスをとって予測可能な順序に保つことです。コストは木のバランスを保つことにあります。
<！ - 1 - >アプリケーションが行うすべてのタスクのうち、検索には時間がかかり、必要なものも多くなります。データの追加（および後での並べ替え）には時間がかかりますが、データセットの作成と保守の利点は、データセットを使用して有益な作業を実行することにあります。したがって、効率の低いCRUD機能や最適化されていないソートルーチンを使用することもありますが、可能な限り効率的に検索を進める必要があります。唯一の問題は、すべてのタスクを絶対効率で実行する検索はないため、検索ルーチンの一部として期待していることに基づいてオプションを評価する必要があります。
<！より効率的な検索方法の2つに、バイナリ検索ツリー（BST）とバイナリヒープの使用があります。両方の検索手法は、データ要素にアクセスするために使用されるキーを保持するためにツリー状の構造に依存しています。しかし、2つの方法の配置が異なっているため、特定のタスクを実行するときに他の方法よりも利点があります。この図は、BSTの配置を示しています。<！ - 3 - >
BSTを使用するときのキーの配置。
バイナリヒープを使用する場合のキーの配置。
バイナリミニヒープ を作成することもできます。ここでは、ルートに最も低いキー値が含まれ、各レベルはより高い値になり、最も高い値がリーフの一部として表示されます。前述のように、BSTには、検索を実行する際にバイナリヒープに比べていくつかの利点があります。以下のリストは、これらの利点のハイライトのいくつかを提供します： 要素を検索するには、バイナリヒープのO（n）時間とは対照的に、O（log n）時間が必要です。 要素を順番に印刷するには、バイナリヒープのO（n log n）時間とは対照的に、O（log n）時間だけが必要です。 床と天井を見つけるにはO（log n）時間が必要です。
K番目の最小/最大要素を見つけるには、ツリーが適切に構成されているときにO（log n）時間が必要です。
- これらの時間が重要かどうかは、アプリケーションによって異なります。 BSTは、検索に時間を費やし、ツリーを構築する時間が短い状況で最も効果的です。バイナリヒープは、キーが定期的に変更される動的な状況で最適に動作する傾向があります。
- バイナリヒープは配列に依存するため、必要な構造を作成するために必要なリソースが少なくて済みます。
- バイナリヒープを構築するには、O（n）時間が必要であり、BSTとは対照的であり、O（n log n）時間が必要です。
- ポインタを使ってツリーを実装する必要はありません。バイナリヒープの変化（例えば、フィボナッチヒープ）に依存することは、O（1）時間のキー時間の増減などの利点を提供する。
