5種類のデータ構造の二分木の説明

バイナリ ツリーは、最大 2 つの子を持つ各ノードを含む非線形ツリー データ構造です。 バイナリ名は数字の 2 を示唆しているため、どのバイナリ ツリーも左と右の子を持つことができます。

ポインターは、通常はツリーのルートと呼ばれる最上部のノードへのバイナリ ツリーを表します。 バイナリ ツリーのすべてのノードには、データ、左側の子へのポインター、および右側の子へのポインターが含まれます。 二分木を実装するためにポインタが使用されます。 ルート ポインターは、ツリーの最初のノードを示します。 二分木を作成するには、まずノードを作成する必要があります。

データ構造のバイナリ ツリーとは何かを理解したら、バイナリ ツリーで実行される基本的な操作についても知る必要があります。要素の挿入、要素の削除、要素の検索、バイナリ ツリーのトラバースなどの機能を実行できます。

データ構造のバイナリ ツリーは、計算において 2 つの異なる方法で使用されます。まず、各ノードにリンクされた特定のラベルまたは値に応じてノードにアクセスするために使用されます。 次に、関連する分岐構造を持つデータ表現として使用されます。

さまざまな二分木の種類について説明する前に、まず二分木で使用される用語について理解しましょう。

ノード:二分木でデータ値を保持します。

ルート:バイナリ ツリーの最上位ノードは、ツリーのルートと呼ばれます。

サイズ:二分木のノード数を表します。

親ノード:子を持つ二分木内のノード。

子ノード:二分木のルートから離れて移動する親ノードに由来するノードです。

内部ノード:二分木に少なくとも 1 つの子を持つノードです。

葉ノード:子を持たないノードです。または、外部ノードです。

ノード ツリーの深さ:特定のノードのコンテキストで計算されます。これは、特定のノードからルートまでのエッジの数と呼ばれます。

ツリーの内部パスの長さ:バイナリ ツリー内のすべての内部ノードのレベルの合計を指します。

ツリーの外部パスの長さ:バイナリ ツリー内のすべての外部ノードのレベルの合計として定義されます。

ツリーのノードの高さ:特定のノードから二分木の最も深いリーフ ノードまでのエッジの数です。ルートの高さは、バイナリ ツリー内の他のノードの高さよりも常に高くなります。

では、5 種類の二分木の詳細を見てみましょう。

二分木の種類

1.完全二分木

このデータ構造のバイナリ ツリーは、 Proper Binary Tree および Strict Binary Tree という名前でも知られています。 これは、データ構造における二分木の最も基本的なタイプの 1 つです。 フル バイナリ ツリーは、各ノードに 2 つの子があるかまったくないバイナリ ツリーとして定義されます。

これは、リーフ ノードを除くすべてのノードが 2 つの子を含むバイナリ ツリーとしても特徴付けられます。 ルートノードのアドレスが格納されているノードは、ルートの子ノードと呼ばれます。 子を持たないノードは、リーフ ノードと呼ばれます。

木が二分木かどうかを確認するには、すべてのノードを移動する必要があります。 いずれかのノードに子が 1 つある場合、コードは「False」を返します。 すべてのノードに 0 または 2 つの子がある場合、「True」が返されます。

完全二分木のプロパティは次のとおりです。

• リーフ ノードの数は、内部ノードの数 + 1 に等しくなります。たとえば、内部ノードの数が 4 の場合、リーフ ノードの数は 5 に等しくなります。
• ノードの最大数と二分木のノード数は等しくなります。 2h+1 -1 で表されます。
• 完全なバイナリ ツリーのノードの最小数は 2h-1 です。
• 完全なバイナリ ツリーの最小の高さは、log 2 (n+1) – 1 です。
• 完全なバイナリ ツリーの最大の高さは、h = (n+1)/2 です。

2. 完全二分木

完全二分木は、すべてのノードが 0 または 2 つの子を持つ必要があり、各リーフ ノードのレベルが同じである必要がある二分木のタイプの1 つです。 つまり、データ構造の完全な二分木は、すべての内部ノードが 2 つの枝を持ち、枝を持たないノード (リーフ ノード) が同じレベルに存在するツリーとして定義されます。

このコンテキストでは、ノードのレベルはルート ノードからの距離または高さです。 完全な二分木は、最後のレベルも完全に占有されている完全な二分木と見なすことができます。

世界トップクラスの大学が提供するデータ サイエンス コースをオンラインで学びましょう。 エグゼクティブ PG プログラム、上級認定プログラム、またはマスター プログラムを取得して、キャリアを加速させましょう。

3. 完全な二分木

完全なバイナリ ツリーは、データ構造のバイナリ ツリーのタイプの 1 つであり、ツリーのすべてのレベルが完全に満たされています。 二分木の最後のレベルは、完全に埋まっている場合とそうでない場合があります。 ただし、すべてのノードは、ノードの最後のレベルの左端に配置する必要があります。 ノードは左から含める必要があります。

これらは、ノード数とツリーの高さの最適な比率を提供するため、バイナリ ツリーの重要なタイプの 1 つです。

完全なバイナリ ツリーの主要なプロパティは次のとおりです。

• ノードの最大数は 2 h+1 – 1 です。
• ノードの最小数は 2 hです。
• 最小の高さは log 2 (n+1) – 1 です。

4.バランスの取れた二分木

平衡二分木では、木の高さはノードの総数のlog 2です。 木の高さが h で、木のノードの総数が n であるとします。 高さを計算する式は、h = log(n) です。 右サブツリーと左サブツリーの高さの最大差は「1」でなければなりません。

差は、0 や -1 などの他の値を持つことができます。 これらのタイプのバイナリ ツリーは、 AVL ツリーとも呼ばれます。 バランスのとれた二分木のよく知られた例の 1 つは、赤黒木です。

次のコードを実装して、バランスのとれた二分木を実行できます。

プライベート クラス ノード {

プライベート int 値;

プライベート ノードが残されました。

プライベートノードの権利;

}

public boolean isBalanced(Node n) {

if (balancedtreeHeight(n) > -1)

true を返します。

false を返します。

}

public int BalancedtreeHeight(ノード n) {

もし (n == null)

0 を返します。

int h1 = BalancedtreeHeight(n.right);

int h2 =balancedtreeHeight(n.left);

もし (h1 == -1 || h2 == -1)

-1 を返します。

if (Math.abs(h1 – h2) > 1)

-1 を返します。

もし (h1 > h2)

h1 + 1 を返します。

h2 + 1 を返します。

}

米国をチェック - データサイエンスプログラム

5. 縮退二分木

縮退二分木は、あまり使用されないタイプの二分探索木の1 つです。 これは、各ノードが 1 つの子、つまり左または右の子のみを持つバイナリ ツリーです。 左右両方の子を持つノードはありません。

人気のある米国 - データ サイエンスの記事を読む

結論

二分木をさまざまな用途に使用するには、データ構造の中で二分木とは何かを理解することが不可欠です。 二分木にさまざまな関数を実装すると、データを効率的に整理して保存するのに役立ちます。

複数のタイプのバイナリ ツリーを調べると、時間の複雑さでより効果的に操作を実行するのに役立ちます。バイナリ ツリー データ構造を含むデータ サイエンスの基礎は、データ サイエンスの旅を簡単に始めるのに役立ちます。その後、高度なデータ サイエンス プロジェクトに取り組み、スキルとポートフォリオを強化することができます。

upGrad で機械学習の旅を始めましょう

データ サイエンスを学びたい場合は、upGrad のMaster of Science in Data Scienceプログラムを追求できます。 この 24 か月のコースでは、Python、ML モデルのデプロイ、Spark を使用した BD 処理、予測分析と統計、教師ありおよび教師なし ML モデルなどのスキルを習得します。 このコースは、野心的なマネージャー、MBA 卒業生、エンジニア、さまざまな分野の専門家に適しています。

このコースを修了すると、データ エンジニア、ビッグ データ アナリスト、機械学習エンジニア、データ サイエンティストとして働くことができます。