二分探索木におけるノードの削除方法

ノードの削除にはいくつかのケースがあります。以下に、それぞれのケースに対するシンプルで簡単な方法とコード例を示します。

削除するノードが葉ノードの場合: 葉ノードは子を持たないノードです。削除するノードが葉ノードであれば、そのノードを単純に削除するだけです。

例:

def delete_node(root, key):
   if root is None:
       return root
   if key < root.key:
       root.left = delete_node(root.left, key)
   elif key > root.key:
       root.right = delete_node(root.right, key)
   else:
       if root.left is None:
           return root.right
       elif root.right is None:
           return root.left
       root = None
   return root

削除するノードが子を1つだけ持つ場合: 削除するノードが子を1つだけ持つ場合、その子ノードを削除するノードの位置に移動させます。

例:

def delete_node(root, key):
   if root is None:
       return root
   if key < root.key:
       root.left = delete_node(root.left, key)
   elif key > root.key:
       root.right = delete_node(root.right, key)
   else:
       if root.left is None:
           return root.right
       elif root.right is None:
           return root.left
       temp = root.right
       root = root.left
   return root

削除するノードが子を2つ持つ場合: 削除するノードが子を2つ持つ場合、削除するノードの直後のノード（右部分木の最小値）または直前のノード（左部分木の最大値）を見つけて、そのノードと値を入れ替えます。そして、入れ替えたノードを再帰的に削除します。

例:

def delete_node(root, key):
   if root is None:
       return root
   if key < root.key:
       root.left = delete_node(root.left, key)
   elif key > root.key:
       root.right = delete_node(root.right, key)
   else:
       if root.left is None:
           return root.right
       elif root.right is None:
           return root.left
       temp = find_min(root.right)
       root.key = temp.key
       root.right = delete_node(root.right, temp.key)
   return root
def find_min(node):
   current = node
   while current.left is not None:
       current = current.left
   return current

以上が、二分探索木におけるノードの削除方法とコード例です。これらの方法を使用することで、効率的かつ正確にノードを削除することができます。