C++ のバイナリヒープとバイナリ検索ツリー-C++-php.cn

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

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

1. バイナリヒープ

1.1 概念

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

1.1.1 ヒープの順序性

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

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

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

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

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

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

ログイン後にコピー

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

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 類似点

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