トリッキーコードネット トップへ戻る   C/C++, Java, Perl, PHP, JavaScript, アルゴリズム, ショートコーディング, IOCCCコードの解説, 等々

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> データ構造 >> 二分探索木 - ノード削除 (C言語)

二分探索木(Binary Search Tree) - ノード削除

こちらの続きです。

次は、ツリー内のノードを削除する関数を実装します。
追加・検索と比べて少々ややこしいですが・・・・、まぁ頑張っていきましょう^^

削除するユニークIDを指定し、まずは検索関数(← 前ページにて実装済)を使い、削除対象のノードを取得します。

/*
 * idを指定し、該当するノードを削除する。
 *
 * [戻り] 成功時:0 / 該当するノードがない:1
 */
int deleteNode(int delId)
{
    node * n, * tmp;

    if ( ! (n = searchNode(delId)) ) { // 指定されたidを持つノードがない
        return 1;
    }

    ~~ 処理 ~~

}
この削除対象ノード(上記コード中の n )に子が存在するか否かによって、その後の処理が大きく異なります。 それでは、簡単なパターンから見ていきます。

削除対象ノードに子がいない場合

二分探索木 - 子がいないノードの削除 さて、この状態で n を削除する方法ですが、 単純に n を releaseNodeData関数(←前々ページにて実装済)に渡せば良いワケではありません。 「nの親ノードが nを指している」ポインタを、NULLにセットする必要があります。 そして、もしnがルートの場合は、ルートを指すポインタ(g_root)をNULLにセットする必要があります。 コードは以下の様になります。
 1 : /*** 削除対象のノードが、子を持たない場合 ***/
 2 : if (! n -> left && ! n -> right) {
 3 :
 4 :     if (n == g_root) {
 5 :         g_root = NULL;
 6 :     }
 7 :     else {
 8 :         if (n -> parent -> left == n)
 9 :             n -> parent -> left = NULL;
10 :         else
11 :             n -> parent -> right = NULL;
12 :     }
13 :
14 :     releaseNodeData(n);
15 : }
8~11行目: 親ノードがnを、右の子として指しているのか、左の子として指しているのかを判定し、nを指している子側のポインタをNULLにセットします。

削除対象ノードが、左の子のみを持つ場合

二分探索木 - 左の子のみを持つノードの削除 コードを見ながら説明します。
 1 : /*** 削除対象のノードが、左の子のみを持つ場合 ***/
 2 : if (n -> left && ! n -> right) {
 3 :
 4 :     if (n == g_root) {
 5 :         g_root = n -> left;
 6 :         g_root -> parent = NULL;
 7 :     }
 8 :     else {
 9 :         if (n -> parent -> left == n)
10 :             n -> parent -> left = n -> left;
11 :         else
12 :             n -> parent -> right = n -> left;
13 :
14 :         n -> left -> parent = n -> parent;
15 :     }
16 :
17 :     releaseNodeData(n);
18 : }
4~7行目: nがルートの場合、nの左子ノードにルートを譲り、ルート(←この時点ではn)の親ノードを指すポインタをNULLにセットします。 9~12行目: 「nの親ノードがnを指しているポインタ」に、nの左子ノードをセットします。 14行目: 「nの左子ノードが、親ノードを指すポインタ」に、nの親ノードをセットします。 ・・・つまり、n が削除された後でも、各ノードが 親/左の子/右の子 を指すポインタの連結が、 途切れない用にします。

削除対象ノードが、右の子のみを持つ場合

二分探索木 - 右の子のみを持つノードの削除
 1 : /*** 削除対象のノードが、右の子のみを持つ場合 ***/
 2 : if (n -> right && ! n -> left) {
 3 :
 4 :     if (n == g_root) {
 5 :         g_root = n -> right;
 6 :         g_root -> parent = NULL;
 7 :     }
 8 :     else {
 9 :         if (n -> parent -> left == n)
10 :             n -> parent -> left = n -> right;
11 :         else
12 :             n -> parent -> right = n -> right;
13 :
14 :         n -> right -> parent = n -> parent;
15 :     }
16 :
17 :     releaseNodeData(n);
18 : }
「削除対象ノードが左の子のみを持つ場合」の対パターンです。ほぼ似たような内容の為、詳細は割愛します。

削除対象ノードが、両方の子を持つ場合

二分探索木 - 両方の子を持つノードの削除 これが最もやっかいな削除パターンです。 両方の子を持つノードを削除しても、ツリーのルールである 「とあるノードが存在する場合、左側にはそのノードよりも大きいノード、右側にはそのノードよりも小さいノードを配置する」 に違反しない為には、 右側の子孫(自分よりも小さいIDを持つノード郡)中、最も大きいIDを持つノード もしくは 左側の子孫(自分よりも大きいIDを持つノード郡)中、最も小さいIDを持つノード を、削除対象のノードへと上書きコピーします。 そして、コピー後に、コピー元のノードを削除します。 コードは以下の通りです。
 1 : /*** 削除対象のノードが、左の子、右の子両方を持つ場合 ***/
 2 : if (n -> left && n -> right) {
 3 :
 4 :     // 右の子の、左の子を辿っていく
 5 :     tmp = n -> right;
 6 :
 7 :     while(tmp -> left) {
 8 :         tmp = tmp -> left;
 9 :     }
10 :
11 :
12 :     // tmpの内容を、nにコピーする。-------------------
13 :
14 :     free(n -> data -> pszName);
15 :
16 :     if (! (n -> data -> pszName = (char *)malloc(strlen(tmp -> data -> pszName) + 1)) ) {
17 :         // エラー処理
18 :     }
19 :
20 :     strcpy(n -> data -> pszName, tmp -> data -> pszName);
21 :     n -> nId = tmp -> nId;
22 :
23 :     // ここまで --------------------------------------
24 :
25 :
26 :     // データをコピーしたtmpを、削除対象とする
27 :     n = tmp;
28 : }
4~9行目: 右側の子孫中、最も大きいIDを持つノードを探しています。 探し出したコピー元ノードは、tmpが指しています。 12~23行目: tmp(コピー元ノード)から、n(削除対象ノード)へ、データをコピーしています。 (ノード内のデータ構造体メンバによっては、コードを改修する必要があります。) 26~27行目: データをコピーした後、コピー元ノードを削除させる為、tmpをnに代入します。 その後は、上で述べたパターンに当てはめ、nを削除します。

二分探索木 - 削除関数まとめ

以上のことを1つの削除関数にまとめたものが、以下のコードです。
/*
 * idを指定し、該当するノードを削除する。
 *
 * [戻り] 成功時:0 / 該当するノードがない:1
 */
int deleteNode(int delId)
{
    node * n, * tmp;

    if ( ! (n = searchNode(delId)) ) { // 指定されたidを持つノードがない
        return 1;
    }


    if (n -> left && n -> right) {   /*** 削除対象のノードが、左の子、右の子両方を持つ場合 ***/

        // 右の子の、左の子を辿っていく
        tmp = n -> right;

        while(tmp -> left) {
            tmp = tmp -> left;
        }


        // tmpの内容を、nにコピーする。-------------------

        free(n -> data -> pszName);

        if (! (n -> data -> pszName = (char *)malloc(strlen(tmp -> data -> pszName) + 1)) ) {
            // エラー処理
        }

        strcpy(n -> data -> pszName, tmp -> data -> pszName);
        n -> nId = tmp -> nId;

        // ここまで --------------------------------------


        // データをコピーしたtmpを、削除対象とする
        n = tmp;
    }


    if (n -> left) {                 /*** 削除対象のノードが、左の子のみを持つ場合 ***/

        if (n == g_root) {
            g_root = n -> left;
            g_root -> parent = NULL;
        }
        else {
            if (n -> parent -> left == n)
                n -> parent -> left = n -> left;
            else
                n -> parent -> right = n -> left;

            n -> left -> parent = n -> parent;
        }
    }
    else if (n -> right) {       /*** 削除対象のノードが、右の子のみを持つ場合 ***/

        if (n == g_root) {
            g_root = n -> right;
            g_root -> parent = NULL;
        }
        else {
            if (n -> parent -> left == n)
                n -> parent -> left = n -> right;
            else
                n -> parent -> right = n -> right;
        }

        n -> right -> parent = n -> parent;

    }
    else {                     /*** 削除対象のノードが、子を持たない場合 ***/

        if (n == g_root) {
            g_root = NULL;
        }
        else {
            if (n -> parent -> left == n)
                n -> parent -> left = NULL;
            else
                n -> parent -> right = NULL;
        }

    }

    releaseNodeData(n);

    return 0;
}
         このエントリーをはてなブックマークに追加   


作業効率化・ライフハックのオススメ記事




コンピュータ・テクノロジーのオススメ記事





恋愛・人間関係のオススメ記事




※ 当サイトは、トップページからリンクで辿る事の出来るページに限り、リンクフリーです。
※ 当サイトの閲覧/利用によって生じた如何なる損害も、当サイト管理人は責任を負いません。
※ 当サイトの内容を転載される場合は、当サイトへのリンクをお願い致します。