二分探索木 (BST) への挿入
二分探索木 は、部品が左右 2 つの札を持つ形の構造です。守るべき決まりは 1 つだけで、左にぶら下がる値は自分より小さく、右にぶら下がる値は自分より大きい、というものです。この決まりが守られている限り、探したい値は毎回どちらか片側を丸ごと捨てながら降りていけます。
決まりは、外から 1 行で壊せる
決まりを持つ構造で怖いのは、外から属性を直接書き換えられることです。木で言えば、左の札に自分より大きい値をぶら下げられた瞬間、探索は間違った枝を降りるようになります。壊れたことに気づくのは、ずっと後の「あるはずの値が見つからない」場面です。
Python
class Wallet:
def __init__(self):
self._balance = 0
def deposit(self, amount):
self._balance += amount
def withdraw(self, amount):
if amount > self._balance:
return False
self._balance -= amount
return Truewithdraw は残高以上を引けないよう見張っています。ところが w._balance = -5000 と書かれると、その見張りを素通りして残高がマイナスになります。
入り口をメソッド 1 つに絞る
Python では、頭にアンダースコアを付けた名前を「外から触らない」の合図に使います。文法で禁止されるわけではなく、あくまで約束です。Java の private、JavaScript の # 付きの名前のように、文法で止められる言語もあります。
JavaScript
class Wallet {
#balance = 0;
deposit(amount) { this.#balance += amount; }
balance() { return this.#balance; }
}狙いはどちらも同じで、状態を変えられる場所を減らすことです。木も同じで、左右の札を外から繋ぎ替えさせず、値を 1 つ受け取る挿入の手続きだけを入り口にします。ルートから降りていき、空いている場所に着いたらそこへ新しい部品を置く。降りる向きは値の比較で決まるので、決まりは自動的に守られます。
1, 2, 3, 4, 5の順に入れると、右にだけ伸び続けて一直線になります。決まりは守られていますが枝分かれしないので、探索は端から順に見るのと同じ手間になります。実用の実装は、傾きを検知して形を組み替える仕組みを足してこれを防ぎます。
やってみよう
bstInsertAll(values) を書いてください。値と左右 2 つの札を持つクラスを定義し、values を先頭から 1 つずつ木に入れます。空いている場所に着いたら新しい部品を返し、呼び出した側でそれを左右どちらかの札に繋ぐ形にすると、再帰で素直に書けます。既にある値と等しいときは何もしません。最後に、左、自分、右の順にたどって値を集めると、昇順に並んだ配列が得られます。
要件
Nodeクラスを定義し、value/left/rightを持たせる- 再帰関数で BST に挿入する。
Noneに当たったら新ノードを返し、親側でleft/rightに繋ぐ - in-order (左 → 自分 → 右) で走査して、ソート済み配列を返す。重複は無視する
入出力例
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]ヒント
