はじめに
n番煎じですが自分の理解のために木構造についてまとめます。
この記事は導入です。具体的に木構造を学ぶ前に全体像を感じるための始まりの記事です。
木構造の各種類ごとの解説や探索アルゴリズムについても記事を書こうと思います。それぞれ作成次第リンクを貼る予定です。
木構造とは
グラフ理論において、連結で閉路を持たないグラフを「木」と呼びます。
ノードが一つだけある場合は「木」と呼べます。
ノードが二つあり、それらが一つの枝で結ばれている場合、「木」と呼べます。
ノードが三つあり、それらが二つの枝で結ばれている場合、「木」と呼べます。
ノードが三つあり、それらが結ばれて三角形をなしている場合、閉路があるため「木」とは呼べません。
一般的に、データ構造における「木」というと、以下のような画像が使われます。
〇のことを「ノード（節）」、ノードをつなぐ線を「枝（ブランチ）」、一番上のノードを「根（ルート）」、一番下のノードを「葉（リーフ）」と呼びます。
また、根からのノードの数を「深さ」と呼びます。上の画像の場合、葉の深さは2です。
また、ノード同士の位置関係を家系図になぞらえて、特定のノードの上に位置するノードを「親」、下に位置するノードを「子」、同じ深さのノードを「兄弟」と呼ぶことがあります。
何がうれしいか
階層的データが表現できる
ディレクトリや組織図など、階層的なデータ構造を表したいとき、木構造であればこれらを自然に表現できます。
データ挿入と削除が柔軟に行える場合がある
一口で「木」といっても、さまざまな形があるため、すべてがそうとは言えませんが、木の形を工夫することで、リストよりもデータ挿入や削除を効率的に行える場合があります。
巡回方法がいろいろある
たとえばリストだと、上から順にみる、下から順にみる、という2パターンに限られますが、
木構造にはさまざまな巡回方法があるため、場合に応じて効率的な巡回方法を選択できます。
探索が早い、安定した速度となる場合がある
リストを上から順に見る場合、お目当ての要素が一番最後にある場合、すべての要素を確認していく必要があり、リスト内の要素の数とお目当ての要素の位置によっては時間がかかります。
木構造では、（挿入・削除と同じく）適切な形に整形し、適切な巡回方法を選択することで、確認する要素の個数を制限できます。
そのおかげで、データの量が増えても速度劣化が少なく済んだり、データの位置が悪くてもそれなりの速さでアクセスできます。
部分集合が扱いやすい
木構造のうち、一部のノードの集合に注目すると、その部分も木構造になっていることに気づきます。
特定のノードを根として扱うことで「部分木」を簡単に取り出すことができます。
特定のデータ群の抽出や操作が可能です。
活用例
ファイルシステム
ファイルシステムは階層構造であるため、木構造で表現するのがぴったりです。
ルートディレクトリを「根」として配置し、各サブディレクトリを子ノードとして配置することで実現します。
データベースのインデックス
データベースでの検索を速くするために「インデックス」という機能がありますが、これは木構造で実現されています。
「B木」という形が一般的に利用されているようです。
構文解析
コンパイラによる構文解析は木構造を作成するのが一つのゴールで、そのアウトプットは「構文解析木」と呼ばれます。
ソースコード（文字列）としての構文を木として表現することで、プログラム解析と最適化に利用されます。
さまざまな形
木構造にはさまざまな形が考案されており、形によって、構造の変更（挿入や削除）に強い、検索が速い、などのメリットがあります。
子ノードの個数による分類
2分木
全てのノードの子ノードが「2つ以下」である木構造を「2分木」と呼びます。
構造が単純なので、操作が容易です。
シンプルがゆえに検索やデータ操作のアルゴリズムを適用しやすく、さまざまな変種が考案されています。
n分木
全てのノードの子ノードが「n個以下」である木構造を「n分木」と呼びます。「多分木」とも呼びます。
平衡木（バランス木）
冒頭に挙げたこちらの木は、左右のノードの個数が均等になっています。
対して、以下も木構造ですが、右に偏っています。偏っていても、木であることに変わりありません。
前者のように左右のノードが均等、つまりバランスが取れている木構造を平衡木（バランス木）と呼びます。
根から葉まで探索することを考えると、前者の場合どの葉にアクセスするにも3つたどればたどり着きます。
後者の場合、5つたどる必要があります。
前者の方がノードの個数が多いにもかかわらず、前者の方が速いといえます。
このように、バランス木はデータの格納やアクセスが効率的にできます。
AVL木
各ノードの左部分木と右部分木の高さの差を1以下することで平衡を保つ二分探索木です。
二分探索木とは、ノードが持つ値を「左の子<=親<=右の子」となるように並べた2分木を指します。
赤黒木
ノードを赤と黒で色分けすることで木の高さを一定に保つ二分探索木です。
B木, B+木
各ノードが複数のキーとポインタを持ち、各ノードが複数の子ノードを持つことで深さを一定に抑えて平衡を保つn分探索木です。
B木ではすべてのノードに値を格納できますが、B+木では値を持つのは葉のみです。
B+木は探索途中の経路に値を持たず検索に必要な情報のみを持つことで、より高さを抑えることに成功し、検索性能を向上させています。
2-3木
各ノードが2つか3つの子ノードを持ち、すべての葉が同じ深さとなるように平衡を保った多分探索木です。
さまざまな探索方法
深さ優先探索（Depth-First Search）（DFS）
深さ方向に可能な限り進んで、行き止まりに達したら分かれ道まで戻って、兄弟側の深さ方向を探索します。
どの兄弟を先に見るのかで３パターンの探索方法が存在します。
再帰処理として実装できます。
行きがけ順
親→左の子→右の子 の順に訪問します。
通りがけ順
左の子→親→右の子 の順に訪問します。
二分探索木にて通りがけ順で探索すると、ノードが昇順に並びます。
帰りがけ順
左の子→右の子→親 の順に訪問します。
幅優先探索（Breadth-First Search）（BFS）
根から順に、兄弟を見ていきます。兄弟が見終わったらその子孫に移ります。
キュー（FIFO）で実装できます。
おわりに
せっかく大学で習ったのに、社会人になって活かす機会がいままでありませんでした。でもそれは私の知識として定着していないから引き出しとして機能していなかったのだろうと感じます。（競プロerが業務で速度改善をばちこりキメている、なんて話はよく聞きますものね）