BST に値を挿入する
BST に値を挿入する
このレッスンで分かること
- BST の鉄則は「左の子
<親<右の子」- 通常の二分木は親子関係のみで、値の順序に制約はありません
- この条件のおかげで、欲しい値を探すときも、新しい値を入れるときも、
左 or 右の二択で済みます
BST に値を挿入する とは
二分探索木 (BST) に新しい値を挿入し、挿入後の in-order 走査結果を配列で返す関数を実装する。
ここまでで普通の 二分木 を一通り扱えるようになりました。本章では、ノードに「順序」を入れた 二分探索木 (BST: Binary Search Tree) を実装していきます。BST は 左の子は親より小さい / 右の子は親より大きい というシンプルなルールを守るだけで、検索・挿入・削除が O(log n) で行える優れたデータ構造です。
本レッスンでは、配列 (BFS 順, 欠損は null) で表された BST に新しい値を挿入し、その結果を in-order 走査して 10 進数の配列で返す bstInsert 関数を作ります。挿入の感覚を体に覚え込ませると、後続の search delete の理解がぐっと楽になります。
BST の鉄則は「左の子
<親<右の子」。挿入はこの不変条件を守りながら、末端に向かって枝を辿るだけ。
BST の不変条件
通常の二分木は親子関係のみで、値の順序に制約はありません。BST はそこに次の 不変条件 を足します。
- 左部分木のすべての値は、ノードの値より 小さい
- 右部分木のすべての値は、ノードの値より 大きい
- 重複は扱わない (本レッスンでは無視)
この条件のおかげで、欲しい値を探すときも、新しい値を入れるときも、左 or 右 の二択で済みます。比較ごとに探索範囲が半分になるので、平均 O(log n) の計算量を得られます。
木の
高さをhとすると、検索/挿入/削除のコストは全部O(h)。平衡が崩れて棒のような木になると最悪O(n)。
配列での BST 表現
本コースでは木構造を BFS 順の配列で表現します。[10, 5, 15, 3, 7, null, 18] は次の図のようになります。
図のポイント (テキスト併記)
- インデックス
iのノードの左の子は2i + 1、右の子は2i + 2です
インデックス i のノードの左の子は 2i + 1、右の子は 2i + 2 です。null のところは穴を表します。配列表現は読み書きが楽な反面、深さが偏ると配列がスカスカに大きくなる欠点があります。
挿入アルゴリズム
挿入の手続きは次の通りです。
- ルートから出発する
- 新しい値が現在のノードより
小さいなら左へ、大きいなら右へ進む - 進んだ先が
nullだったら、そこに新しい値を置く
再帰でも反復でも書けます。再帰は宣言的でわかりやすく、反復は呼び出しスタックを使わない分わずかに高速です。
Python での実装例
配列表現のままだと扱いにくいので、一度ノードオブジェクトに変換してから挿入し、最後に in-order 走査して配列に戻す方式が読みやすくなります。
Python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def bstInsert(arr, target):
# arr (BFS 配列) -> Node ツリー -> 挿入 -> in-order 配列
root = buildTree(arr)
root = insert(root, target)
return inorder(root)肝は insert 関数です。再帰で書くと「現在の node を返す」というシグネチャになり、None の場所に新しいノードを作って差し込めます。
Python
def insert(node, val):
if node is None:
return Node(val)
if val < node.val:
node.left = insert(node.left, val)
elif val > node.val:
node.right = insert(node.right, val)
return nodeJavaScript での実装例
JavaScript
function insert(node, val) {
if (node === null) return { val, left: null, right: null };
if (val < node.val) node.left = insert(node.left, val);
else if (val > node.val) node.right = insert(node.right, val);
return node;
}ロジックは Python と同じです。null に当たったら新規ノードを返し、親側で left / right に繋ぎ直しています。
よくある間違い
まず多いのが、挿入 後に in-order 走査で結果を返すのを忘れるケースです。本問では戻り値が in-order 配列なので、ここを揃えないとテストが落ちます。次に多いのは、再帰で node.left = insert(...) と 代入 を書き忘れて、せっかく作った新ノードがツリーに繋がらないパターンです。return node も忘れないようにします。最後に、挿入対象が 重複 していた場合の扱いです。本問では「既に存在する値は無視する」ので、== なら何もしません。
挿入時に
重複の扱いをどうするかは設計判断。本問では「無視」、別の問題では「カウンタを増やす」「複製を許す」など状況に応じて変える。
やってみよう
[]に5, 3, 8, 1を順番に入れて、in-order が[1, 3, 5, 8]になるか確認する- 同じ値
5を 2 回挿入しても、in-order に5は 1 回しか出ないことを確認する - 逆順
[10, 9, 8, 7]を空木に挿入すると、左に偏った棒のような木になることを観察する。これは平衡が崩れた状態
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は BST から値を検索する で、BST の不変条件「左 < 親 < 右」を使って目的の値を効率よく探す方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BST insert の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BST insert とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 配列
arrは BFS 順、欠損ノードはnull(Python では None) で表される - BST の不変条件 (左 < 親 < 右) を守って挿入する
- 戻り値は挿入後の in-order 走査結果の整数配列。重複は無視する
入出力例
test-cases.txt
bstInsert([], 5) → [5]
bstInsert([10,5,15], 7) → [5,7,10,15]
bstInsert([10,5,15], 20) → [5,10,15,20]
bstInsert([10,5,15,3,7,null,18], 1) → [1,3,5,7,10,15,18]
bstInsert([10,5,15], 10) → [5,10,15]
bstInsert([5,3,null,1], 4) → [1,3,4,5]