女性向けエンジニアスクール
3秒でわかる
1つの根から枝分かれして広がる構造。データ構造としての木と、階層を表示する Linux の tree コマンドの両方で同じ形が出てきます。
30秒図解
もう少し詳しく
どういうものか
木は、1つの根から始まり、各要素が0個以上の子を持つ形で広がるデータ構造です。要素をノード、つながりをエッジ、子を持たない末端を葉と呼びます。閉じた輪ができない点が特徴で、任意のノードから根までの道筋は必ず1本に定まります。
同じ名前で、Linux のコマンドとしての tree もあります。こちらはフォルダの階層を枝の形で表示するもので、扱っている対象がまさに木構造なので名前が重なっています。
なぜ必要か
現実の階層はほとんど木になっています。ファイルとフォルダ、HTML の DOM、組織図、JSON の入れ子、いずれも根から辿る形です。木として捉えられると、「全部を漏れなく巡る」処理を、深さ優先や幅優先という決まった手順で書けます。
二分探索木のように順序の規則を持たせた木なら、要素数が100万でも20回程度の比較で目的の値に届きます。総当たりとの差は、扱う量が増えるほど開きます。
具体例
Linux で階層を表示する使い方です。
tree -L 2 -d # 2段まで、フォルダだけ表示
tree -a -I node_modules # 隠しファイルも含め、node_modules は除外.
├── src
│ ├── components
│ └── utils
└── testsデータ構造として扱う場合は、子を配列で持たせるのが素直です。
tree = {
"name": "src",
"children": [
{"name": "components", "children": []},
{"name": "utils", "children": [{"name": "date.py", "children": []}]},
],
}
def walk(node, depth=0):
print(" " * depth + node["name"])
for child in node["children"]:
walk(child, depth + 1)
walk(tree)つまずきやすいところ
再帰で書くときに、終了条件を置き忘れて自分自身を呼び続ける失敗が起きます。上の例では子が0個なら for が回らないので自然に止まりますが、親への参照も持つ構造にすると、行き来を繰り返して止まらなくなります。
深さ優先と幅優先の使い分けも迷いどころです。最短の階層で見つけたいなら幅優先、全部を辿って集計するなら深さ優先が向きます。
コマンドのほうでは、node_modules のようなフォルダを除外せずに実行して、端末が数万行で埋まる事故がよくあります。-L で段数を切るのが先です。
覚え方
根が上、葉が下という向きで描かれるので、現実の木をひっくり返した図と覚えると混乱しません。
