2分探索木において、木の左右をバランスさせるのが望ましい。木の片寄り方に一定の限度を設けて、挿入と探索の両方を最悪の場合でも O(log n)の計算量でできるようにする。 どのノードにおいても、その左部分木の高さと右部分木の高さの差を、+1、 0、-1のいずれかにする。

この制約を満たす2分探索木をAVL木(AVL-tree、考案者Adelson-Velskii とLandisという2人の旧ソ連数学者の頭文字をとったもの)と呼ぶ。

AVL木は2分探索木であるから、探索のアルゴリズムは2分探索木のと同じだが、データの挿入や削除については、初めは2分探索木のと同様に処理する。しかしその結果として左右の部分木の高さの差が2になるノードがあれば、木を再構成して制約条件を満たすように直す。

AVL木と2分探索木の得失を厳密に評価することは難しい。実験的評価から、 AVL木は十分実用的なアルゴリズムだと考えられる。探索に要する計算量が、平均的にも最悪の場合にも2分探索木より少ない。挿入や削除には余分の手間がかかるが、計算量のオーダは変わらない。ただし、プログラムがやや複雑になるのは欠点。

理論的な観点からは、探索と挿入を同時に O(log n)の計算量で処理できることを初めて示した点でAVL木の価値は大きい。

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

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

  AVL木におけるノードの挿入
    NODE *insert(int key);

  AVL木におけるノードの削除
    int delete(int key);

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

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

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

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

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

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

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

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

用例

<関数本体>
  avlTree.c

Comments are closed.

Post Navigation