二分木とは

バイナリツリーは、情報の保存、並べ替え、およびアクセスのためにコンピュータープログラミングで使用されるデータ構造の一種です。 バイナリツリーは最も単純な種類のツリーですが、非常に便利で実装も簡単です。 バイナリツリーの典型的な実装は、ポインター変数によってツリー自体を構成する一連のノードにリンクされたルートノードに依存します。 このタイプのツリーは、ツリー内のノードが3つ以上の子を持つことはできないという事実からその名前を導きます。

ツリーデータ構造にはさまざまな種類があります。 これらは、階層パターンで編成された異なるノードで構成されています。 単一のノードであるルートは、データツリー全体を検索したり操作したりできるアクセスポイントです。 このルートノードは、ツリー自体の最上位ノードを指します。

最上位ノードを除いて、ツリー内のノードには、ツリーの階層でその上にある親ノードがあります。 また、その下にある子ノードを持つこともできます。 特定のノードは、ツリー内のその上のノードからアクセスされ、その下のノードへのアクセスを提供します。

バイナリツリーデータ構造により、各ノードは2つ以下の子を持つことができます。 したがって、特定のノードには、0、1、または2つの子ノードを接続できます。 通常のバイナリツリーでは、ツリーの任意のポイントに任意の数の子を持つノードを使用できます。 また、ツリーを構成するノードに格納されている値の配置方法に制限を設けません。

データ構造は、コンピューターがデータにアクセスできる速度を向上させ、バイナリツリーの修正バージョンを使用して効率を向上させる場合に最も役立ちます。 バイナリ検索ツリーとは、特定のノードの左下にあるブランチにあるすべてのデータ値が、そのノードに格納されている値以下の値を持つツリーです。 順序付けられたバイナリツリーのノードの右側の値は、ベースノードの値よりも大きくなければなりません。 このデータの順序付けにより、はるかに効率的な検索アルゴリズムを作成できます。

バイナリツリーの形状は、検索アルゴリズムの効率を判断する上でも重要です。 バイナリツリーの最も効率の低い種類は、各ノードに子が1つしかないものです。 コンピューターは、この構成内の単一の情報を見つけるために、ツリー全体のすべてのデータ項目を調べる必要がある場合があります。 対照的に、最も効率的なバイナリツリーは、ツリーの最下部にあるノードを保存するすべてのノードに2つの子があり、すべてのリーフノード（ツリーの最下位ノード）がルートから同じ距離にあるツリーです。