この記事は何か?
入力として木構造が渡されたとき、それが二分探索木かどうか調べるアルゴリズムについて紹介する。
二分探索木
二分探索木は二分木であり、節の左側の子には節と同じか小さい要素しか含まず、右側の子には節と同じか大きい要素しか含まないものを指す。
次の木は二分探索木の例である。
すべての部分木で左側の子が節と同じかそれより小さく、右側の子が節と同じかそれより大きい要素を持っている。
二分探索木かどうか判定するアルゴリズム
二分探索木の子の節が取りうる値の幅は、親の節よりも狭くなる。上の二分探索木を例に考えよう。
根の要素が取りうる値の幅は [-∞, ∞] である。つまり、どのような値でも問題がない。根から左側の子である 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 を返す。