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

前回につづいて、「与えられた木が二分探索木か判定するアルゴリズム」について。

二分木が二分探索木であると判定するには、すべての節が制約を満足しているか調べればよいと前回の記事に書いた。これは幅優先探索でも実現できる。

次のコードは幅優先探索ですべての節が制約を満足しているか調べるものである。

import collections


def is_binary_tree_bst_bfs(tree: BstNode) -> bool:
    QueueEntry = collections.namedtuple('QueueEntry', ('node', 'lower', 'upper'))
    bfs_queue = collections.deque([QueueEntry(tree, float('-inf'), float('inf'))])

    while bfs_queue:
        entry = bfs_queue.popleft()
        if entry.node:
            if not (entry.lower <= entry.node.data <= entry.upper):
                return False
            bfs_queue.append(QueueEntry(entry.node.left, entry.lower, entry.node.data))
            bfs_queue.append(QueueEntry(entry.node.right, entry.node.data, entry.upper))

    return True

is_binary_tree_bst_bfs は根の節を受け取り QueueEntry オブジェクトにしてキュー (bfs_queue) につめる。 QueueEntry オブジェクトは BstNode オブジェクトと、その節を二分探索木として成立させるための下限値 (lower) と上限値 (upper) を含む namedtuple である。

ループの中でデキューして節を取得し、その値が lower 以上かつ upper 以下であるかチェックする。この条件を満足しなければ False を返す。満足していれば、「左の子」「右の子」とキューに詰めて、ループを継続する。ループを最後まで回せたら True を返す。

この方法では木を最後まで巡回せずとも False を返せる。このことから前回のコードより実行効率が高いと期待したが、サンプルデータに対してこのコードを走らせると前回のコードより遅かった (約30倍くらいの実行時間になる)。