エンジニア実践的基礎: ツリーセット/マップ

背景

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

BST セット/マップとは

セットとハッシュマップは検索が O(1) でできる、非常に優れたデータ構造です。しかし、いずれもキーがソートされない欠点があります。配列のインデックスに対応するハッシュ化されたキーがソートされないからです。

BST を使うとキーがソートされたセットとマップを実装できます。それぞれツリーセット・ツリーマップと呼ばれます。BST の全ての値をユニークにすればツリーセットになります。BST のノードの値を Pair のようにキーバリューを持てる構造体にすればソートマップになります。

あとは BST を inorder で走査すれば、キーを小さい順で取得できます。

実装

以前紹介した BST は重複を許さない BST でした。これはツリーセットと同義なので、実装は割愛します。ツリーマップは BST でキーバリューの構造体を使うだけです。

def insert(root, key, val):
    if not root:
        return TreeNode(key, val)
    
    if key > root.key:
        root.right = insert(root.right, key, val)
    elif key < root.key:
        root.left = insert(root.left, key, val)
    return root

計算量

配列ではなく木構造で実装するため、ハッシュセット/マップに比べて計算量は多いです。ハッシュセット/マップが検索・挿入・削除に O(1) だったのに対し、ツリーセット/マップは O(log n) です。