【きこうぞう（つりー）】
木構造（ツリー） とは？
最終更新:
💡 根から親子関係で枝分かれする、データの階層
根から親子関係で枝分かれする階層的なデータ構造。ノード・葉・二分木、DOMの例と、木の形によって検索効率が変わる理由を解説します。
ひよこ 木構造は、どんな関係を表す？
ペンギン先生 根から枝分かれする階層を表すよ。ここでは根付きの木を考えよう。根以外の要素は一つの親を持ち、子をたどって出発点へ戻る輪はない。フォルダの階層を考えるとイメージしやすいね。
ひよこ 根とノードと葉は、別の部品？
ペンギン先生 全部がノードだよ。根は、親を持たない出発点のノード。葉は、子を持たないノードの呼び名だ。一つだけのノードなら、そのノードが根でも葉でもある。図で同じ高さに並んでいても、親が同じとは限らないんだ。
ひよこ 木なら、子は二つだけ？
ペンギン先生 ひよこ 二分探索木なら、いつも速い？
ペンギン先生 検索では木の高さが関係する。高さを抑えた木なら、件数nに対してO(log n)の探索を期待できる。一方、一方向に偏ると、順にたどる長い形になりO(n)になる場合がある。値の置き方だけで常に高速になるわけではないんだ。
ひよこ Webページも、木構造？
もっと詳しく知りたい人へ
根は、最初から必ずある？
空の木を認めるデータ構造の定義もあります。根がある木では、根の親はありません。空の状態をどう扱うかは、使うデータ構造やAPIで確認します。
フォルダの実体は、すべて木？
階層の説明には木が役立ちますが、リンクによって別の場所を参照する仕組みもあります。表示している階層と、すべての参照関係を同じものとして扱わないことが大切です。
まとめ：ざっくりこれだけ覚えればOK！
「木構造」って出てきたら「根から親子関係で枝分かれする階層的なデータ構造」と思えばだいたいOK！
📖 おまけ：英語の意味
「Tree」 ＝ 木・樹木
💬 枝分かれする関係に由来する表現です。コンピューターの図では、根を上、葉を下に描くことがよくあります。上下はデータの意味を決める条件ではありません。