Pythonで二分探索木（BST）をシリアライズ・デシリアライズする方法

シリアライズとデシリアライズとは？

本記事では、二分探索木（BST：Binary Search Tree）をシリアライズおよびデシリアライズするアルゴリズムをPythonで設計する方法を解説します。

シリアライズ（直列化）とは、データ構造やオブジェクトをビット列や文字列へ変換し、ファイルやメモリバッファへの保存、あるいはネットワーク越しの送信を可能にする処理のことです。一方、デシリアライズ（逆直列化）は、シリアライズされたデータから元のデータ構造を復元する逆のプロセスを指します。

例として、次のような二分木を考えてみます。

[5, 2, 9, 1, 3, 7]

この場合、処理結果は以下のようになります。

• シリアライズ結果： 5.2.9.1.3.7.N.N.N.N.N.N.N
• デシリアライズ結果（中順走査）： 1, 2, 3, 5, 7, 9,

ここでは「N」がnull（存在しないノード）を表し、各ノードの値はドット（.）で区切られています。この形式により、木の構造全体をひとつの文字列として正確に表現できます。

アルゴリズムの考え方

この問題は、幅優先探索（BFS：レベル順走査）を利用することで効率的に解けます。木を上から下へ、同じレベル内では左から右へと辿りながら、各ノードの情報を順番に記録していきます。

serialize() の手順

1. 引数として根ノード root を受け取る serialize() 関数を定義します。
2. 結果を格納するための新しいリスト res を用意します。
3. キューを1つ作成し、root を挿入します。
4. キューが空になるまで、以下を繰り返します。
   • キューの先頭要素を current として取り出し、res の末尾に追加します。
   • current がnullの場合は、そこでループを終了します。
   • current.left が存在すればキューに追加し、存在しなければ None を追加します。
   • current.right についても同様の処理を行います。
5. 空文字列 s を用意し、res の各要素を先頭から走査します。
   • 要素が有効なノードであれば、その値（data）を s に連結します。
   • nullであれば、代わりに「N」を連結します。
   • 最後の要素以外の後ろには、区切り文字「.」を連結します。
6. 完成した文字列 s を返します。

deserialize() の手順

1. 文字列 data を受け取る deserialize() 関数を定義します。
2. data をドット（.）で分割し、要素のリストに変換します。
3. ノード管理用のスタック（リスト）を新しく用意します。
4. data[0] が「N」であれば、空の木を意味するため None を返します。
5. data[0] の値を持つ新しいノードを root として作成し、スタックに追加します。
6. インデックス i = 1、current = 0 とし、i が data の長さに達するまで以下を繰り返します。
   • data[i] が「N」でなければ新しいノードを作成し、stack[current] の左の子として設定したうえでスタックに追加します。「N」であれば左の子を None とします。
   • 続く要素（右の子に相当）についても同様の処理を行います。
   • current と i をそれぞれ1ずつ進めます。
7. 復元した root を返します。

Pythonでの実装例

理解を深めるために、実際の実装コードを見ていきましょう。

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)


def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree


def print_tree(root):
    # 中順走査（inorder traversal）で表示
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)


class Codec:
    def serialize(self, root):
        res = []
        queue = [root]
        while queue:
            while True and queue:
                current = queue[0]
                res.append(current)
                queue.pop(0)
                if current:
                    break
            if not current:
                break
            if current.left:
                queue.append(current.left)
            else:
                queue.append(None)
            if current.right:
                queue.append(current.right)
            else:
                queue.append(None)

        s = ""
        for i in range(len(res)):
            if res[i]:
                s += str(res[i].data)
            else:
                s += "N"
            if i == len(res) - 1:
                break
            s += "."
        return s

    def deserialize(self, data):
        data = data.split(".")
        stack = []
        if data[0] == 'N':
            return None
        root = TreeNode(int(data[0]))
        stack.append(root)
        i = 1
        current = 0
        while i < len(data):
            if data[i] != 'N':
                temp = TreeNode(int(data[i]))
                stack[current].left = temp
                stack.append(temp)
            else:
                stack[current].left = None
            i += 1
            if data[i] != 'N':
                temp = TreeNode(int(data[i]))
                stack[current].right = temp
                stack.append(temp)
            else:
                stack[current].right = None
            current += 1
            i += 1
        return root


ob = Codec()
root = make_tree([5, 2, 9, 1, 3, 7])
ser = ob.serialize(root)
print('Serialization:', ser)
print_tree(ob.deserialize(ser))

実行結果

入力

[5, 2, 9, 1, 3, 7]

出力

Serialization: 5.2.9.1.3.7.N.N.N.N.N.N.N
1, 2, 3, 5, 7, 9,

計算量について

このアルゴリズムでは、各ノードを一度だけ訪問するため、シリアライズ・デシリアライズともに時間計算量は O(n) です。また、キューとスタックが最大で木の全ノード分の参照を保持しうるため、空間計算量も O(n) となります。ノード数に比例して処理が線形に増加するため、大規模な木に対しても安定した性能が期待できます。