ツリー構造

略歴/流れ

インターネット上の情報が増えるにつれ、情報を順序だてて分類し、ユーザーにとってもサイト運営側にとっても、情報を分かりやすくする必要が出てきました。

そしてツリー構造（木構造）の概念が確立されると、ツリー構造は様々な仕組みに組み込まれることになりました。

種類・定義

ツリー構造とは

ツリー構造とは、データ構造の一種で、複数のデータが木のように枝分かれした状態で配置された構造のことです。

ツリー構造を構成するそれぞれの要素をノード（または節）と言い、ノード同士の繋がりをエッジ（または枝）と言います。

ノードは複数の子ノードを持ち、子ノードも自身を親ノードとして複数の子ノードを持つことから、家系図を想像すると分かりやすいでしょう。

ノード

始まりとなる、親を持たないノードを根ノードと言い、親と子を持っているノードを枝ノード（または内部ノード、中間ノード、非終端ノード）、子を持たないノードを葉ノード（または外部ノード、終端ノード）などのように呼びます。

あるノードから見て葉ノード側にあるノードをまとめて子孫ノードと言い、反対に根ノード側にあるノードをまとめて先祖ノードと言います。

同じ親を持つノード同士は兄弟ノードと呼ばれます。親は複数の子を持ちますが、子が複数の親を持つことはありません。

ツリー構造の種類

ツリー構造は子の数によって分類することができます。

二分木

二分木は、子の数が2つまでと決まっているツリー構造を指し、すべてのノードが2つの子を持っている二分木を完全二分木や二進木、バイナリツリーと呼びます。

多分木

多分木は、親が3つ以上の子を持てるツリー構造で、多進木とも呼びます。

n分木

n=3以上の自然数としたとき、n個の子を持つツリー構造をn分木、またはn進木と呼び、子の数に合わせて呼び方の種類が変わります。

関連する単語の紹介

深さ

あるノードから根ノードまでのエッジ数を深さと言います。根ノードの深さは0で、そこから子ノードへ1階層下るごとに1ずつカウントしていきます。

高さ

高さは、あるノードから一番深い葉ノードまでのエッジ数のことです。根ノードの高さはそのツリー構造の高さとイコールになります。

幅

同じ深さにあるノードの数を幅と言います。

部分木

あるノードからその子孫ノードを見ると、その部分だけでもツリー構造が形成されています。

これを部分木と言い、根ノードから始まる部分木はそのツリー構造全体ということになります。根ノードを含まない部分木は真部分木と呼びます。

平衡木

平衡木は葉の深さが等しくなるように構築された木（ツリー構造）のことで、バランス木とも呼ばれます。

森

森は、複数の木からなる木の集合体を指します。

ヒープ

ヒープは、「子ノードの値が親ノードの値よりも常に小さいか等しい（または常に大きいか等しい）」という特徴を持つツリー構造です。

ヒープは最大値、または最小値を求めることに適しています。

二分ヒープ

二分ヒープはバイナリーヒープともいい、二分木を使ったヒープを指します。単に「ヒープ」と言う場合、この二分ヒープのことを指す場合もあります。

二分探索木

二分探索木は、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という特徴を持つ二分木で、値の探索に適した性質を持つ探索木の中で最も基本的なツリー構造です。

深さ優先探索

深さ優先探索は、ツリー構造のノードを体系的に調査する走査アルゴリズムの一つで、あるノードから目的のノード、もしくは子のないノードまで深く伸びていく探索方法です。

末端の葉ノードまで行ったら、そこから一番近くの探索が終わっていないノードまで戻るということを繰り返します。

幅優先探索

幅優先探索もツリー構造の走査アルゴリズムで、根ノードから始まり、その子ノードをすべて探索したら、さらに次の深さの同じ幅にある子ノードを探索します。

一般的な活用方法、様々な目線から紹介

サイトの構造が分かりやすくなる

ツリー構造を用いてウェブサイトのページを階層ごとに整理することで、ユーザーが今どこにいるのか分かりやすく表示することができます。

代表的なものがパンくずリストで、ウェブサイトでは必ずと言っていいほど採用されています。

「ホーム>製品案内>製品A」のような表示をページに記載することで、ユーザーはサイトの構造を把握しやすくなり、いまサイトのどこにいるのか・目的の情報がどこにあるのかが分かりやすくなります。

URLもツリー構造になっており、「http://www.●●●.co.jp/product/productA」のように「製品一覧>製品A」とURLからも、サイト内の位置が分かるようになっています。

情報を管理しやすくなる

構築されたウェブサイトの情報が無秩序に点在していると、情報を探したり、付け加えることが困難です。

ツリー構造を基に、様々な情報をモデル化するのに使われる非巡回グラフや、複数の文書を関連付けるシステムであるハンパーリンクを用いることで、情報を管理しやすくなります。

また、ツリー構造は子が増えていくという特性から、後から情報を付け加えることが容易にできます。

ツリー構造のメリット・注意点

ツリー構造のメリット

ツリー構造を用いて情報が分かりやすく分類されることで、ユーザーがサイトの内容を把握しやすくなったり、サイトのテーマの関連性が高くなることから、SEO効果が期待できます。

サイト運営側としても情報を管理しやすくなり、効率化を図ることができます。

ツリー構造の注意点

ツリー構造の階層を深くしすぎると、目的のデータへのアクセスが複雑になることや、データの処理に時間がかかることなどが挙げられます。

また、同じ情報を複数の箇所で使用した場合、その情報の分類が分かりにくくなるケースもあります。逆に階層が浅すぎると、データの関連性が分かりにくくなったり、薄くなったりします。

これはSEOの観点から見ると良くない影響が懸念されます。とはいえ、ツリー構造を適切に用いればこれらの問題を回避することができるので、ツリー構造は積極的に用いるべきでしょう。

関連キーワード

パンくずリスト