二分木（バイナリツリー）とは何ですか？

各ノードが最大2つの子ノードを持つ木構造のデータ構造。検索、ソート、データ管理の基盤となる。

二分木（バイナリツリー）のポイントは？

各ノードは左の子と右の子を最大2つ持つ。二分探索木（BST）なら左の子＜親＜右の子の順序を維持。平衡二分木（AVL木、赤黒木）で最悪計算量O(log n)を保証。IPA試験のアルゴリズム・データ構造分野で頻出

【にぶんぎ】

💡 「左か右か」の2択で高速にデータを探す

📌 このページのポイント

二分探索木のイメージ（左 < 親 < 右）

ひよこ

二分木って何に使うの？

ペンギン先生

一番身近なのはデータベースのインデックス。B木やB+木（二分木の発展形）でインデックスを構築して高速検索を実現している。他にもコンパイラの構文解析木、ファイルシステムのディレクトリ構造、ハフマン符号化による圧縮など用途は広いよ

ひよこ

二分探索木って何？

ペンギン先生

左の子＜親＜右の子という規則を満たす二分木だよ。データを探すとき、探したい値が親より小さければ左へ、大きければ右へ進む。うまくバランスが取れていれば、n個のデータからO(log n)で検索できる。1000個のデータなら約10回の比較で見つかるんだ

ひよこ

バランスが崩れるとどうなるの？

ペンギン先生

最悪の場合、すべてのノードが一直線に並んでリスト状になる（偏木）。こうなると検索がO(n)になって二分探索の意味がなくなる。これを防ぐのが平衡二分木（AVL木や赤黒木）で、挿入・削除のたびに自動的にバランスを保つんだよ

ひよこ

走査（トラバーサル）って何種類あるの？

ペンギン先生

主に3種類。前順（preorder：親→左→右）、中順（inorder：左→親→右）、後順（postorder：左→右→親）。二分探索木を中順走査すると昇順にデータが取り出せる。これはIPA試験でもよく出題されるから、小さい木で手を動かして練習するのがおすすめだよ

まとめ：ざっくりこれだけ覚えればOK！

「二分木」って出てきたら「各ノードが最大2つの子を持つ木構造」と思えればだいたいOK！

📖 おまけ：英語の意味

「Binary Tree」＝二分木・二項木

💬 Binary（2つの）Tree（木）。データベースのインデックスからコンパイラの構文解析まで幅広く使われるよ