C++ のバイナリ ヒープとバイナリ検索ツリー

C プログラミングでは、バイナリ ヒープとバイナリ検索ツリーはよく使用される 2 つのデータ構造であり、類似点もありますが、相違点もあります。この記事では、バイナリ ヒープとバイナリ サーチ ツリーの概念、基本操作、および応用シナリオをそれぞれ紹介します。

1. バイナリ ヒープ

1.1 概念

バイナリ ヒープは、次の 2 つの特性を満たす完全なバイナリ ツリーです:

1.1.1 ヒープの順序性

ヒープの順序性とは、バイナリ ヒープ内で、各ノードの値がその親ノードの値より大きくない (または小さくない) ことを意味します。ここでは例として最大ヒープを取り上げます。つまり、ルート ノードの値がツリー全体で最大の値であり、すべての子ノードの値がルート ノードの値以下になります。

1.1.2 完全なバイナリ ツリー プロパティ

最下層を除き、他のすべての層を塗りつぶし、すべてのノードを左に揃える必要があります。

ここでは、最大ヒープを表すために次の配列が使用されています:

[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]

対応するヒープは次のとおりです:

16

/
14 10
/ /
8 7 9 3
/
2 4

1

1.2 基本操作

1.2.1 挿入操作

バイナリ ヒープに新しい要素を挿入する操作では、「シフトアップ」メソッドを使用して調整を行います。

• 新しい要素をヒープの一番下の左端の空きスペースに挿入します。
• 新しい要素の値がその親ノードよりも大きい場合は、新しい要素とその親ノードを比較します。親ノード ノードの方が大きい場合は、2 つの要素の位置を交換し、新しい要素が親ノードより大きくなくなるか、ヒープの先頭に達するまでこのプロセスを繰り返します。

1.2.2 削除操作

バイナリ ヒープ内のヒープの先頭要素を削除する操作は、「ふるい分け」メソッドによって調整されます。

• ヒープの一番上の要素をヒープの一番下の右端の要素と交換します;
• ヒープの元の一番上の要素を削除します;
• ヒープの新しい一番上の要素を追加します比較し、その値が子ノードの最大値より小さい場合は、子ノードの最大値と交換し、ヒープ順序が満たされるまでこのプロセスを繰り返します。

1.3 アプリケーション シナリオ

バイナリ ヒープは、優先キューやヒープ ソート、topK 問題などのヒープ ベースのソート アルゴリズムを実装するためによく使用されます。

2. 二分探索ツリー

2.1 概念

二分探索ツリー (BST) は、次の特性を満たす順序付きツリーです:

2.1.1左側のサブツリー上のすべてのノードの値は、そのルート ノードの値よりも小さくなります。

2.1.2 右側のサブツリー上のすべてのノードの値が、そのルート ノードの値よりも大きくなります。

2.1.3 左側と右側のサブツリーもそれぞれ二分探索ツリーです。

次のツリーを例に挙げます。

    6
  /   
 2     7

/
1 4 9

   /    /
  3   5 8

これは二分探索ツリーです。

2.2 基本操作

2.2.1 検索操作

二分探索木でノードを見つける操作。その本質は、ノードの値を継続的に比較することです。現在のノード値のサイズで検索し、左/右のサブツリーに沿って再帰的に検索します。

2.2.2 挿入操作

二分探索木に新しいノードを挿入する操作では、ルート ノードから開始して挿入する位置を見つける必要があります。二分探索木のプロパティを満たす必要があります。

2.2.3 削除操作

二分探索木内のノードを削除する操作は、次の 3 つの状況に分類できます。

• 削除されるノードは次のとおりです。リーフ ノードの場合は、直接削除してください。
• 削除対象のノードに子ノードが 1 つしかない場合は、そのノードをその子ノードに置き換えます。
• 削除対象のノードに子ノードが 2 つある場合ノードの場合は、このノードを使用します。 右のサブツリーの最小のノードがノードを置き換え、ノードの右のサブツリーの最小のノードが削除されます。

2.3 アプリケーション シナリオ

二分探索ツリーは、辞書や記号テーブルなどの検索および挿入操作を伴うシナリオの実装によく使用され、検索パフォーマンスはデータの分散に関係します。

3. バイナリ ヒープとバイナリ検索ツリーの比較

3.1 類似点

バイナリ ヒープとバイナリ検索ツリーはどちらもバイナリ ツリーであり、同じ特性のいくつかを持っています。

##ルート ノードの初期位置は任意のノードにすることができます。
• は優先キューの実装に使用できます。
• #挿入と削除の時間計算量は等しいです。 O(ログン)。

3.2 相違点

バイナリ ヒープとバイナリ検索ツリーの間には、明らかな相違点もいくつかあります。

3.2.1 データ分散

バイナリ ヒープでは、要素は規則性なくノード間で分散されます。必要なのは、各ノードがヒープの順序を満たすことだけを確認することだけです。バイナリ サーチ ツリーでは、要素のサイズには特定の並べ替え規則があります。つまり、次の条件を満たします。左が小さく右が大きいという性質。

3.2.2 最小値/最大値へのアクセス

バイナリ ヒープでは、最大値/最小値は O(1) でアクセスできます。つまり、ルート ノードで取得されます。要素の時間計算量は O(logn) です。二分探索ツリーでは、最小値/最大値を見つけるにはサブツリーを走査する必要があり、時間計算量も O(logn) です。

3.2.3 削除操作と挿入操作

バイナリ ヒープでは、各削除操作と挿入操作はヒープ順序、つまり O(logn) の時間計算量に従う必要があります。二分探索木では、ノードの検索と新しいノードの挿入の時間計算量は木の高さに関係するため、最悪の場合、時間計算量は O(n) になる可能性があります。

3.3 選択に関する提案

バイナリ ヒープとバイナリ検索ツリーを選択するときは、アプリケーション シナリオの特定の条件に基づいて選択する必要があります。

最小値/最大値をすぐに取得する必要があり、要素のサイズに特別な要件がない場合は、バイナリ ヒープを優先できます。

要素を迅速に挿入/削除する必要があり、要素のサイズに特定の並べ替えルールが必要な場合は、二分探索ツリーの選択を検討できます。

4. 結論

要約すると、バイナリ ヒープとバイナリ検索ツリーはどちらも比較的重要なデータ構造であり、さまざまなシナリオでそれぞれ利点と欠点があります。バイナリ ヒープとバイナリ検索ツリーの概念、基本操作、アプリケーション シナリオを理解することは、効率的なプログラムを作成する上で非常に重要です。

以上がC++ のバイナリ ヒープとバイナリ検索ツリーの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。