エンジニア実践的基礎: バイナリサーチツリー(BST)

背景

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

バイナリサーチツリー(BST)とは

バイナリサーチツリー (BST) はバイナリツリーの一種で、各ノードが持つ特性として、左部分木の全てのノードはルートより小さく、右部分木の全てのノードはルートより大きいというソートされた性質があります。この性質は木の全てのノードに再帰的に適用されます。

BSTを使用することで、ソートされた配列と同様に、値を O(log n) の時間で検索できます。さらに、BSTは挿入や削除も O(log n) の時間で行えるため、ソートされた配列よりも効率的です。ソートされた配列ではこれらの操作にO(n) の時間がかかります。

BST探索

木構造は再帰的なデータ構造であるため、最も簡単な巡回方法は再帰を使用することです。

例えば、次の BST で target = 3 を検索する場合で考えます。

バイナリサーチのように、ターゲットが中間要素より小さければ左へ、大きければ右へ進みます。BSTでも同様で、ターゲットが現在のノードより大きければ右部分木を、小さければ左部分木を再帰的に検索します。

ターゲット値のノードに到達すれば true を返し、到達できなければ false を返します。

def search(root, target):
    if not root:
        return False
    
    if target > root.val:
        return search(root.right, target)
    elif target < root.val:
        return search(root.left, target)
    else:
        return True

この例では、まずルート値をターゲットと比較します。2は小さすぎるため、右部分木を検索します。次のノードが3であり、ターゲットと一致するため、再帰呼び出しから true が返されます。ターゲットが存在しない場合は false を返します。

ポイントは探索範囲が半分ずつ狭まっていることです。 BST が素早く探索できる理由です。

時間計算量

平衡なバイナリツリーの場合、検索アルゴリズムは O(log n) の時間で動作します。平衡なツリーとは、左部分木と右部分木の高さが等しいか、差が1以下のツリーを指します。この場合、各操作でノードの半分を除外できるため、O(log n) の時間で検索が可能です。

最悪の場合、ツリーが一方向に偏っているとき、その高さはノード数と等しくなり、時間計算量は O(n) となります。