【にぶんぎ】
二分木（バイナリツリー） とは？
最終更新:
💡 1つの点から、子は左と右に最大2つ
各ノードが左・右に最大2つの子を持つ木構造。子が0個や1個のノードもある。値の大小の規則は必須ではなく、二分探索木はその規則を追加した一種。形が偏ると、探索でたどる道が長くなることもある。
ひよこ 必ず2つに分かれるの？
ペンギン先生 最大2つだよ。子がない点も、1つだけの点もあってよい。点をノード、上側の出発点を根、子がないノードを葉と呼ぶ。図の例は、値の大小を決めずに二分木の形を示しているよ。
ひよこ 左の方が小さくなければ、間違い？
ペンギン先生 普通の二分木には、その規則はないよ。二分探索木では、各ノードの左の部分木に小さいキー、右の部分木に大きいキーを置く。直下の子だけでなく、その先の子孫を含む範囲の規則だね。同じキーを入れる場合の扱いは、実装の方針も確認しよう。
ひよこ 二分木なら、高速に探せる？
ペンギン先生 形の条件だけで高速な探索ができるわけではないよ。二分探索木なら、大小を比べて進む側を選べる。しかし一直線に偏ると、たくさんのノードを順にたどる場合がある。探索の規則と木の高さ、両方を見ることが大切なんだ。
ひよこ 偏りを防ぐ方法は？
ペンギン先生 まとめ：ざっくりこれだけ覚えればOK！
「二分木」って出てきたら「各ノードの子が、左と右に最大2つある木構造」と思えばだいたいOK！
📖 おまけ：英語の意味
「Binary Tree」 ＝ 二分木
💬 binaryは2つの側を持つことを表すよ。すべてのノードに必ず2つの子がある、という意味ではないんだ。