二分探索木 (BST) への挿入
二分探索木 (BST) への挿入
このレッスンで分かること
- BST の鉄則は「左の子
<親<右の子」- 昇順や降順に挿入していくと、
BSTは片側に偏った「棒のような形」になってしまいます二分探索木(Binary Search Tree, 略してBST) は、各ノードが最大 2 つの子を持ち、左の子は親より小さい / 右の子は親より大きい という不変条件を守る木構造です
二分探索木 (BST) への挿入 とは
Node クラスを使って二分探索木を構築し、挿入後の
in-order 走査結果を返す。OOP と再帰の合わせ技。
二分探索木 (Binary Search Tree, 略して BST) は、各 ノード が最大 2 つの子を持ち、左の子は親より小さい / 右の子は親より大きい という不変条件を守る 木構造 です。本レッスンでは Node クラスを使って BST を空から構築し、複数の値を順に 挿入 していった結果を in-order (中順) 走査で返します。
BST の鉄則は「左の子
<親<右の子」。挿入も検索も、この不変条件を守りながら左右どちらかへ進むだけ。
Node クラスの設計
木構造 の ノード は、value と「左の子 への参照」「右の子 への参照」を持ちます。
Python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = Noneリンクリスト の ノード は next だけでしたが、木 の ノード は left と right の 2 本に分岐します。これが「木」の名前の由来でもあります。
挿入アルゴリズム
BST に新しい値 v を入れる手順は次の通りです。
- ルートから出発する
vが現在のノードのvalueより小さいなら左へ、大きいなら右へ進む- 進んだ先が
Noneだったら、そこに新しいNode(v)を置く
再帰 で書くと、こうなります。
Python
def insert(node, v):
if node is None:
return Node(v)
if v < node.value:
node.left = insert(node.left, v)
elif v > node.value:
node.right = insert(node.right, v)
return nodenode.left = insert(node.left, v) の 代入 がポイント。None に当たって新規 Node が返ってきたら、それを親の left / right に繋ぎ直しています。
挿入の流れを図解
値 5, 3, 8, 1, 4 を空 BST に順に挿入する流れは次のようになります。
図のポイント (テキスト併記)
- 最初に
5がルートに置かれ、3は5 > 3なので左へ、8は5 < 8なので右へ、1は5 > 1, 3 > 1で3の左へ、4は5 > 4, 3 < 4で3の右へ、と進みます
最初に 5 がルートに置かれ、3 は 5 > 3 なので左へ、8 は 5 < 8 なので右へ、1 は 5 > 1, 3 > 1 で 3 の左へ、4 は 5 > 4, 3 < 4 で 3 の右へ、と進みます。
in-order 走査
BST を in-order (中順) で走査すると、ソート済みの配列 が得られます。これが BST の大きな利点。
Python
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.value)
inorder(node.right, out)「左 → 自分 → 右」の順で再帰的に訪問するだけで、自然と昇順になります。先ほどの [5, 3, 8, 1, 4] を in-order で取り出すと [1, 3, 4, 5, 8] になるはずです。
JavaScript での実装
JavaScript
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function insert(node, v) {
if (node === null) return new Node(v);
if (v < node.value) node.left = insert(node.left, v);
else if (v > node.value) node.right = insert(node.right, v);
return node;
}このレッスンでやること
関数 bstInsertAll(values) を実装してください。values を空 BST に 順番に 挿入 し、最後に in-order で走査した結果の 配列 を返します。重複 する値は無視 (= 何もしない) してください。例として [5, 3, 8, 1, 4] → [1, 3, 4, 5, 8]、[10, 5, 5, 15] → [5, 10, 15]。
よくある間違い
node.left = insert(node.left, v)の代入を忘れると、新ノードがツリーに繋がらない。
if v < node.valueをif v <= node.valueにしてしまうと、重複が左に入ってしまう。本問では重複は無視。in-orderの順序を間違える (左 → 自分 → 右 が正解)。空配列を渡されたときにNoneをinorderに渡してエラー。先にif node is None: returnで弾く。
BST が崩れるとどうなるか
BSTの検索/挿入がO(log n)になるのは「木が平衡している」場合だけ。最悪はO(n)まで悪化する。
昇順や降順に挿入していくと、BST は片側に偏った「棒のような形」になってしまいます。たとえば [1, 2, 3, 4, 5] を順に空 BST に挿入すると、右だけにずっと伸びる リンクリスト のような構造になり、検索が O(n) になります。これを防ぐために、実用的な実装では AVL 木 や 赤黒木 といった 自己平衡 する BST が使われます。本コースでは基本の挿入のみを扱いますが、偏り の問題があることは覚えておきましょう。
やってみよう
再帰の insert と inorder を組み合わせる感覚を身につけましょう。OOP (クラスでノードを定義) と 再帰 (関数で操作) の組み合わせは、データ構造 の実装ではほぼ必ず登場します。
よくある質問
Q. 重複した値を挿入しようとするとどうなりますか？
A. 本レッスンの実装では、重複値は無視します。v < node.value / v > node.value のどちらにも当てはまらない場合(等しい場合)は何もせずに node をそのまま返します。重複を許したい場合は「左か右のどちらか一方に入れる」ルールを決めて実装します。
Q. 再帰版と反復版はどっちが良いですか？
A. 反復版が安定して高速です。再帰版は読みやすい代わりにスタック消費があります。配列の長さが極端に大きい（数億）場合のみ反復版を選び、教育用や読みやすさ重視なら再帰版で十分です。Python は再帰深さ制限にも注意してください。
Q. lower_bound / upper_bound とは何ですか？
A. lower_bound は target 以上が最初に現れる位置、upper_bound は target より大きい値が最初に現れる位置を返します。重複要素のある配列で「何個含まれているか」を upper - lower で求める典型イディオムで使います。
次のレッスン
次は カウンタクラス（機能合成） で、状態を持つ Counter クラスを実装し、inc / dec / reset の操作列を順に適用して最終的なカウント値を返す方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BST insert の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BST insert とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
Nodeクラスを定義し、value/left/rightを持たせる- 再帰関数で BST に挿入する。
Noneに当たったら新ノードを返し、親側でleft/rightに繋ぐ - in-order (左 → 自分 → 右) で走査して、ソート済み配列を返す。重複は無視する
入出力例
test-cases.txt
bstInsertAll([5,3,8,1,4]) → [1,3,4,5,8]
bstInsertAll([10,5,5,15]) → [5,10,15]
bstInsertAll([1,2,3,4,5]) → [1,2,3,4,5]
bstInsertAll([5,4,3,2,1]) → [1,2,3,4,5]
bstInsertAll([42]) → [42]
bstInsertAll([7,3,9,1,5,8,10]) → [1,3,5,7,8,9,10]