BST に値を挿入する
空いている枝は 6 か所あるのに、置ける場所は 1 つしかない
次の木に 9 を足したいとします。
子のいない場所を数えると、3 の左右、7 の左右、15 の左、18 の左右と 6 か所あります。しかし 9 を置いてよいのは 7 の右だけです。他のどこに置いても、木の形としては成立するのに「順番に取り出すと昇順になる」という約束が壊れます。
この約束が二分探索木 (BST) の全部です。あるノードから見て、左にぶら下がる値はすべてそのノードより小さく、右にぶら下がる値はすべて大きい。直接の子だけでなく、その先の孫もひ孫も、です。
比べるたびに、行き先が 1 つに決まる
境目が決まっていれば、行き先は迷いようがありません。点数を 3 段階に分ける関数を思い浮かべてください。
JavaScript
// 別題材 — 境目が決まっていれば、行き先は 1 つ
function grade(score) {
if (score < 60) return "C";
if (score < 80) return "B";
return "A";
}BST は、この境目がノードの値そのものになったものです。10 と比べて小さければ左、大きければ右。降りた先の 5 でまた比べ、7 でまた比べる。降りるほど境目が増えて、9 の居場所が絞られていきます。
行き止まりに着いたら、そこが置き場所
9 を入れるときの比較を並べると次のようになります。
| 今いるノード | 比較 | 進む先 |
|---|---|---|
| 10 | 9 は 10 より小さい | 左の 5 へ |
| 5 | 9 は 5 より大きい | 右の 7 へ |
| 7 | 9 は 7 より大きい | 右へ。そこは空 |
空にたどり着いた時点で終わりです。「もっと良い場所があるかもしれない」と引き返す必要はありません。途中で 1 回でも違う方向へ進んでいたら約束が壊れるので、通れる道は最初から 1 本しかないのです。
同じ値がすでにある場合は、比較が「小さい」でも「大きい」でもない状態になります。今回はそこで何もせずに終わります。
配列で渡された木を、先にノードへ直す
課題の入力は [10, 5, 15, 3, 7, null, 18] のような、上の段から左詰めで並べた配列です。この形のまま枝をたどるのは骨が折れるので、先にノードの形へ組み直します。添字 i のノードの子は次の位置にいます。
JavaScript
const left = arr[2 * i + 1];
const right = arr[2 * i + 2];null の位置は「そこにノードが無い」という意味なので、繋がずに飛ばします。組み直したら値を 1 つ入れ、最後に小さい順で取り出して配列にします。
入れた後に取り出すところまでが戻り値です。木を直しただけで返すと、形は合っているのに答えが合いません。
要件
- 配列
arrは BFS 順、欠損ノードはnull(Python では None) で表される - BST の不変条件 (左 < 親 < 右) を守って挿入する
- 戻り値は挿入後の in-order 走査結果の整数配列。重複は無視する
入出力例
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]ヒント
