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

2024-03-01 00:07 二分探索木ノードの削除C言語

ノードの削除には、いくつかのケースが存在します。以下では、それぞれのケースについて詳しく説明し、コード例を示します。

  1. 削除するノードが葉ノード（子ノードを持たない）の場合:

    • 削除対象のノードをその親ノードから切り離すだけで削除できます。
    void deleteNode(Node* root, int key) {
   // ノードの検索処理を実装する
   // 削除対象のノードを見つける
   // 削除対象のノードの親ノードの子ポインタをNULLに設定する
   // メモリの解放処理を行う（必要な場合）
}

  2. 削除するノードが1つの子ノードを持つ場合:

    • 削除対象のノードを、その子ノードで置き換えます。
    void deleteNode(Node* root, int key) {
   // ノードの検索処理を実装する
   // 削除対象のノードを見つける
   // 削除対象のノードの子ノードを削除対象のノードの親ノードに接続する
   // メモリの解放処理を行う（必要な場合）
}

  3. 削除するノードが2つの子ノードを持つ場合:

    • 削除対象のノードを、その右部分木の最小値で置き換えるか、左部分木の最大値で置き換えます。
    void deleteNode(Node* root, int key) {
   // ノードの検索処理を実装する
   // 削除対象のノードを見つける
   // 削除対象のノードの右部分木の最小値または左部分木の最大値を削除対象のノードにコピーする
   // 削除対象のノードの右部分木または左部分木から、コピーした値を持つノードを再帰的に削除する
}

以上が、BSTにおけるノードの削除方法とそれぞれの場合のコード例です。ノードの削除には、ノードの検索と適切なリンクの調整が必要です。これらのコード例を参考にして、実際のプログラムでノードの削除を実装してみてください。