この記事は何か?

入力として木構造が渡されたとき、それが二分探索木かどうか調べるアルゴリズムについて紹介する。

二分探索木

二分探索木は二分木であり、節の左側の子には節と同じか小さい要素しか含まず、右側の子には節と同じか大きい要素しか含まないものを指す。

次の木は二分探索木の例である。

すべての部分木で左側の子が節と同じかそれより小さく、右側の子が節と同じかそれより大きい要素を持っている。

二分探索木かどうか判定するアルゴリズム

二分探索木の子の節が取りうる値の幅は、親の節よりも狭くなる。上の二分探索木を例に考えよう。

根の要素が取りうる値の幅は [-∞, ∞] である。つまり、どのような値でも問題がない。根から左側の子である 7 の節が取りうる値は [-∞, 19] である。なぜなら、根の左側の子は根よりも大きい値であってはならないからである。次に 7 の節の右側の子について考えよう。この節の取りうる値は [7, 19] で、実際の値は 11 である。親が 7 なので、右側の子は 7 より大きい値でなければならず、親が 19 より小さいという制約を持っているため、この節も同じ制約を引き継ぐためである。

このように、根から葉に向かって取りうる値のレンジを更新しつつ、実際の値がそのレンジにおさまっているかどうかを調べることで、与えられた木が二分探索木かどうかを判定できる。

具体的な実装は次のようになる。

# 木のノードは BstNode クラスで表現する
class BstNode:
    def __init__(self, data=None, left=None, right=None):
        self.data, self.left, self.right = data, left, right


def is_binary_tree_bst(tree: BstNode, low_range=float('-inf'), high_range=float('inf')) -> bool:
    if not tree:
        return True

    if not (low_range <= tree.data <= high_range):
        return False

    return \
        is_binary_tree_bst(tree=tree.left, low_range=low_range, high_range=tree.data) and \
        is_binary_tree_bst(tree=tree.right, low_range=tree.data, high_range=high_range)

根から再帰的に左右の子の部分木を探索し、すべての節の値がレンジの範囲内におさまっていれば is_binary_tree_bst は True を返す。