データ構造の二分木：プロパティ、タイプ、表現、利点

さまざまなタイプのデータ構造の中には、他のほとんどのタイプよりも多くの用途がある二分木があります。 彼らの最も注目すべきアプリケーションには、ピアツーピアプログラミング、検索、暗号化、他よりも高い帯域幅のネットワークルーター、および3Dビデオゲームが含まれます。 ここで、データサイエンスの二分木とは何か、それらのタイプは何か、そしてそれらはどのように表現されるかについて詳しく説明します。

二分木とは何ですか？

以前に通常のツリーで作業したことがあるか、その基本を知っている場合は、さまざまなノードがこれらのツリーに持つことができる子の数に関しては制限がないことをご存知でしょう。 この意味で二分木は少し異なります。 二分木のすべての親またはノードは、最大2つの子を持つことができます。

バイナリツリーのすべてのノードには、3つの主要なコンポーネントがあります–

• データ要素
• 正しい参照
• 左の参照

ツリーの最上位にあるノードは、ルートノードと呼ばれます。 親ノードは子を持つノードです。 子ノードと親ノードは、参照を介して相互に接続されています。 子を持たないノードは、リーフノードと呼ばれます。

二分木のノードには、1つの子、2つの子、またはまったく子がない可能性があることは明らかです。 二分木は、キュー、配列、スタック、リンクリストなどの線形データ構造ではありません。 代わりに、それらは階層データ構造です。

チェックアウト：初心者向けのデータサイエンスプロジェクトのアイデア

二分木のノードの重要なプロパティ

これらのプロパティをよりよく理解すると、二分木に関するこの議論を最大限に活用するのに役立ちます。 さまざまなノードの深さは、ルートを特定のノードに接続する途中に存在するノードの数として定義されます。 そのため、ルートノードの深さは0です。一方、バイナリツリー内のさまざまなノードの高さは、特定のノードとルートノードを接続するパスにあるノードの数です。 そのため、葉のノードの高さは0です。

はっきりとわかるように、ノードの深さは、ルートノードから開始して、そのノードに到達するまで下がることによって測定されます。 一方、高さの計算に関しては、問題のノードから開始して、ルートノードに向かって進みます。 どちらの場合も、0から開始します。0からではなく1から高さと深さを測定する人もいます。これは間違いではなく、さまざまな人が好むものです。

これで、ノードの最大深度が二分木の深度として定義されます。 同様に、ノードの最大の高さは、二分木の高さとして定義されます。 したがって、二分木の高さと深さは常に同じです。

詳細： Pythonのデータ構造とアルゴリズム

二分探索木とは何ですか？

二分探索木は、他のすべての種類の二分木の中で最も一般的です。 これは特殊な二分木であり、他の形式の二分木とは異なり、より便利なプロパティが付属しています。 二分探索木またはBSTとは正確には何ですか？ その名前が示すように、ツリー内のデータを検索するために二分探索木が使用されます。

BSTには、効率的な検索を容易にするプロパティが付属しています。 BSTは、右側のサブツリーのノードと左側のサブツリーのノードよりも小さいノードと大きいノードのキーを持つ二分木です。

二分木の表現

1.リンクされた表現

リンク表現の二分木は、リンクリストとしてメモリに保存されます。 これらのリストには、隣接または隣接するメモリ位置に格納されておらず、ツリーに関連付けられた親子関係を介して相互にリンクされているノードがあります。

この表現では、各ノードには3つの異なる部分があります–

• 右ノードを指すポインタ、
• 左ノードを指すポインタ、
• データ要素。

これは、より一般的な表現です。 すべての二分木は、ルートノードの方向を指すルートポインタで構成されます。 ルートノードがnullまたは0を指しているのを見ると、空の二分木を扱っていることがわかります。 右と左のポインタは、ツリーの右と左の子のアドレスを格納します。

2.順次表現

リンクされた表現よりも単純ですが、その非効率性により、2つの二分木表現はあまり好ましくありません。 非効率性は、さまざまなツリー要素を格納するために必要なスペースの量にあります。 順次表現は、ツリー要素の格納に配列を使用します。

二分木が持つノードの数は、使用される配列のサイズを定義します。 二分木のルートノードは、配列の最初のインデックスにあります。 特定のノードが格納されるインデックスは、ノードの右と左の子が格納されるインデックスを定義します。 空のツリーの最初のインデックスはnullまたは0です。

二分木の種類

1. 完全な二分木：完全な二分木は、ノードに2つの子があるか、まったくない二分木です。 つまり、葉を除いて、他のすべてのノードに2つの子がある場合、二分木は完全な二分木になります。
2. 完全な二分木：完全な二分木とは、すべての異なるレベルが完全に満たされているものです。 これに対する唯一の例外は、キーが主に左側にある最後のレベルである可能性があります。 バイナリヒープは、完全なバイナリツリーの例としてよく使用されます。
3. 完全な二分木：完全な二分木は、葉が同じレベルに存在し、内部ノードが2つの子を持つ二分木です。 完全な二分木の一般的な例は、祖先の家系図です。
4. 病理学的縮退二分木：縮退木は、内部ノードに1つの子を持つ二分木です。 それらのパフォーマンスレベルは、リンクリストに似ています。 二分木の種類の詳細をご覧ください。

読む： Rで最も一般的に使用される6つのデータ構造

二分木の利点

1. データを階層的に保存するための理想的な方法
2. 特定のデータセットに存在する構造的関係を反映する
3. リンクリストや配列よりも高速に挿入と削除を行う
4. データを保持および移動する柔軟な方法
5. できるだけ多くのノードを格納するために使用されます
6. 要素へのアクセスに関しては、リンクリストよりも高速で、配列よりも低速です

結論

このブログでは、データ構造内の二分木とは何かについて説明し、そのタイプ、表現、および利点についても説明しました。 ツリーの2つの主な用途は、データの検索と保存であるため、データサイエンスとその関連分野の研究に不可欠です。

データ構造、データサイエンスのバイナリツリーについて知りたい場合は、IIIT-BとupGradのデータサイエンスのエグゼクティブPGプログラムをご覧ください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップを提供します。業界の専門家とのメンターシップ、業界のメンターとの1対1のメンターシップ、400時間以上の学習、トップ企業との就職支援。