二分探索木 (BST) への挿入

二分探索木 は、部品が左右 2 つの札を持つ形の構造です。守るべき決まりは 1 つだけで、左にぶら下がる値は自分より小さく、右にぶら下がる値は自分より大きい、というものです。この決まりが守られている限り、探したい値は毎回どちらか片側を丸ごと捨てながら降りていけます。

決まりは、外から 1 行で壊せる

決まりを持つ構造で怖いのは、外から属性を直接書き換えられることです。木で言えば、左の札に自分より大きい値をぶら下げられた瞬間、探索は間違った枝を降りるようになります。壊れたことに気づくのは、ずっと後の「あるはずの値が見つからない」場面です。

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 True

withdraw は残高以上を引けないよう見張っています。ところが w._balance = -5000 と書かれると、その見張りを素通りして残高がマイナスになります。

入り口をメソッド 1 つに絞る

Python では、頭にアンダースコアを付けた名前を「外から触らない」の合図に使います。文法で禁止されるわけではなく、あくまで約束です。Java の private、JavaScript の # 付きの名前のように、文法で止められる言語もあります。

class Wallet {
  #balance = 0;
  deposit(amount) { this.#balance += amount; }
  balance() { return this.#balance; }
}

狙いはどちらも同じで、状態を変えられる場所を減らすことです。木も同じで、左右の札を外から繋ぎ替えさせず、値を 1 つ受け取る挿入の手続きだけを入り口にします。ルートから降りていき、空いている場所に着いたらそこへ新しい部品を置く。降りる向きは値の比較で決まるので、決まりは自動的に守られます。

解説

1, 2, 3, 4, 5 の順に入れると、右にだけ伸び続けて一直線になります。決まりは守られていますが枝分かれしないので、探索は端から順に見るのと同じ手間になります。実用の実装は、傾きを検知して形を組み替える仕組みを足してこれを防ぎます。

やってみよう

ひな形の TODO を完成させてください。空への挿入と、大小による再帰・枝の接続を自分で書きます。結果を左・自分・右の順に集める走査は用意しました。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

例は 9 の左に 4、右に 13 がある木へ 6 を入れる場面です。9 より小さいので左へ、4 より大きいので右へ進み、その空き場所に置きます。再帰が返したノードを親の枝につなぎ直す必要があります。挿入の本体だけを書きます。Node は関数の外で定義済みです。入力列を読む部分と、結果を左・自分・右の順に集める inorderTraverse も用意しました。走査では空なら止まり、左の枝をたどり、自分の値を追加し、右の枝をたどります。

1. 空への挿入と、大小による再帰・枝の接続を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える