LoginSignup
1
0

More than 3 years have passed since last update.

与えられた木が二分探索木か判定するアルゴリズム

Posted at

この記事は何か?

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

二分探索木

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

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

binary-search-tree.png

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

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

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

根の要素が取りうる値の幅は [-∞, ∞] である。つまり、どのような値でも問題がない。根から左側の子である 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_bstTrue を返す。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0