二分探索木 (BST) の応用操作。挿入と削除を擬似言語で読みこなします。
日野 こむぎ
二分探索木に値を追加するのって、どうやるの?
藤森 さやか 先生
ルールは単純。
「key < ノードなら左へ、key > ノードなら右へ」を末端まで降りて、null の位置に新ノードを挿入するの。
青木 澪
つまり、挿入の擬似言語はこうなる、という理解で合っていますか?
/* BST に value を挿入 */
○ 手続: insertBST(ノード型: node, 整数型: value)
if (node = null)
/* 末端に到達 → 新ノードを作成 */
node ← 新しいノード
node.value ← value
node.left ← null
node.right ← null
return node
endif
if (value < node.value)
node.left ← insertBST(node.left, value)
elseif (value > node.value)
node.right ← insertBST(node.right, value)
endif
/* value = node.value の場合は重複として無視 */
return node
桃井 すみれ
わぁ、再帰でシンプルに書けるんですねぇ
青木 澪
計算量は平均 O(log n)、最悪 O(n)。
最悪ケースは木が偏ったとき (連結リストになった状態)。
これを防ぐのがAVL木・赤黒木などの平衡二分探索木よ。
藤森 さやか 先生
削除はもう少し複雑。
3つのケースに分けて考えるの:
/* BST から target を削除 */
○ 手続: deleteBST(ノード型: node, 整数型: target)
if (node = null) return null
if (target < node.value)
node.left ← deleteBST(node.left, target)
elseif (target > node.value)
node.right ← deleteBST(node.right, target)
else
/* 削除対象を発見 */
if (node.left = null) return node.right /* ケース1: 左子なし */
if (node.right = null) return node.left /* ケース2: 右子なし */
/* ケース3: 子が2つある場合 */
/* 右部分木の最小値で置き換え (in-order successor) */
node.value ← findMin(node.right)
node.right ← deleteBST(node.right, node.value)
endif
return node
日野 こむぎ
要は、子の数で場合分けするってこと?
よっしゃ、あたししっかり覚える!
青木 澪
そう、特に「子が2つある場合」が肝心なの。
補足すると、in-order successor (右部分木の最小値) で置き換えれば、BST の性質が保たれます。
藤森 さやか 先生
試験では「次の操作後の木の状態は?」「以下のBSTから値Xを削除した後の中順走査結果は?」のような問題が出るわ。
確認クイズ
二分探索木で、子を2つ持つノードを削除する場合の標準的な手法はどれか。
- 何もしない
- 右部分木の最小値 (in-order successor) で置き換える
- ルートを削除
- 全ノードを削除
こたえを見る
正解: 2. 右部分木の最小値 (in-order successor) で置き換える
BST で2つの子を持つノードを削除する場合、右部分木の最小値 (in-order successor) で値を置き換え、その successor を削除します。これによりBST性質 (左<親<右) が保たれます。左部分木の最大値で置き換える方法も同等です。
