ツリー（Tree）：枝分かれで持つ
階層をそのまま表す構造 — 二分探索木の O(log n)、通りがけ順とソートの関係、そして C・Java・C#・Python での持ち方まで
ツリーとは：階層をそのまま表す
配列も連結リストもスタックもキューも、データを一列に持つ構造でした。ツリーはそこに枝分かれを持ち込みます。1 つの根（root）から枝が伸び、それぞれの節（node）は子を持つことができ、子のない節を葉（leaf）と呼びます。
50 <- 根（root） / \ 30 70 <- 節（node） / \ / \ 20 40 60 80 <- 子のない節が葉（leaf） 根から下へ枝分かれしていく（木は上下逆さまに描かれる）
フォルダとファイル、HTML の要素（DOM）、組織図 — 世の中の「入れ子」や「階層」は、ツリーでそのまま表せます。一列の構造に無理に押し込めなくてよいこと。それがツリーを使う第一の理由です。
二分探索木：「左は小さい、右は大きい」
ツリーに規律を 1 つ足すと、強力な検索の道具になります。二分探索木（BST：Binary Search Tree）は、「どの節でも、左側にはそれより小さい値だけ、右側には大きい値だけを置く」という約束を守る木です。
60 を探す: 大小を比べて、左右どちらかへ降りるだけ 50 60 > 50 -> 右へ / \ 30 70 60 < 70 -> 左へ / \ / \ 20 40 [60] 80 <- 3 回の比較で到着 1 回比べるごとに候補が半分になる -> バランスしていれば O(log n)（100 万件でも約 20 回）
探しものは根から始めて、大小を比べて左右どちらかへ降りるだけです。1 回比べるたびに候補が半分に絞られるので、比較の回数は「n を 1 になるまで半分にできる回数」で済みます。この回数を log n と書き、木のバランスが取れていれば O(log n) — 100 万件でも約 20 回の比較 — で見つかります。
Array と List のページを思い出してください — 配列は添字アクセスこそ速いものの途中への挿入が O(n)、連結リストは挿入がつなぎ替えで済むものの目的の場所へ辿り着くのに O(n) かかりました。二分探索木は、探すのも入れるのも O(log n) にする「いいとこ取り」を狙った構造です。
偏りに注意
ソート済みの値を順に挿入すると、木は一直線に伸びて実質ただの連結リストになり、検索は O(n) に退化します。実用の木は、挿入や削除のたびに形を整えて偏りを防ぎます — これが自己平衡木（AVL 木、赤黒木など）です。Java の TreeMap も、その 1 つ（赤黒木）を中身に使っています。
走査：木を一列に読む
木の中身をすべて見て回ることを走査（traversal）と呼びます。代表は 3 つ — 自分を先に見る行きがけ順（pre-order）、左 → 自分 → 右の通りがけ順（in-order）、子を先に見る帰りがけ順（post-order）です。それに、浅い階層から順に見るレベル順を加えた 4 つを覚えておけば十分です。
通りがけ順（in-order）: 左の子 -> 自分 -> 右の子 の順に読む 50 / \ 30 70 / \ / \ 20 40 60 80 読み出される順: 20, 30, 40, 50, 60, 70, 80 -> 二分探索木を通りがけ順に読むと、ソート済みの列になる
通りがけ順には面白い性質があります。二分探索木を通りがけ順に読むと、値がソート順に出てくるのです。そして実装にも注目してください — レベル順の走査にはキューを、深さ優先の走査にはスタック（または再帰）を使います。前の 2 ページの構造が、木を歩く道具として再登場します。
どこで使われているか
階層データの表現は、ほぼツリーです。ファイルシステム、ブラウザが持つページの構造（DOM）、そしてコンパイラがプログラムを理解するときに作る構文木。
検索の道具としても要所にいます。データベースの索引に使われる B 木は、二分ではなく多分岐にした二分探索木の親戚です。優先度付きキューの中身であるヒープも、木の一種です。
各言語での持ち方：C・Java・C#・Python
C の例
/* C: 標準の木はない — 構造体と参照（ポインタ）で自作する */ struct Node { int key; struct Node *left; /* 左の子（自分より小さいキー） */ struct Node *right; /* 右の子（自分より大きいキー） */ };
C には標準の木がありません。構造体と参照（ポインタ）で節を自作します — 連結リストの「次へ」が「左へ・右へ」の 2 本になった形です。
Java の例
// キーがソート順に保たれる Map（中身は赤黒木） TreeMap<Integer, String> map = new TreeMap<>(); map.put(50, "root"); map.put(30, "left"); map.put(70, "right"); map.firstKey(); // 30 — 最小のキー map.ceilingKey(60); // 70 — 「60 以上で最小のキー」も O(log n)
Java で「キーをソート順に保ちながら、検索・挿入・削除をすべて O(log n) で」やりたいときは、TreeMap / TreeSet を使います。中身は赤黒木 — 挿入・削除のたびに「色」の規則で形を整える、自己平衡二分探索木です。
// TreeMap の内部構造（OpenJDK を簡略化） static final class Entry<K,V> { K key; V value; Entry<K,V> left; // 左の子（自分より小さいキー） Entry<K,V> right; // 右の子（自分より大きいキー） Entry<K,V> parent; // 親 boolean color; // 赤か黒か — バランスを保つための情報 }
HashMap との使い分けはこうです。順序が要らず、1 件ごとの出し入れが最速でよいなら HashMap（キーから格納場所を直接計算する Map で、平均 O(1)）。キーをソート順に辿りたい、あるいは「60 以上で最小のキー」のような範囲の質問をしたいなら TreeMap（O(log n)）。
C# の例
// C#: SortedDictionary<K,V>（中身は赤黒木） var map = new SortedDictionary<int, string>(); map[50] = "root"; map[30] = "left"; map[70] = "right"; // キーは常にソート順で列挙される: 30, 50, 70
C# の SortedDictionary<K,V> も中身は赤黒木で、キーは常にソート順に列挙されます（似た名前の SortedList は配列ベースで、性質が違います）。
Python の例
# Python: 標準ライブラリに平衡二分探索木はない # （dict はハッシュテーブル — 平均 O(1)、ソート順は保たない） data = {50: "root", 30: "left", 70: "right"} for key in sorted(data): # ソート順が要るなら都度ソートする print(key, data[key]) # 本格的に必要なら外部ライブラリ（sortedcontainers など）を使う
Python の標準ライブラリには平衡二分探索木がありません。dict はハッシュテーブルで、平均 O(1) ですがキーのソート順は保ちません（挿入順は保持されます）。ソート順が必要なら都度 sorted() するか、外部ライブラリ（sortedcontainers など）を使うのが実情です。
まとめ
ツリーは階層をそのまま表す構造。根から枝分かれし、子のない節が葉。
二分探索木は「左は小さい、右は大きい」の規律で、バランスしていれば検索・挿入とも O(log n)。偏ると O(n) — だから実用は自己平衡木。
通りがけ順に読むとソート順に出てくる。レベル順はキュー、深さ優先はスタックで歩く — データ構造は組み合わさって働く。
Java の TreeMap も C# の SortedDictionary も中身は赤黒木。Python に標準の平衡木はなく、dict はハッシュテーブル。C では構造体と参照で自作する。