プログラミング技法とデータ構造

探索木

2分探索木

木構造の一種に2分木があったが，これを元に探索問題に使用したものが二分探索木である．任意のノードAにおいて，左の部分木に含まれるノードの値は，ノードAよりも小さな値だけで構成され，右の部分木に含まれるノードは大きな値だけであるように作成された木である．

この二分探索木は，まったく同じn個のデータから作成しても，具体的な木構造は一意に定まらず，複数形が存在しうる．例えば両極端な例ととして，n個のデータのうち最大値を根にして，大きさ順に左方向の枝だけが伸びている木構造もあれば，逆に最小値を根にして右方向の枝だけが伸びている木も考えられる．同じデータからどのような木構造を構築するかは，一般にデータの挿入順に関係する．

二分探索木の探索

一番基本となる部分のプログラムはある値を探索する部分である．その他の操作，例えばデータの挿入削除などでも，まず該当部分を探索する必要がある．

typedef struct node {
  int d;
  struct node *right, *left;
} NODE;

NODE *find(NODE *p, int key)
{
  if(p==NULL)
      return NULL;
  else if(p->data==key)
      return p;
  else if(p->data > key)
      return find(p->left, key);
  else if(p->data < key)
      return find(p->right, key);
}

ノードの挿入は，探索と類似するものの，ノードの先がない末端を探すことで行われる．

NODE *insert(NODE *p, int key)
{
  if(p==NULL){
     p=malloc(sizeof(NODE));
     p->data=key;
     p->right = p->left=NULL;
     return p;
  }else if(p->data==key){
     printf("すでに登録されています");
     exit(EXIT_FAILURE);
  }else if(p->data > key)
     p->left=insert(p->left, key);
  else if(p->data < key)
     p->right=insert(p->right, key);
  return p;
}

逆に，削除の場合には少し面倒な手続きが必要となる．うかつにノードを削除すると，二分探索木の性質を維持できない場合があるためである．これは削除対象のノードの子供の数によって対処が異なる．子供が無い場合には単純にそのノードを削除すればよい．また，子供が一つの場合には，目的のノードを削除した後，その位置へ子供を格上げすればよい．問題なのは子供が二つある場合である．削除対象ノードの左部分木から最大値のノードを探索する．(右部分木から最小値でもよい)削除対象ノードと最大値ノードを入れ替える．最大値と入れ替えたのでこの段階で少なくとも子供が1つ以下になっているはずの削除対象ノードを削除する．