Pythonで二分探索木（BST）を使ってリストをソートするプログラム

二分探索木（Binary Search Tree）を使ってデータをソートしたい場合、専用のクラスを作成し、その中に「要素の挿入」や「中順走査（inorder traversal）」といった操作を行うメソッドを定義します。二分探索木の性質上、中順走査を実行することで、要素が昇順に並び替えられた結果を得ることができます。

この手法は「木構造ソート（Tree Sort）」とも呼ばれます。以下に具体的な実装例を示します。

サンプルコード

class BinSearchTreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def insert_elem(self, node):
        if self.key > node.key:
            if self.left is None:
                self.left = node
                node.parent = self
            else:
                self.left.insert_elem(node)
        elif self.key <= node.key:
            if self.right is None:
                self.right = node
                node.parent = self
            else:
                self.right.insert_elem(node)

    def inorder_traversal(self):
        if self.left is not None:
            self.left.inorder_traversal()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.inorder_traversal()

class BinSearchTree:
    def __init__(self):
        self.root = None

    def inorder_traversal(self):
        if self.root is not None:
            self.root.inorder_traversal()

    def add_val(self, key):
        new_node = BinSearchTreeNode(key)
        if self.root is None:
            self.root = new_node
        else:
            self.root.insert_elem(new_node)

my_instance = BinSearchTree()

my_list = input('Enter the list of numbers... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
    my_instance.add_val(x)
print('Sorted list: ')
print(my_instance.inorder_traversal())

出力結果

Enter the list of numbers... 67 54 89 0 11 34 99
Sorted list:
0 11 34 54 67 89 99

コードの解説

• 必要な属性を持つ「BinSearchTreeNode」クラスを作成します。

• __init__メソッドでは、「left」「right」「parent」の各ノードを「None」で初期化します。

• 「insert_elem」メソッドは、ツリーに新しいノードを追加するために定義されています。キーの大小関係を比較しながら、適切な位置へ再帰的にノードを挿入します。

• 「inorder_traversal」メソッドは、左の子ノード → 自身 → 右の子ノードの順に訪問する中順走査を実行します。

• 次に、ツリー全体を管理するための「BinSearchTree」クラスを定義します。

• このクラスでは、ルートノードを「None」に初期化します。

• 「inorder_traversal」メソッドにより、ルートから中順走査を開始できます。

• 「add_val」メソッドは、受け取った値から新しいノードを生成し、ツリーに追加します。

• 「BinSearchTree」クラスのインスタンスを作成します。

• ユーザーからスペース区切りの数値リストを入力として受け取ります。

• 入力された各数値をノードとして追加し、二分探索木を構築します。

• 最後に中順走査を実行することで、昇順にソートされた結果が得られます。

• ソート済みのリストがコンソールに出力されます。

計算量について

この手法の平均計算量は O(n log n) です。ただし、入力データによって木のバランスが崩れる（偏った木になる）場合、最悪で O(n²) まで計算量が悪化する可能性がある点には注意が必要です。安定した性能を求める場合は、AVL木や赤黒木のような自己平衡型の二分探索木の採用も検討するとよいでしょう。