【Python】二分探索木（BST）で最小値・最大値を求めるプログラムの書き方

二分探索木（Binary Search Tree：BST）の中から最小の要素と最大の要素を見つけるには、まず二分木のクラスを作成し、要素を追加するメソッドや特定のノードを検索するメソッドを定義します。その後、クラスのインスタンスを生成して、これらのメソッドを使って操作を行います。

二分探索木には「左側の子孫は必ず親より小さく、右側の子孫は必ず親より大きい」という重要な性質があります。そのため、最小値は常に最も左端のノード、最大値は常に最も右端のノードに存在します。この性質を利用すれば、木の高さに比例した計算量 O(h) で最小値・最大値を効率よく取得できます。

サンプルコード

class BST_Node:
   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 search_node(self, key):
      if self.key > key:
         if self.left is not None:
            return self.left.search_node(key)
         else:
            return None
      elif self.key < key:
         if self.right is not None:
            return self.right.search_node(key)
         else:
            return None
      return self

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

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

   def search_node(self, key):
      if self.root is not None:
         return self.root.search_node(key)

   def get_smallest_elem(self):
      if self.root is not None:
         current = self.root
         while current.left is not None:
            current = current.left
         return current.key

   def get_largest_elem(self):
      if self.root is not None:
         current = self.root
         while current.right is not None:
            current = current.right
         return current.key

my_instance = BSTree()

print('メニュー（キーの重複はないものとする）')
print('add <key>')
print('smallest')
print('largest')
print('quit')

while True:
   my_input = input('実行する操作を入力してください : ').split()

   operation = my_input[0].strip().lower()
   if operation == 'add':
      key = int(my_input[1])
      my_instance.add_elem(key)
   elif operation == 'smallest':
      smallest = my_instance.get_smallest_elem()
      print('最小の要素は : {}'.format(smallest))
   elif operation == 'largest':
      largest = my_instance.get_largest_elem()
      print('最大の要素は : {}'.format(largest))
   elif operation == 'quit':
      break

実行結果

メニュー（キーの重複はないものとする）
add <key>
smallest
largest
quit
実行する操作を入力してください : add 5
実行する操作を入力してください : add 8
実行する操作を入力してください : add 11
実行する操作を入力してください : add 0
実行する操作を入力してください : add 3
実行する操作を入力してください : smallest
最小の要素は : 0
実行する操作を入力してください : largest
最大の要素は : 11
実行する操作を入力してください : quit

コードの解説

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

• __init__（コンストラクタ）で、左・右・親の各ノードへの参照を「None」で初期化します。

• insert_elem メソッドにより、二分探索木のルール（左は小さい値・右は大きい値）に従って要素を挿入できます。

• search_node メソッドにより、ツリー内の特定のノードを再帰的に検索できます。

• もう一つのクラス「BSTree」を定義し、ルートノードを「None」で初期化しています。

• add_elem メソッドで、新しいノードをツリーに追加します。最初に追加された要素がルートになります。

• get_smallest_elem メソッドは、ルートから左の子をたどり続け、最も左端にあるノードの値（最小値）を返します。

• get_largest_elem メソッドは、ルートから右の子をたどり続け、最も右端にあるノードの値（最大値）を返します。

• BSTree クラスのインスタンスを生成し、ユーザーが選択した操作（add / smallest / largest / quit）に応じて処理を実行します。

なお、最小値・最大値の取得処理は、いずれも木の高さ h に対して O(h) の時間計算量で動作します。木がバランスしていれば O(log n) に近い効率で実行できるため、大量のデータを扱う場合でも高速に最小値・最大値を求められます。