Pythonで二分探索木の削除を実装する方法をいくつか紹介します。以下のコード例では、二分探索木のノードを表すNodeクラスと、木全体を管理するBinarySearchTreeクラスを使用します。
まず、削除操作の基本的なアルゴリズムを説明します。以下の手順に従って、指定された値を持つノードを二分探索木から削除します。
- 削除する値と一致するノードを見つける。
- 削除するノードが葉ノードである場合、そのノードを削除します。
- 削除するノードが子ノードを1つだけ持つ場合、その子ノードを削除されるノードの位置に移動します。
- 削除するノードが子ノードを2つ持つ場合、次の手順に従います。 a. 削除するノードの右部分木における最小値のノードを見つけます。 b. 最小値のノードの値を削除するノードにコピーします。 c. 最小値のノードを削除します。
以下に、Pythonでの二分探索木の削除操作のコード例を示します。
上記のコード例では、BinarySearchTreeクラスにdeleteメソッドと_delete_nodeメソッドを実装しています。deleteメソッドは公開された削除メソッドであり、_delete_nodeメソッドは再帰的に呼び出される内部の削除メソッドです。
この実装では、指定された値を持つノードを削除する操作を行うことができます。削除後の二分探索木は、依然として二分探索木の性質を保持しています。
以上が、Pythonでの二分探索木の削除方法とコード例です。