【G検定】探索木と幅優先探索・深さ優先探索

探索木

検索木は、情報を効率的に検索および取得できるように、データを階層的に編成および格納するためにコンピュータ サイエンスで使用されるデータ構造です。ツリーの各ノードはデータ項目を表し、各ノードには 0 個以上の子があり、ノード間に親子関係が形成されます。ツリーは通常、ルート ノードが階層の最上位ノードであり、ノードの子がそのノードの親によって表されるデータのサブカテゴリまたはサブ項目を表すように編成されます。

検索木の構造により、バイナリ検索や深さ優先検索などの効率的な検索アルゴリズムが可能になります。検索ツリーでは、検索アルゴリズムが検索に関係のないツリーの大部分をすばやく除外できるようにデータが編成され、検索する必要があるデータの量が削減され、検索プロセスが高速化されます。

探索木には、二分探索木・三分探索木・B木・a-b木など、いくつかの種類があります。

以下は二分探索木のイメージ図です。

幅優先探索

木構造にある各ノードを1度だけ訪問することを探索（走査）と呼び、全探索の代表例として、深さ優先探索(DFS)と幅優先探索(BFS)があります。

幅優先探索は、深さごとに浅い順かつ左側から探索していく方式です。

最短距離でゴールにたどり着く解を見つけやすくなりますが、探索の途中で立ち寄ったノードをすべて記憶しておく必要がありメモリが多く必要となります。

深さ優先探索

深さ優先探索は、行きがけ順（先行順 / 前順 / preorder）、通りがけ順（中間順 / 間順 / inorder）、帰りがけ順（後行順 / 後順 / postorder）の3つに分類することができます。

以下の図は行きがけ順の例となります。

その他の探索木

二分探索木: BST は、ノードの左側のサブツリーの各ノードの値がノードの値より小さく、右側のサブツリーの各ノードの値がノードの値より大きいツリーです。BST は、ソートされたリスト内の値を効率的に検索するために使用されます。BST で値を検索するには、平均で O(log n) 時間がかかります。ここで、n はツリー内のノードの数です。

バランス探索木: バランス探索木は、ツリーの高さがツリーに格納されている要素数の対数になるようにバランス プロパティを維持する検索ツリーの一種です。このプロパティにより、BST と比較して検索、挿入、および削除操作が高速になります。BST では、ツリーの高さが格納された要素の数に比例するため、操作が遅くなる可能性があります。バランス検索木の例には、AVL木、Red-Black木、および B木が含まれます。

AVL木: AVL木は自己均衡二分探索ツリーです。任意のノードの左右のサブツリーの高さの差を最大 1 に維持することで、バランスを確保します。このプロパティにより、ツリーの高さが、ツリーに格納されている要素の数の対数になることが保証されます。

赤黒木: 赤黒木は、別の種類の自己平衡二分探索木です。ツリーのノードを赤または黒に色付けすることでバランスを維持し、ツリーが特定のプロパティ (ルートからリーフ ノードへのすべてのパスの黒いノードの数が同じであるなど) を満たすようにします。

B木: B木は、ディスクベースのデータ ストレージ システムに使用される一種の平衡検索ツリーです。二分探索木とは異なり、B木では複数のキーと値を各ノードに格納できます。これにより、値を見つけるために必要なディスク アクセスの回数を減らすことができるため、B木は大規模なデータセットに特に役立ちます。