二分木と二分探索木：二分木と二分探索木の違い

序章

並べ替えは、データをより効果的に分析できるように体系的な順序でデータを配置するプロセスです。 特定のレコードを識別するプロセスは、検索と呼ばれます。 データが特定の順序で適切に並べ替えられている場合、検索は簡単で効率的なタスクになります。 この記事では、最も重要な非線形データ構造の1つ、つまりツリーについて説明します。

ツリーは主に、要素間の階層関係を示すことによってデータを表すために使用されます。 たとえば、目次、家系図。 技術的には、ツリーは、ノードがツリーのルートとして割り当てられ、他のノードがn> = 0の互いに素なセットT1、T2、T3、 T4…。 Tnは、そのルートノードのサブツリーまたは子として呼び出されます。

二分木とは何ですか？

二分木は非線形データ構造であり、ノードは0、1、または2つのノードを持つことができます。 二分木の各ノードは、親ノードまたは子ノードと呼ばれます。 バイナリツリーの最上位ノードは、ルートノードと呼ばれます。 各親ノードには、左側の子ノードと右側の子ノードの最大2つの子ノードを含めることができます。

二分木のノードには、次の3つのフィールドがあります。

1. データ要素–ノードによって保存されるデータ値を保存します。
2. 左の子へのポインタ–左の子ノードへの参照（またはアドレス）を格納します。
3. 右の子へのポインタ–右の子ノードへの参照を格納します。

このようにして、複数のノードが結合されてバイナリツリーが構築されます。

二分木は次のように表すことができます。

ソース

上の図から、ルートノード2には7と5の2つの子（または子ノード）があります。7は左子ノードと呼ばれ、5は右子ノードと呼ばれます。 このように、各子ノードは他のいくつかのノードの親ノードとして機能し、一緒にバイナリツリーを表します。

チェックアウト：二分木の種類

二分木で使用される用語

ノード：ツリー内の終点の基本的な表現。

ルートノード：バイナリツリーの最上位ノード。

親ノード：ノードがエッジを介して別のノードに接続されている場合、それは親ノードと呼ばれます。 二分木では、親ノードは最大2つの子ノードを持つことができます。

子ノード：ノードに先行ノードがある場合、それは子ノードと呼ばれます。

リーフノード：子ノードを持たないノードは、リーフノードと呼ばれます。

ノードの深さ：ルートノードから、深さが測定される特定のノードまでの距離です。

木の高さ：ルートノードからリーフノードまでの最長距離です。

これらは、バイナリツリーのいくつかの基本的な用語です。 バイナリツリーのこの基本的な理解を持って、バイナリ検索ツリーとして知られているバイナリツリーの進歩に移りましょう。

また読む：二分探索アルゴリズム：機能、利点、時間と空間の複雑さ

二分探索木とは何ですか

名前が示すように、バイナリ検索ツリーまたはBSTは、データの並べ替え、取得、および検索に使用されるツリーです。 これは、ノードが特定の順序で配置されている一種の非線形データ構造でもあります。 したがって、「順序付き二分木」とも呼ばれます。 次のプロパティがあります。

• ノードの左側のサブツリーには、そのノードのキーよりも小さいノードしかありません。
• ノードの右側のサブツリーには、そのノードのキーよりも大きいノードがあります。
• 各ノードには個別のキーがあり、バイナリ検索ツリーでの重複は許可されていません。
• 左右のサブツリーも二分探索木である必要があります。

この概念を視覚化して、二分探索木を明確に理解しましょう。

ソース

上の図では、ルートノードの値が8であることがわかります。さらに詳しく調べると、左側のサブツリーのすべての値がルートノードの値よりも小さく、右側のサブツリーのすべての値がルートノードより大きい値。 さらに、二分探索木の各値は一意であり、重複がないことに注意してください。 したがって、上記の二分探索木の特性が検証されます。

さらに別の例では、左右のサブツリーは、ツリー全体で一意の値を持つ二分探索木であることがわかります。 左側のサブツリーのリーフノードの値は12であり、ルートノードの値である12よりも大きくなっています。したがって、これはBSTのプロパティを満たさないため、二分探索木ではありません。

BSTでの検索操作–

以下に示す値を持つ二分探索木を考えてみましょう。 二分探索木から9を取得するために検索操作がどのように実行されるかを理解しましょう。

ソース

二分探索を実行するために、最初にすべての整数をソートされた配列に配置します。 これは検索空間と呼ばれます。 このサーチスペースは、開始ポインタと終了ポインタと呼ばれる2つのポインタで構成されます。 上記の二分探索木の配列は次のように表されます。

最初のステップは、配列の中央の値を計算し、それを検索する値（この場合は9）と比較することです。 これは、n / 2を計算することによって行われます。ここで、nは配列内の要素の総数（BST）であり、6です。したがって、3番目の要素は中央の要素である5です。

真ん中の要素が9と比較され、等しくない（大きい）ため、検索操作は右側の配列で実行されます。 このようにして、以下に示すように、検索操作が半分になります。

次のステップでは、中央の要素が計算され、9であることがわかります。これは、検索する要素と一致します。

二分木と二分探索木–

二分木と二分探索木の両方の基本的な理解ができたので、両方の違いのいくつかを簡単に要約しましょう。

結論

したがって、バイナリツリーとバイナリ検索ツリーはどちらもノードのコレクションを持つ共通の階層構造を持っていますが、アプリケーションにはいくつかの違いがあると推測されます。 二分木は基本的な構造であり、親が2つを超える子を持つことはできないという単純なルールがありますが、二分探索木は、ノードを編成する特定の順序に従った二分木の変形です。

二分木と二分探索木について知りたい場合は、IIIT-BとupGradのデータサイエンスのPGディプロマをチェックしてください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界とのメンターシップを提供します。専門家、業界のメンターと1対1で、400時間以上の学習とトップ企業との仕事の支援。

世界のトップ大学からオンラインでデータサイエンスコースを学びましょう。 エグゼクティブPGプログラム、高度な証明書プログラム、または修士プログラムを取得して、キャリアを早急に進めましょう。