(cache) データ構造：二分探索木［３］ ― データ要素の削除

二分探索木［３］ ― データ要素の削除

＜目次＞

＜概要＞ この資料では、二分探索木からデータ要素を削除するための関数（削除関数）の実装法を解説する。

1. おおまかな手順

削除関数は、大まかに言って、次のように処理する。

(1) 「二分探索木へのポインタ」と「削除対象のデータ要素（以下、valで表す）」を引数として受け取る。
(2) 二分探索木が空だったら、削除対象のデータ要素がそもそも存在しないので、何もせずに終了する。以下、二分探索木が空でなかったとする。
(3) そこでまず、valを保持したノードが存在するか否かを検査する。
- valを保持したノードが存在するときには、 valを保持したノード（へのポインタ）と、その親ノード（へのポインタ）を求める。以下、valを保持したノードを v で表し、その親ノードを u で表す。
- ただし、存在しないときには何もせずに終了する。
(4) valを保持したノードvが存在したときには、次の四つの場合に分けてノードvを削除する。
- vが子供を持たない場合。
- vが右側の子供を持たない場合。
- vが左側の子供を持たない場合。
- vが二人の子供を持つ場合。

以下では、

関数頭部・ローカル変数（上記の(1)）・二分探索木が空か否かの判定（上記の(2)）、
存在検査処理（上記の(3)）、
削除処理（上記の(4)）

といった順に、処理手順とプログラムを解説する。なお、valを保持したノードを「削除対象ノード」と呼ぶことにする。

2. 関数頭部とローカル変数、二分探索木が空か否か

削除関数の頭部、削除関数の中で使用するローカル変数の宣言、ならびに、二分探索木が空か否かを検査する処理は次のようになる。

void delete( struct node * * rt, int val ){
  struct node * del_node, * parent;
  struct node * pred_node, * pred_parent;

  /*-- 二分探索木が空だったら何もせずに終了する      --*/
  if( *rt == NULL ){ return; }

      ...（存在検査処理へと続く）...

【補足１】（ポインタ変数のポインタ渡しを使用する）
二分探索木の根がvalを保持していた場合、その根を削除することになる。そのため、二分探索木の根へのポインタが削除関数内部で変化する可能性がある。従って、根を指すポインタ変数（root）に関してポインタ渡しを使用する。

【補足２】（ローカル変数 del_node と parent ）
ローカル変数del_nodeには削除対象ノードへのポインタを格納し、ローカル変数parentにはその親ノードへのポインタを格納する。

【補足３】（ローカル変数 pred_node と pred_parent ）
削除対象ノードが二人の子供を持っている場合、二分探索木に登録されているデータ要素の中のval未満の最大値（以下では、これを「predecessor」と呼んでいる）を保持したノードへのポインタと、その親ノードへのポインタを求めなければならない。 pred_nodeとpred_parentは、この処理を行うときに使用する。

3. 存在検査（検索処理）

存在検査処理は、追加関数における追加場所を求める処理や検索処理と同じである。従って、この処理の概要は次のようになる。

valを保持したノードが存在するか否かを検査する。
valを保持したノードが存在するとき、（上記の検査処理の中で） valを保持したノードへのポインタ（del_node）と、そのノードの親ノードへのポインタ（parent）を求める。
ただし、valを保持したノードが存在しないときには何もせずに終了する。

詳細については、次のプログラムを読んで学習して欲しい。

  /*-- valを保持するノードが存在するか否かを検査する --*/
  del_node = *rt;  parent = NULL;
  while( del_node != NULL ){
    if( val == del_node->value ){ break; }
    if( val < del_node->value ){
      parent = del_node;
      del_node = del_node->left;
    } else {
      parent = del_node;
      del_node = del_node->right;
    }      
  }

  /*-- valを保持したノードが存在しないときには何もせずに終了する --*/
  if( del_node == NULL ){ return; }

      ...（削除処理へと続く）...

4. 削除処理

valを保持したノード（削除対象ノード；del_nodeが指すノード）の削除処理は、先にも述べたように、次の四つの場合に分けて処理される。

削除対象ノードが子供を持っていない場合。
削除対象ノードが左側の子供だけを持っている場合。
削除対象ノードが右側の子供だけを持っている場合。
削除対象ノードが二人の子供を持っている場合。

以下では、それぞれの場合ごとに処理手順とプログラムを解説する。

4.1. 削除対象ノードが子供を持っていない場合

この場合には、次のように処理する。

(1) 削除対象ノードが根だったとき、根へのポインタをNULLに設定する。
(2) 削除対象ノードが根でなかったとき、次のように処理する。
- (a) 親ノードから見て、削除対象ノードが左側の子供なのか右側の子供なのかを判定する。
- (b) 左側の子供だったら、「親ノードの左側の子供へのポインタ」をNULLに設定する。
- (c) 右側の子供だったら、「親ノードの右側の子供へのポインタ」をNULLに設定する。
(3) 最後に、削除対象ノードのメモリ領域を解放して削除関数を終了する。

参考までに、この処理のイメージ図を以下に示す。

この場合のプログラム（の断片）は、次のようになる。

  /*-- 削除対象ノードが子供を持っていない場合       --*/
  if( del_node->left == NULL && del_node->right == NULL ){
    if( del_node == *rt ){           /* (1) 削除対象ノードが根のとき     */
      *rt = NULL;
    } else {                         /* (2) 削除対象ノードが根でないとき */
      if( val < parent->value ){     /* (a) */
        parent->left = NULL;         /* (b) */
      } else {
        parent->right = NULL;        /* (c) */
      }
    }
    free(del_node);                  /* (3) メモリ領域を解放して、 */
    return;                          /*     終了する */
  }

      ...（次の場合へと続く）...

4.2. 削除対象ノードが左側の子供だけを持っている場合

この場合には、次のように処理する。

(1) 削除対象ノードが根だったとき、削除対象ノード（根）の左側の子供を根にする。
(2) 削除対象ノードが根でなかったとき、次のように処理する。
- (a) 親ノードから見て、削除対象ノードが左側の子供なのか右側の子供なのかを判定する。
- (b) 左側の子供だったら、「親ノードの左側の子供へのポインタ」を「削除対象ノードの左側の子供へのポインタ」に設定する。
- (c) 右側の子供だったら、「親ノードの右側の子供へのポインタ」を「削除対象ノードの左側の子供へのポインタ」に設定する。
(3) 最後に、削除対象ノードのメモリ領域を解放して削除関数を終了する。

参考までに、この処理のイメージ図を以下に示す。

この場合のプログラム（の断片）は、次のようになる。

  /*-- 削除対象ノードが左側の子供だけを持っている場合 --*/
  if( del_node->left != NULL && del_node->right == NULL ){
    if( del_node == *rt ){                /* (1) 削除対象ノードが根のとき     */
      *rt = del_node->left;
    } else {                              /* (2) 削除対象ノードが根でないとき */
      if( val < parent->value ){          /* (a) */
        parent->left = del_node->left;    /* (b) */
      } else {
        parent->right = del_node->left;   /* (c) */
      }
    }
    free(del_node);                       /* (3) メモリ領域を解放して、 */
    return;                               /*     終了する */
  }

      ...（次の場合へと続く）...

4.3. 削除対象ノードが右側の子供だけを持っている場合

この場合には、次のように処理する（注：前節の場合と本質的に同じである）。

(1) 削除対象ノードが根だったとき、削除対象ノード（根）の右側の子供を根にする。
(2) 削除対象ノードが根でなかったとき、次のように処理する。
- (a) その親ノードから見て、削除対象ノードが左側の子供なのか右側の子供なのかを判定する。
- (b) 左側の子供だったら、「親ノードの左側の子供へのポインタ」を「削除対象ノードの右側の子供へのポインタ」に設定する。
- (c) 右側の子供だったら、「親ノードの右側の子供へのポインタ」を「削除対象ノードの右側の子供へのポインタ」に設定する。
(3) 最後に、削除対象ノードのメモリ領域を解放して削除関数を終了する。

参考までに、この処理のイメージ図を以下に示す。

この場合のプログラム（の断片）は次のようになる。

  /*-- 削除対象ノードが右側の子供だけを持っている場合 --*/
  if( del_node->left == NULL && del_node->right != NULL ){
    if( del_node == *rt ){                 /* (1) 削除対象ノードが根のとき     */
      *rt = del_node->right;
    } else {                               /* (2) 削除対象ノードが根でないとき */
      if( val < parent->value ){           /* (a) */
        parent->left = del_node->right;    /* (b) */
      } else {
        parent->right = del_node->right;   /* (c) */
      }
    }
    free(del_node);                        /* (3) メモリ領域を解放して */
    return;                                /*     終了する */
  }

      ...（次の場合へと続く）...

4.4. 削除対象ノードが二人の子供を持っている場合

この場合の処理は、これまでに比べてやっかいである。この場合には、次に示すような四段階の処理を行う。

  /*-- 削除対象ノードが二人の子供を持っている場合 --*/
  if( del_node->left != NULL && del_node->right != NULL ){
    /* [1] val（削除対象のデータ要素）のpredecessorノードを求める */

      ...（詳細は後述）...

    /* [2] predecessorノードを二分探索木から取り外す */

      ...（詳細は後述）...

    /* [3] 削除対象ノードをpredecessorノードに置き換える  */

      ...（詳細は後述）...

    /* 削除対象ノードのメモリ領域を解放して終了する */
    free(del_node);
    return;
  }

以下では、上記の[1]、[2]、[3]の詳細を示す。

4.4.1. val（削除対象のデータ要素）の predecessorノードを求める

まず初めに、

二分探索木に登録されているデータ要素の中で、val未満の最大値、言い換えると、二分探索木に登録されているデータ要素を仮に昇順（小さい順）に並べたときに「valの直前に来るデータ要素」

を保持したノードへのポインタ（以下、pred_nodeと表す）と、そのノードの親ノードへのポインタ（以下、pred_parentと表す）を求める。

【定義】これ以後、「valの直前に来るデータ要素」のことを、valの「predecessor」と呼ぶことにする。また、valのpredecessorを保持したノードを「predecessorノード」と呼ぶことにする。（参考：「predecessor」は「前者」などと訳されることが多い）。〈定義終わり〉

valのpredecessorは、削除対象ノードの左部分木内の最大値である。従って、削除対象ノードの左部分木内の最大値を保持したノードへのポインタと、その親ノードへのポインタを求めればよい。その手順は次の通り。

(a) まず、削除対象ノードの左側の子供（左部分木の根）へ移動する。
(b) 次に、左部分木の根からスタートして、右側の子供へのポインタを（芋づる式に）辿りながら、左部分木の中を右へ右へと降りていく。
(c) やがて、右側の子供へのポインタがNULLになって、もはや右へ降りることができなくなるときがやってくる。そのときのノードがvalのpredecessorノード（左部分木の最大値を保持したノード）である。このとき同時に、predecessorノードの親ノードへのポインタを求めなければならないのだが、それは、追加関数の追加場所を求める処理と同じ方法によって求めることができる。

参考までに、この処理のイメージ図を次に示す。

この処理のプログラム（の断片）を次に示す。

    /* valのpredecessorノードを求める */
    pred_node = del_node->left;                 /* (a) */
    pred_parent = del_node; 
    while( pred_node->right != NULL ){          /* (b),(c) */
      pred_parent = pred_node;
      pred_node = pred_node->right;
    }

4.4.2. predecessorノードを二分探索木から取り外す

次に、predecessorノードを二分探索木から取り外す。ただし、次の処理において、削除対象ノードをpredecessorノードに置き換えるので、メモリ領域は解放しない。

この処理は「左側の子供だけ持っている場合の削除処理」と基本的に同じである。すなわち、 predecessorノードの親ノードの自己参照メンバ（predecessorノードを指しているもの）を、predecessorノードの左側の子供へのポインタに変更すればよい。

ただし、次の二つの場合を分けて処理する必要がある。

predecessorノードが削除対象ノードの子供だった場合（参考：削除対象ノードの左側の子供（左部分木の根）が右側の子供を持っていないときに、この場合が発生する）。
predecessorノードが削除対象ノードの子供でなかった場合。

predecessorノードが削除対象ノードの子供だった場合、predecessorノードはその親ノード（削除対象ノード）の「左側の子供」になる（下図参照）。一方、そうでなかった場合、predecessorノードはその親ノードの「右側の子供」になる（［１］のところで示したイメージ図参照）。親ノードから見たときのpredecessorノードの位置が異なるので場合分けしなければならない。

以上をまとめると、次のようなプログラム（の断片）が得られる（説明はくどいが、プログラムは単純である）。

    /* predecessorノードを二分探索木から取り外す */
    if( pred_parent == del_node ){
      pred_parent->left = pred_node->left;
    } else {
      pred_parent->right = pred_node->left;
    }

参考までに、precdecessorノードを取り外すときのイメージ図を次に示す。

4.4.3. 削除対象ノードをpredecessorノードに置き換える

次に、削除対象ノードをpredecessorノードに置き換える。その処理手順は次の通り。

(a) 削除対象ノードの自己参照メンバの値（二人の子供へのポインタ）をpredecessorノードの自己参照メンバに代入する。
(b) 「削除対象ノードの親ノードから削除対象ノードへ向かうリンク（ポインタ）」を「predecessorノードへ向かうリンク（ポインタ）」に張り替える。ただし、削除対象ノードが根である場合（その親ノードが存在しない場合）と、そうでない場合（親ノードが存在する場合）に分けて処理しなければならない。

この処理のプログラム（の断片）は次のようになる。

    /* 削除対象ノードをpredecessorノードに置き換える  */
    pred_node->left  = del_node->left;
    pred_node->right = del_node->right;
    if( *rt == del_node ){
      *rt = pred_node;
    } else {
      if( val < parent->value ){
        parent->left = pred_node;
      } else {
        parent->right = pred_node;
      }
    }

参考までに、この処理のイメージ図を次に示す。

4.4.4. 二人の子供を持っている場合のプログラム（まとめ）

以上のプログラム（の断片）をまとめたものを次に示す。

  if( del_node->left != NULL && del_node->right != NULL ){
    /* val（削除対象のデータ要素）のpredecessorノードを求める */
    pred_node = del_node->left;
    pred_parent = del_node; 
    while( pred_node->right != NULL ){
      pred_parent = pred_node;
      pred_node = pred_node->right;
    }

    /* predecessorノードを二分探索木から取り外す */
    if( pred_parent == del_node ){
      pred_parent->left = pred_node->left;
    } else {
      pred_parent->right = pred_node->left;
    }

    /* 削除対象ノードをpredecessorノードに置き換える  */
    pred_node->left  = del_node->left;
    pred_node->right = del_node->right;
    if( *rt == del_node ){
      *rt = pred_node;
    } else {
      if( val < parent->value ){
        parent->left = pred_node;
      } else {
        parent->right = pred_node;
      }
    }

    /* 削除対象ノードのメモリ領域を解放して終了する */
    free(del_node);
    return;
  }

5. 削除関数のプログラム（まとめ）

削除関数全体のプログラムを示しておこう。

/*-★ 削除関数（データ要素を削除する） --*/
void delete( struct node * * rt, int val ){
  struct node * del_node, * parent;
  struct node * pred_node, * pred_parent;

  /*-- 二分探索木が空だったら何もせずに終了する      --*/
  if( *rt == NULL ){ return; }

  /*-- valを保持するノードが存在するか否かを検査する --*/
  del_node = *rt;  parent = NULL;
  while( del_node != NULL ){
    if( val == del_node->value ){ break; }
    if( val < del_node->value ){
      parent = del_node;
      del_node = del_node->left;
    } else {
      parent = del_node;
      del_node = del_node->right;
    }      
  }      
  /*-- valを保持したノードが存在しないときには何もせずに終了する --*/
  if( del_node == NULL ){ return; }

  /*-- 削除対象ノードが子供を持っていない場合       --*/
  if( del_node->left == NULL && del_node->right == NULL ){
    if( del_node == *rt ){         /* 削除対象ノードが根のとき     */
      *rt = NULL;
    } else {                       /* 削除対象ノードが根でないとき */
      if( val < parent->value ){
        parent->left = NULL;
      } else {
        parent->right = NULL;
      }
    }
    free(del_node);               /* 削除対象ノードのメモリ領域を解放 */
    return;                       /* 終了 */
  }

  /*-- 削除対象ノードが左側の子供だけを持っている場合 --*/
  if( del_node->left != NULL && del_node->right == NULL ){
    if( del_node == *rt ){         /* 削除対象ノードが根のとき     */
      *rt = del_node->left;
    } else {                       /* 削除対象ノードが根でないとき */
      if( val < parent->value ){
        parent->left = del_node->left;
      } else {
        parent->right = del_node->left;
      }
    }
    free(del_node);               /* 削除対象ノードのメモリ領域を解放 */
    return;                       /* 終了 */
  }

  /*-- 削除対象ノードが右側の子供だけを持っている場合 --*/
  if( del_node->left == NULL && del_node->right != NULL ){
    if( del_node == *rt ){         /* 削除対象ノードが根のとき     */
      *rt = del_node->right;
    } else {                       /* 削除対象ノードが根でないとき */
      if( val < parent->value ){
        parent->left = del_node->right;
      } else {
        parent->right = del_node->right;
      }
    }
    free(del_node);               /* 削除対象ノードのメモリ領域を解放 */
    return;                       /* 終了 */
  }
    
  /*-- 削除対象ノードが二人の子供を持っている場合 --*/
  if( del_node->left != NULL && del_node->right != NULL ){
    /* val（削除対象のデータ要素）のpredecessorノードを求める */
    pred_node = del_node->left;
    pred_parent = del_node; 
    while( pred_node->right != NULL ){
      pred_parent = pred_node;
      pred_node = pred_node->right;
    }

    /* predecessorノードを二分探索木から取り外す */
    if( pred_parent == del_node ){
      pred_parent->left = pred_node->left;
    } else {
      pred_parent->right = pred_node->left;
    }

    /* 削除対象ノードをpredecessorノードに置き換える  */
    pred_node->left  = del_node->left;
    pred_node->right = del_node->right;
    if( *rt == del_node ){
      *rt = pred_node;
    } else {
      if( val < parent->value ){
        parent->left = pred_node;
      } else {
        parent->right = pred_node;
      }
    }

    /* 削除対象ノードのメモリ領域を解放して終了する */
    free(del_node);
    return;
  }

}

【参考】上記のプログラムでは、削除対象ノードが子供を持っているか否か（さらに、何人持っているか）といった場合分けを、次のようなif文によって判定している。

  /*-- 削除対象ノードが子供を持っていない場合       --*/
  if( del_node->left == NULL && del_node->right == NULL ){
         ......
  }

  /*-- 削除対象ノードが左側の子供だけを持っている場合 --*/
  if( del_node->left != NULL && del_node->right == NULL ){
         ......
  }

  /*-- 削除対象ノードが右側の子供だけを持っている場合 --*/
  if( del_node->left == NULL && del_node->right != NULL ){
         ......
  }
    
  /*-- 削除対象ノードが二人の子供を持っている場合 --*/
  if( del_node->left != NULL && del_node->right != NULL ){
         ......
  }

各if文の条件が満たされて、その内部（then節）に処理が移行した場合、上のプログラムでは、その内部でreturn文を実行している。従って、２番目と３番目のif文の条件式を次のように書き換えたとしても正しく処理される。

      .....

  /*-- 削除対象ノードが左側の子供だけを持っている場合 --*/
  if( del_node->right == NULL ){
         ......
  }

  /*-- 削除対象ノードが右側の子供だけを持っている場合 --*/
  if( del_node->left == NULL ){
         ......
  }
     ......

さらに、３番目までのif文の条件が満たされなかったときには、削除対象ノードが二人の子供を持っていることは明らかである。従って、４番目のif文については、その内部（then節）だけを残して、if節（ifと条件式）ならびにthen節全体を囲む中カッコを削除してしまっても構わない。〈参考終わり〉

6. 試験用プログラム

最後に、簡単な試験用プログラムを示しておこう。以下のプログラムは、これまで作成したものに削除関数を追加したものである。また、内容表示関数を少しだけ見やすくなるように変更している。この変更点に関しては特に説明しない。プログラムを見て何をしているか分析して欲しい。

/**********************************************************************
 * ヘッダファイル
 **********************************************************************/
#include <stddef.h>                      /*-- NULL , size_t --*/
#include <stdio.h>                       /*-- printf関数    --*/
#include <stdlib.h>                      /*-- malloc関数    --*/

/**********************************************************************
 * 二分探索木のノードを表す自己参照構造体
 **********************************************************************/
struct node {
  int value;                             /*-- データ要素     --*/
  struct node * left;                    /*-- 左側の子供へのポインタ --*/
  struct node * right;                   /*-- 右側の子供へのポインタ --*/
};

/**********************************************************************
 * 基本操作関数（プロトタイプ宣言）
 **********************************************************************/
void init( struct node * * rt );                        /*-- 初期設定 --*/
void add( struct node * * rt, int val );                /*-- 追加 --*/ 
struct node* search( struct node * root, int val );     /*-- 検索 --*/
void delete( struct node * * rt, int val );             /*-- 削除 --*/

/**********************************************************************
 * その他の関数（プロトタイプ宣言）
 **********************************************************************/
void display( struct node * p, int level);       /* 内容表示 */
void freeAll( struct node * * rt );              /* メモリ解放(main) */ 
void freeTree( struct node * p );                /* メモリ解放(sub)  */

/**********************************************************************
 * main関数
 **********************************************************************/
int main(void){
  int A[] = { 29, 13, 5, 19, 15, 47, 35, 33, 40, 51, 65, -1 }; 
  int i;

  struct node * root;          /* 二分探索木（の根）を指すポインタ変数 */

  /*-★ 二分探索木の初期設定 --*/
  init( &root );

  /*-★ 各A[i]を二分探索木に追加する --*/
  i = 0;
  while( A[i] > 0 ){ 
    add( &root, A[i] ); 
    i++;
  }

  /*-★ 二分探索木の内容を表示する --*/
  printf("[1] 登録直後の二分探索木\n");
  printf("root=%p\n", root);               /* 根へのポインタを表示 */
  display(root,0);                         /* 二分探索木の内容表示 */
  printf("\n");

  /*-★ 40を削除したあと表示（子供なしの場合） --*/ 
  delete(&root,40);
  printf("[2] 40を削除（子供なしの場合）\n");
  printf("root=%p\n", root);               /* 根へのポインタを表示 */
  display(root,0);                         /* 二分探索木の内容表示 */
  printf("\n");

  /*-★ 35を削除したあと表示（左側の子供だけの場合） --*/ 
  delete(&root,35);
  printf("[3] 35を削除（左側の子供だけの場合）\n");
  printf("root=%p\n", root);               /* 根へのポインタを表示 */
  display(root,0);                         /* 二分探索木の内容表示 */
  printf("\n");

  /*-★ 51を削除したあと表示（右側の子供だけの場合） --*/ 
  delete(&root,51);
  printf("[4] 51を削除（右側の子供だけの場合）\n");
  printf("root=%p\n", root);               /* 根へのポインタを表示 */
  display(root,0);                         /* 二分探索木の内容表示 */
  printf("\n");

  /*-★ 47を削除したあと表示（子供が二人いる場合） --*/ 
  delete(&root,47);
  printf("[5] 47を削除（子供が二人いる場合）\n");
  printf("root=%p\n", root);               /* 根へのポインタを表示 */
  display(root,0);                         /* 二分探索木の内容表示 */
  printf("\n");

  /*-★ 29を削除したあと表示（根を削除） --*/ 
  delete(&root,29);
  printf("[6] 29を削除（根を削除）\n");
  printf("root=%p\n", root);               /* 根へのポインタを表示 */
  display(root,0);                         /* 二分探索木の内容表示 */
  printf("\n");


  /*-★ メモリ領域を解放する --*/
  freeAll(&root);

  return 0;
}

/**********************************************************************
 * 基本操作関数（関数本体の定義）
 **********************************************************************/
/*-★ 初期設定関数 --*/
/*-★ 追加関数（データ要素を追加する） --*/
/*-★ 検索関数（データ要素を検索する） --*/

  ...（上記の各関数については、以前のものと同じなので省略する）...


/*-★ 削除関数（データ要素を削除する） --*/
void delete( struct node * * rt, int val ){
  struct node * del_node, * parent;
  struct node * pred_node, * pred_parent;

     ...（前節で示したプログラムを参照）...

}

/*-★ 内容表示関数（レベルに応じて字下げする） --*/
void display( struct node * p, int level){
  int i;
  if( p != NULL ){
    if( level == 0 ){
      printf("%p:[%d;%p,%p]\n", p, p->value, p->left, p->right);
    } else {
      for(i=0;i<level;i++){ printf("   "); }
      printf("┗ %p:[%d;%p,%p]\n", p, p->value, p->left, p->right);
    }
    display(p->left,level+1);            /* 左部分木をトラバースする */
    display(p->right,level+1);           /* 右部分木をトラバースする */
  }
}


/*-★ メモリ解放関数 --*/

   ...（以前のものと同じなので省略する）...

（実行結果）

[1] 登録直後の二分探索木
root=0x804a050
0x804a050:[29;0x804a060,0x804a0a0]
   ┗ 0x804a060:[13;0x804a070,0x804a080]
      ┗ 0x804a070:[5;(nil),(nil)]
      ┗ 0x804a080:[19;0x804a090,(nil)]
         ┗ 0x804a090:[15;(nil),(nil)]
   ┗ 0x804a0a0:[47;0x804a0b0,0x804a0e0]
      ┗ 0x804a0b0:[35;0x804a0c0,0x804a0d0]
         ┗ 0x804a0c0:[33;(nil),(nil)]
         ┗ 0x804a0d0:[40;(nil),(nil)]
      ┗ 0x804a0e0:[51;(nil),0x804a0f0]
         ┗ 0x804a0f0:[65;(nil),(nil)]

[2] 40を削除（子供なしの場合）
root=0x804a050
0x804a050:[29;0x804a060,0x804a0a0]
   ┗ 0x804a060:[13;0x804a070,0x804a080]
      ┗ 0x804a070:[5;(nil),(nil)]
      ┗ 0x804a080:[19;0x804a090,(nil)]
         ┗ 0x804a090:[15;(nil),(nil)]
   ┗ 0x804a0a0:[47;0x804a0b0,0x804a0e0]
      ┗ 0x804a0b0:[35;0x804a0c0,(nil)]
         ┗ 0x804a0c0:[33;(nil),(nil)]
      ┗ 0x804a0e0:[51;(nil),0x804a0f0]
         ┗ 0x804a0f0:[65;(nil),(nil)]

[3] 35を削除（左側の子供だけの場合）
root=0x804a050
0x804a050:[29;0x804a060,0x804a0a0]
   ┗ 0x804a060:[13;0x804a070,0x804a080]
      ┗ 0x804a070:[5;(nil),(nil)]
      ┗ 0x804a080:[19;0x804a090,(nil)]
         ┗ 0x804a090:[15;(nil),(nil)]
   ┗ 0x804a0a0:[47;0x804a0c0,0x804a0e0]
      ┗ 0x804a0c0:[33;(nil),(nil)]
      ┗ 0x804a0e0:[51;(nil),0x804a0f0]
         ┗ 0x804a0f0:[65;(nil),(nil)]

[4] 51を削除（右側の子供だけの場合）
root=0x804a050
0x804a050:[29;0x804a060,0x804a0a0]
   ┗ 0x804a060:[13;0x804a070,0x804a080]
      ┗ 0x804a070:[5;(nil),(nil)]
      ┗ 0x804a080:[19;0x804a090,(nil)]
         ┗ 0x804a090:[15;(nil),(nil)]
   ┗ 0x804a0a0:[47;0x804a0c0,0x804a0f0]
      ┗ 0x804a0c0:[33;(nil),(nil)]
      ┗ 0x804a0f0:[65;(nil),(nil)]

[5] 47を削除（子供が二人いる場合）
root=0x804a050
0x804a050:[29;0x804a060,0x804a0c0]
   ┗ 0x804a060:[13;0x804a070,0x804a080]
      ┗ 0x804a070:[5;(nil),(nil)]
      ┗ 0x804a080:[19;0x804a090,(nil)]
         ┗ 0x804a090:[15;(nil),(nil)]
   ┗ 0x804a0c0:[33;(nil),0x804a0f0]
      ┗ 0x804a0f0:[65;(nil),(nil)]

[6] 29を削除（根を削除）
root=0x804a080
0x804a080:[19;0x804a060,0x804a0c0]
   ┗ 0x804a060:[13;0x804a070,0x804a090]
      ┗ 0x804a070:[5;(nil),(nil)]
      ┗ 0x804a090:[15;(nil),(nil)]
   ┗ 0x804a0c0:[33;(nil),0x804a0f0]
      ┗ 0x804a0f0:[65;(nil),(nil)]

7. 演習問題

【問題１】削除対象ノードのメモリ領域を解放する代わりに、削除対象ノードへのポインタを返すように削除関数を変更せよ。なお、ポインタを返す前に、削除対象ノードの自己参照メンバにNULLを設定すること（二分探索木に対する不適切なアクセスを回避するため）。関数名を withdraw とすること。

【問題２】二分探索木の中の最小値を削除する関数を作成せよ。関数名を delete_min とすること。（なお、最大値を削除する関数も自習用課題として作成してみるように。）

【解説】（問題３のための準備）
削除対象ノードが子供を二人持っている場合、「削除対象ノードとpredecessorノードを置き換える」といった処理を行ったが、この置き換え処理の代わりに次のように処理しても削除対象のデータ要素を削除したことになる。

predecessorノードのデータ要素「pred」を削除対象ノードのvalueメンバに代入する。
さらに、削除対象ノードのメモリ領域を解放せずに、代わりに、predecessorノードのメモリ領域を解放する。

「置き換える」といった処理方法がもっとも一般的である。しかしながら、上のように処理することによって、「置き換え」処理におけるポインタの張り替え操作が不要になるので、プログラムがより単純になる。
どちらが優れているかは、どのようなデータ要素を扱っているかに依存する。一般にデータ要素のサイズ（メモリ領域のサイズ）が小さければ上のように処理したほうがよい。しかし、データ要素のサイズが大きいときには、代入操作に多くの時間を要する可能性があるので「置き換え」処理を行ったほうがよい。〈解説終わり〉

【問題３】「置き換え」処理の代わりに、上の解説で述べた処理を行うように削除関数を変更せよ。変更後の関数名を erase としよう。

【定義】（問題４のための準備）
valを二分探索木に登録されている任意のデータ要素とする。二分探索木に登録されているすべてのデータ要素を昇順に並べたとき、「valの直後に来るデータ要素」のことを、valの「successor」と呼ぶ。また、valのsuccessorを保持したノードを、valの「successorノード」と呼ぶことにする。（参考：「successor」は「後者」などと訳されることが多い。）

【問題４】この資料で解説した削除関数では、削除対象のデータ要素valのpredecesoorノードを求めたが、その代わりに、valのsuccessorノードを求めて、削除対象ノードをsuccessorノードに置き換えるといった処理を行ってもよい。そこで、削除関数をそのように変更せよ。変更後の関数名を remove としよう。

【問題５】次のように処理する関数を作成せよ。

根のデータ要素に対するpredecessorノードを求めて、根をpredecessorノードに置き換える。
さらに、置き換えたあとの二分探索木に、もともとの根のデータ要素を改めて追加する（新たな根の右部分木に追加されるはず）。

この処理によって、見かけ上、根の左部分木から右部分木にノードを一つ移動することになる。そこで、関数名を left_to_right としよう。

【問題６】 right_to_left と呼び得る関数を作成せよ。何をすべきかは問題５の内容から想像せよ。

【定義】（問題７と問題８のための準備）
T を任意の二分探索木とし、vをTの任意のノードとする。このとき、vの左部分木のノード数をL(T,v)で表し、vの右部分木のノード数をR(T,v)で表すことにする。〈定義終わり〉

【問題７】任意に与えられた二分探索木 T を、それに登録されているデータ要素の集合を変えることなく、根の左部分木と右部分木のノード数ががほぼ等しい二分探索木 S に作り変えるような関数を作成せよ。
より正確に言うと、任意に与えられた二分探索木 T を、|L(S,r)-R(S,r)|≦1を満たすような二分探索木 S に作り変えるような関数を作成せよ。ここで、rはSの根を表す。
関数名を balancer としよう。〈参考〉問題５と問題６で作成した関数を活用するとよい。当然、ノード数を求める関数も必要だろう。

【問題８】任意に与えられた二分探索木 T を、それに登録されているデータ要素の集合を変えることなく、次の条件を満たすような二分探索木 S に作り変える関数を作成せよ。

〈条件〉Sの任意のノードvに対して |L(S,v-R(S,v)|≦1 が成り立つ。

関数名をfull_balancerとしよう。〈参考〉問題７で作成したbalancerとトラバーサルを利用するとよい。

日本大学文理学部情報システム解析学科 S.Toda / 2005年12月12日