Pythonで二項ツリー（二項木）を実装する方法：オブジェクト指向による実装例

Pythonで二項ツリー（Binomial Tree）を実装するには、オブジェクト指向のアプローチを利用するのが効果的です。具体的には、クラスを定義し、その中に属性や操作用のメソッドを持たせます。クラスのインスタンスを生成することで、実際に二項ツリーの作成や結合といった操作を行えるようになります。

この記事では、ユーザーが対話的に操作できるメニュー形式のサンプルプログラムを通じて、二項ツリーの基本的な実装方法を解説します。

サンプルコード

class binomial_tree:
    def __init__(self, key):
        self.key = key
        self.children = []
        self.order = 0
    def add_at_end(self, t):
        self.children.append(t)
        self.order = self.order + 1
my_tree = []
print('Menu')
print('create <key>')
print('combine <index1> <index2>')
print('exit')
while True:
    option = input('What do you wish like to do? ').split()
    operation = option[0].strip().lower()
    if operation == 'create':
        key = int(option[1])
        b_tree = binomial_tree(key)
        my_tree.append(b_tree)
        print('Binomial tree has been created.')
    elif operation == 'combine':
        index_1 = int(option[1])
        index_2 = int(option[2])
        if my_tree[index_1].order == my_tree[index_2].order:
            my_tree[index_1].add_at_end(my_tree[index_2])
            del my_tree[index_2]
            print('Binomial trees have been combined.')
        else:
            print('Order of trees need to be the same to combine them.')
    elif operation == 'exit':
        print("Exit")
        break
    print('{:>8}{:>12}{:>8}'.format('Index', 'Root key', 'Order'))
    for index, t in enumerate(my_tree):
        print('{:8d}{:12d}{:8d}'.format(index, t.key, t.order))

実行結果

Menu
create <key>
combine <index1> <index2>
exit
What do you wish like to do? create 7
Binomial tree has been created.
Index Root key Order
0 7 0
What do you wish like to do? create 11
Binomial tree has been created.
Index Root key Order
0 7 0
1 11 0
What do you wish like to do? create 4
Binomial tree has been created.
Index Root key Order
    0     7     0
    1     11    0
    2     4     0
What do you wish like to do? combine 0 1
Binomial trees have been combined.
Index Root key Order
    0     7     1
    1     4     0
What do you wish like to do? exit
Exit

コードの解説

• まず、「binomial_tree」という名前のクラスを定義します。
• コンストラクタでは、ノードのキー（key）、子ノードのリスト（children）、そして次数（order）を初期化します。
• 「add_at_end」メソッドは、指定されたツリーを子として末尾に追加し、自身の次数を1つ増やします。
• メイン処理では空のリスト「my_tree」を作成し、複数の二項ツリーを管理します。
• ユーザーはメニューから操作を選択できます。「create」を指定するとキーの値を受け取り、新しい二項ツリーのインスタンスを生成してリストに追加します。
• 各操作の後には、現在のツリーの一覧がインデックス・ルートのキー値・次数とともに表示されます。
• 「combine」を選択した場合は、結合したい2つのツリーのインデックスを指定します。両者の次数が同じ場合のみ結合が行われ、一方のツリーが他方の子として追加され、リストから削除されます。
• 次数が異なる場合は、結合には同じ次数が必要である旨のメッセージが表示されます。

なお、二項ツリーはヒープや優先度付きキューの実装で利用される重要なデータ構造です。同じ次数の二項ツリー同士を結合すると、次数が1つ大きい二項ツリーになるという性質があります。このサンプルコードはその基本原理をシンプルに体感できる内容となっています。