ツリーは、既に操作している最も一般的なデータ構造です。 ファイルシステムからDOMに至るまで、コンピューターが行うことの多くは、ツリーの生成と操作に完全に依存しています。

木とは何ですか？

つまり、ツリーはノード/値のコレクションであり、各ノードは降順のノードを指し、すべてが単一の親ノードに接続します。 おそらく最もよく知っているツリーであるDOMを見てみましょう。

ツリーのルートには、 document （実際にはウィンドウですが、shhh）そして追加するすべてのHTMLタグは、その下に新しい子ノードを作成します。 ツリーの主なポイントは、ノードがいくつあっても、ランダムに誰かを選択でき、ルートやその他の要素までの道のりをいつでもたどることができるということです。

有効なツリーと無効なツリー

以前は、リンクリストを作成したとき、ルート（ヘッド/テール）があり、各ノードがnext / prevポインターで子に接続されていたため、技術的にはすでに実行可能なツリーを作成していました。 どのノードから始めても、常に単一のルートに戻る方法を見つけることができますが、ノードの単一のチェーンだけでは少し簡単です。

これらはすべて有効なツリーです。 ツリーに基づくさまざまな構造のほとんどは、ツリー内のデータがどのように編成されているかに関係していますが、すべて次のようになります。

適切なツリーを作成するには、従う必要のあるルールがいくつかあります。 ツリーはそれ自体のルートを参照できません。たとえば、循環リンクリストでトラバーサルアルゴリズムを実行すると、すぐに再帰の悪夢になります。 また、複数のルートまたは複数の親を持つノードを持つことはできません。

最後に、ツリーには方向性があり、すべてがルートから移動する必要があります。 方向のないノードのクラスターは、実際にはそれ自体のはるかに複雑な構造であるグラフであり、これについては今後の記事で取り上げます😉。

ノードのリンクを開始してツリーと呼ぶことはできません。これらのルールに違反すると、将来のデータ構造とアルゴリズムが不可能になります。

木の解剖学

かなり退屈ですが、木についてさらに学ぶときに常に目にする最も重要な用語をカバーする必要があります。

  • Node -各単一オブジェクトまたはデータポイント。
  • Root -他のすべてのノードの派生元であるツリーの最初の最上位ノード。
  • Edge -2つのノード間の接続。
  • Parent -下位ノードの直接の祖先。
  • child -上位ノードの直系の子孫。
  • Siblings -同じ親を持つ同じ深さの2つのノード。
  • Leafs -子のない最下部のノード。
  • Depth -木の高さは、ルートから離れたエッジの数と同じレベルで測定されます。したがって、レベル2は、ルートから2つのエッジだけ離れています。
  • Breadth -葉の数で測定された木の幅。
  • Subtree -独立したツリーとして扱うことができるノードとその子孫。 たとえば、辞書をツリーとして作成し、各アイテムをアルファベット順に調べる検索アルゴリズムを使用した場合、ツリー内のすべてのアイテムを調べる代わりに、最初の文字のセクションのノードをルートとして使用できます。

まとめ

今のところ、これはまるでたくさんの綿毛のように見えるかもしれませんが、悪魔は本当に細部にあります。 より複雑な構造に進むにつれて、これらの詳細を見落とし、デバッグが非常に難しいエラーに溺れることがますます容易になります。