2分木の各ノードにデータがあり、あるノードから見て左側の子孫ノードのデータすべてがこのノードのデータの値より小さく、一方、右側の子孫ノードのデータすべてが大きいという関係が成立するものを2分探索木という。

2分探索木による探索は、ルートから始め、探索キーの値がそのノードのデータより小さいか大きいかによって、左側または右側の子ノードをたどっていく。

<関数名>
  search 2分探索木におけるデータの探索
  insert 2分探索木におけるノードの挿入
  delete 2分探索木におけるノードの削除

<形式>
  2分探索木におけるデータの探索
  NODE *search(int key);

  2分探索木におけるノードの挿入
  NODE *insert(int key);

  2分探索木におけるノードの削除
  int delete(int key);

<引数>
  typedef struct _node {
    int key;       /* 比較のキーとなるフィールド */
    int info;      /* その他のフィールド */
    struct _node *left;  /* 左側の子を指す */
    struct _node *right; /* 右側の子を指す */
  } NODE;

  2分探索木におけるデータの探索関数において
  key 探索目標とするキーの値

  2分探索木におけるノードの挿入関数において
  key 追加したいキーの値

  2分探索木におけるノードの削除関数において
  key 削除したいキーの値

<関数値>
  2分探索木におけるデータの探索関数について
    探索が成功したときは見つかったノードへのポインタ。
    失敗のときは NULL。

  2分探索木におけるデータの挿入関数について
    挿入が成功したときは挿入したノードへのポインタ。
    挿入失敗のときや挿入しようとするキーが既にあったときは NULL。

  2分探索木におけるデータの削除関数について
    削除が成功したときは 0。
    削除しようとするキーが存在していないときは -1。

<注意事項>
  2分探索木のルートを示すのに、静的変数 root が使われている。

用例

<関数本体>
  binaryTree.c

<説明>
  完全につりあいのとれた2分探索木なら、n 個のものを調べるのに必要な比較回数は O(log n) 。しかし、左右のバランスの悪い木では探索時間がかかり、最悪場合の計算量は O(n) 。
  また、削除のプログラムがかなり複雑になってしまうことは、2分探索木の特徴である。考えるべきケースとして、削除しようとするノードが
  ・左側に子ノードをもたない場合
   自分自身を右側の部分木で置き換える。つまり、親ノードから右側の部分木にリンクを張り直す。
  ・左側に子ノードをもつ場合
   左側の部分木から最大のノードを探し出し、自分自身をそのノードで置き換える。リンクの張り直しなど、いくつかの操作が必要。
  探索や挿入の単純なルーチンよりも難しいが、注意深く考える価値があろう。
  なお、2分探索木の性質上、同じ探索キーをもつノードは一つしかないので、同じ探索キーに複数のデータをもつ場合はデータ構造中のinfoを工夫する必要がある。

Comments are closed.

Post Navigation