エンジニア実践的基礎: BST 幅優先探索

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

幅優先探索とは？

深さ優先探索では縦に走査しました。幅優先探索は横に走査します。ペンキを横に塗って壁を埋めるイメージです。

赤色の数字が訪問順

最初の行の「4」を訪問するのは簡単です。問題は次の行をどこに保存するかです。つまり「3」と「6」をどこかに保存しておいて、2行目を走査する時に取り出せるようにする必要があります。

この保存する場所に使われるのがキューです。キューは行列のように最初に入れたデータから順に取り出せるデータ構造です。1行目を走査中に、2行目のノードをキューに格納します。2行目のノードは1行目のノードの子ノードです。キューに詰めたノードを先頭から取り出すと2行目の走査を開始できます。あとは最後の行まで繰り返すだけです。

階層別にキューに格納された値

実装

def bfs(root):
    queue = deque()

    if root:
        queue.append(root)
    
    while len(queue) > 0: # キューに値がある = 訪問していないノードがある
        for i in range(len(queue)): # 階層分のノードだけ訪問
            curr = queue.popleft()
            print(curr.val)
            if curr.left:
                # 左子ノード格納
                queue.append(curr.left)
            if curr.right:
                # 右子ノード格納
                queue.append(curr.right)

計算量

時間計算量は全てのノードを訪問するため O(n) です。空間計算量は、最悪でおおよそ半分のノードを格納するので O(n) です。完全に平行な BST であればリーフノードの階層が一番多くなり、その数はおおよそ半分くらいという計算です。