3秒でわかる
ひとつの根から枝分かれし、親子関係で階層をつくるデータ構造。フォルダや DOM、組織図のような入れ子の関係を表すのに使います。
30秒図解
もう少し詳しく
どういうものか
各要素が 0 個以上の子を持ち、親は 1 つだけという規則で枝分かれしていくデータ構造。いちばん上の要素を根、子を持たない末端を葉と呼ぶ。閉じた輪ができないため、どの要素からも根までの道筋がただ 1 通りに定まる。
身近な例が多い。ファイルシステムのフォルダ、HTML の DOM、JSON の入れ子、組織図、ゲームの分岐、コンパイラが作る構文木は、いずれも木になる。
なぜ必要か
一列に並んだリストでは「AのなかのBのなかのC」という包含関係を表せない。木は入れ子をそのまま形にできるうえ、探索の効率も稼げる。値の大小で左右に振り分ける二分探索木なら、1 回の比較で候補が半分になるため、100 万件でも 20 回程度の比較で目的の要素にたどり着く。
具体例
root
/ \
src docs
/ \ \
app.js utils guide.mdこの構造を辞書で表し、再帰でたどる例。
tree = {
"name": "root",
"children": [
{"name": "src", "children": [
{"name": "app.js", "children": []},
{"name": "utils", "children": []},
]},
{"name": "docs", "children": [
{"name": "guide.md", "children": []},
]},
],
}
def walk(node, depth=0):
print(" " * depth + node["name"])
for child in node["children"]:
walk(child, depth + 1) # 子に同じ処理を適用する
walk(tree)木の処理は、ほとんどが「自分を処理して、子に同じ関数を呼ぶ」という再帰で書ける。
つまずきやすいところ
再帰の終了条件を書き忘れると、スタックが尽きて落ちる。子が無いときに何もせず戻る、という分岐を必ず用意する。上の例では for 文が回らないことが終了条件になっている。
深さを取り違えるのも多い。深さ優先で探すと、根から一気に末端まで潜ってから隣に移る。幅優先ならキューを使い、同じ階層をすべて見てから 1 段下がる。「最短の道筋を知りたい」場面で深さ優先を選ぶと、遠回りの経路を先に見つけてしまう。
二分探索木は、値を順番どおりに挿入すると片側だけに伸びて実質リストになり、速さの利点が消える。実務で使われる木が、赤黒木や B 木のように自動で高さを整える仕組みを持っているのはこのためになる。
似た用語との違い
グラフは、輪ができてもよく、親が複数あってもよい一般形になる。木は「輪が無く、親がひとつ」という制約を加えたグラフと言える。
