検索アルゴリズム

(2)2分検索/木検索

検索アルゴリズムの2回目は2分検索と木検索です。

1)2分検索

前回紹介した線形検索は、n個のデータ列に対して平均n/2回の比較操作が必要となるため、処理速度はnに比例していると言えます。これに対して、2分検索(Binary Search)ではn個のデータ列に対して最悪でもlog2n回の比較回数で済むので、線形検索に対してかなりの性能向上が期待できます。
ただし、2分検索を行うためにはデータ列がソートされている必要があり、その分線形検索に比べて前処理のための時間が必要となります。また、1回の比較処理にかかる時間も線形検索より長くなるため、データ数が少ない場合は2分検索の方がかえって遅くなることも考えられます。

2分検索では、まずデータ列の中央にある要素(以下mとします)と検索対象データ(以下xとします)を比較し、一致しなければxとmの大小関係よりxが中央より手前にあるか、それとも後ろにあるかを判断します。仮にデータ列が昇順でソートされているとした場合、

にxが存在していることになるので、データ列を中央で分割して、xが存在する可能性のある区間に対して新たな中央の要素mとxを比較します。この操作を、mとxが一致するか、これ以上データ列が分割ができなくなるまで繰り返します。分割できなくなった場合は目的の要素が見つからなかったことを意味します。

正数1から10までのデータ列から、2分検索で7の値を検索した場合の流れを以下に示します。

1)(ほぼ)中央位置の要素５と比較する。
1 2 3 4 5 6 7 8 9 10
2)5 < 7なので、検索対象はデータ列後半にある。前半部分を切り捨て、中央位置の要素８と比較する。
6 7 8 9 10
3)8 > 7なので、検索対象はデータ列前半にある。後半部分を切り捨て、(ほぼ)中央位置の要素６と比較する。
6 7
4)6 < 7なので、検索対象はデータ列後半にある。前半部分を切り捨て、中央位置の要素７と比較する。
7
5)一致したデータが見つかり、処理終了。

上記の例では、データ列の要素が1つになるまで処理が終わらなかったという、最悪の場合を想定していますが、要素数10個に対して4回の比較を行っています。これが要素数100個になったとき、最悪でも7回の比較で検索処理が終了します。
線形検索では1つの要素に対する比較処理は一致したどうかの1回だけで済みますが、2分検索ではその他にも大小の比較を行う分比較の処理時間は大きくなります。ソートするための前処理にかかる時間も考慮すると、要素数が数十個程度であればかえって線形検索を使用した方が速いと考えられます。

以下に、2分検索のサンプルを示します。

int *BinarySearch( DataStart, DataEnd, Data )
int *DataStart, *DataEnd;
int Data;
{
  int *DataIndex;

  while ( DataStart <= DataEnd ) {
    DataIndex = DataStart + ( DataEnd - DataStart ) / 2;
    if ( *DataIndex > Data )
      DataEnd = DataIndex - 1;
    else if ( *DataIndex < Data )
      DataStart = DataIndex + 1;
    else
      return( DataIndex );
  }
  return( NULL );
}

2分検索は、アルゴリズムがシンプルで処理速度も速いので、利用価値も高いと思います。欠点と言えば最初にソートする必要がある点でしょうか。例えばデータ列を並べ替えることなく何番目の要素かを検索したいような場合は全く不可能ではないにしてもそれなりの工夫が必要になります(データ列を別のメモリにコピーして、かつ各要素のインデックスを保持させるなどすれば一応使えそうですが)。
最後に、2分検索を使った応用例を示したいと思います。以前、楕円描画のアルゴリズムを紹介したときに、サンプルプログラム内で数値の平方根を求めるルーチンを2分検索を利用して作成しました。このとき使用した言語はアセンブラでしたが、これをC言語を使って再度サンプルとして示したいと思います。

double SquareRoot( Data )
unsigned int Data;
{
  double SquareRootData;
  int Gap;

  Data <<= 16;
  SquareRootData = Data / 2;
  for ( Gap = SquareRootData / 2 ; Gap != 0 ; Gap /= 2 ) {
    if ( Data > SquareRootData * SquareRootData )
      SquareRootData += Gap;
    else if ( Data < SquareRootData * SquareRootData )
      SquareRootData -= Gap;
    else
      return( SquareRootData / 256 );
  }
  return( SquareRootData / 256 );
}

関数SquareRootは、与えられた正の整数Dataの平方根を返す関数です。Dataの中央値を初期値(SquareRootData)とし、さらにその1/2を増減分(Gap)として

という操作を、Gapが0になるまで繰り返します。当然Gapの値は1回のループ毎に半分にしていきます。
ただし、このままではあまりにも精度が悪いので、引数はいったん16ビットにシフト(つまり65536倍)してから処理を行い、最後に求めた値を256で割ってから返しています。

このやり方だと精度はあまりよくはありませんが(整数の平方を引数で渡しても、返ってきた値が整数になるとは限りません(^^;;; )、処理が単純な分、処理速度も早いので便利です。まあ、平方根を算出するときの一例と見ておいてください(Cの場合はたいていライブラリにsqrt()関数があるので、これを使う機会はほとんどないと思います。もちろん、もっとまともなやり方もちゃんとあります)。

2)木検索

2分検索は、配列がソートされていることが前提条件となることを除けば、データの検索・探索用途にはかなり有用なアルゴリズムでしたが、データを検索しつつその要素を配列中に挿入するような操作を行う場合には、要素の移動にかなりの時間を要してしまうためあまり向いていません。
ここでは、データの追加・削除を伴う探索に有効なアルゴリズムである木検索(Tree Search)を紹介します。

木検索には、ソート・ルーチンの「ヒープ・ソート」の章で紹介した2分木(Binary Tree)を使用します。2分木を木検索で使用するには、まず任意の節Aに対して、左の部分木(Aより下位にある木全体)にはAに入ったデータより小さなデータ、逆に右の部分木にはAに入ったデータより大きなデータが位置するように木を構成する必要があります。このように構成された木を「2分検索木(Binary Search Tree)」と呼びます。

2分検索木からのデータ検索は次の手順で行えます。

1)検索データXを、根に置いたデータRと比較する
2)
  1. X = Rなら検索終了
  2. X < RならXは左部分木の中にあるので、左の子を新たな根として 1)へ戻る
  3. X > RならXは右部分木の中にあるので、右の子を新たな根として 1)へ戻る
3)外部節(木の末端)に突き当たった時点で対象データがなく検索不成功

まずは上記アルゴリズムのサンプル・プログラムを示します。

/* 2分検索木用構造体 */
struct BinaryTree {
  struct BinaryTree *left;  /* 左部分木のポインタ */
  struct BinaryTree *right; /* 右部分木のポインタ */
  int data;                 /* データ */
};

/* 木検索メインルーチン */
struct BinaryTree *TreeSearch( RootTree, Data )
struct BinaryTree *RootTree;                      /* 根のポインタ */
int Data;                                         /* 検索対象データ */
{
  struct BinaryTree *Tree;

  Tree = RootTree;
  while( Tree != NULL ) {
    if ( Data < Tree->data )
      Tree = Tree->left;
    else if ( Data > Tree->data )
      Tree = Tree->right;
    else break;
  }
  return( Tree );
}

さて、ただ検索を行うだけだったら木検索を使うメリットはほとんどありません。配列にして2分検索を使った方が処理速度の面でもメモリ効率の面でも優れています。前にも述べた通り、木検索が最も効果を発揮するのは、検索と並行してデータを挿入するなど、データ群が増減する場合です。
2分検索木に対するデータの挿入は、まずデータを探索して、突き当たった外部節に新たなデータを入れてやることで実現できます。この処理を加えたサンプルプログラムを以下に示します。

/* 2分検索木用構造体 */
struct BinaryTree {
  struct BinaryTree *left;  /* 左部分木のポインタ */
  struct BinaryTree *right; /* 右部分木のポインタ */
  int data;                 /* データ */
} BINARY_SEARCH_TREE[TREE_SIZE];

/* 挿入する節のバッファ割り当て用ルーチン */
struct BinaryTree *TreeAlloc( Data )
int Data;
{
  static int TreeIndex = 0;

  if ( TreeIndex >= TREE_SIZE ) return( NULL );
  ( BINARY_SEARCH_TREE[ TreeIndex ] ).data = Data;
  ( BINARY_SEARCH_TREE[ TreeIndex ] ).left = NULL;
  ( BINARY_SEARCH_TREE[ TreeIndex ] ).right = NULL;
  return( &BINARY_SEARCH_TREE[ TreeIndex++ ] );
}

/* 挿入付木検索メインルーチン */
struct BinaryTree *TreeSearch2( RootTree, Data )
struct BinaryTree *RootTree; /* 根のポインタ */
int Data;                    /* 検索対象データ */
{
  struct BinaryTree *Tree;

  Tree = RootTree;
  while( 1 ) {
    if ( Data < Tree->data ) {
      if ( Tree->left == NULL )
        return( Tree->left = TreeAlloc( Data ) );  /* 左部分木のポインタがNULLならば節を挿入 */
      else
        Tree = Tree->left;
    } else if ( Data > Tree->data ) {
      if ( Tree->right == NULL )
        return( Tree->right = TreeAlloc( Data ) ); /* 右部分木のポインタがNULLならば節を挿入 */
      else
        Tree = Tree->right;
    } else return( Tree );
  }
}

上記サンプルでは、対象データが木の中に見つからずに外部節に突き当たったら、有限個の要素を持つ配列BINARY_SEARCH_TREEにデータを登録してそのポインタを木につなげ、且つその登録したポインタを返しています。配列がいっぱいになっていたらNULLが返されます。

空の2分検索木に対して、上に示したデータの検索・挿入処理を連続して行えば、2分検索木を作成することができます。あるデータ列の要素から2分検索木を構築する処理を行うルーチンを下に示します。

/* 2分検索木作成ルーチン */
int MakeBinarySearchTree( RootTree, DataList, ListSize )
struct BinaryTree *RootTree; /* 根のポインタ */
int *DataList;               /* 検索対象データ配列 */
int ListSize;                /* 配列の大きさ */
{
  int i, cnt;
  struct BinaryTree *Tree;

  RootTree = TreeAlloc( DataList[0] );
  cnt = 1;
  for ( i = 1 ; i < ListSize ; i++ ) {
    Tree = RootTree;
    while ( 1 ) {
      if ( DataList[i] < Tree->data ) {
        if ( Tree->left == NULL ) {
          if ( ( Tree->left = TreeAlloc( DataList[i] ) ) == NULL )
            return( 0 );
          cnt++;
          break;
        } else Tree = Tree->left;
      } else if ( DataList[i] > Tree->data ) {
        if ( Tree->right == NULL ) {
          if ( ( Tree->right = TreeAlloc( DataList[i] ) ) == NULL )
            return( 0 );
          cnt++;
          break;
        } else Tree = Tree->right;
      } else break;
    }
  }
  return( cnt ); /* 実際に登録されたデータ数を返す */
}

さらに、あらかじめ2分検索木型の構造体にデータだけ並べておいて(左右のリンクポインタはすべて空にしておく)、リンクポインタだけを決めていくやり方も考えられます。

int MakeBinarySearchTree2( RootTree, TreeSize )
struct BinaryTree *RootTree; /* 根のポインタ */
int TreeSize;                /* データ列の大きさ */
{
  int i, cnt;
  struct BinaryTree *Tree;

  cnt = 1;
  for ( i = 1 ; i < TreeSize ; i++ ) {
    Tree = RootTree;
    while ( 1 ) {
      if ( (RootTree[i]).data < Tree->data ) {
        if ( Tree->left == NULL ) {
          Tree->left = &RootTree[i];
          cnt++;
          break;
        } else Tree = Tree->left;
      } else if ( (RootTree[i]).data > Tree->data ) {
        if ( Tree->right == NULL ) {
          Tree->right = &RootTree[i];
          cnt++;
          break;
        } else Tree = Tree->right;
      } else break;
    }
  }
  return( cnt ); /* 実際に登録されたデータ数を返す */
}

上に示したサンプルは、どちらも重複するデータは登録しないようになっています。よって後者では、もし一致する値が木の中に見つかったら、その節はどこにもリンクされず無駄になってしまいます。

3)AVL平衡木

検索アルゴリズムでは、データを比較する回数が処理速度を左右します。木検索の場合、検索回数は最大で2分検索木の高さになりますが、木の高さは節の個数(すなわちデータ数)だけではなくて、木の形にも左右されます。
n個の節からなる2分木の高さは、節が左右均等に配分されている場合log2n程度に収まりますが、木が完全に退化して線形リストと化した場合はnになります。データの挿入を同時に行っている場合は木がどのような形に成長するか予測することができないため、最悪n回の比較を行う必要が生じる可能性もあるわけです(たとえば、空の木にデータが昇順で追加されていった場合、その木は線形リストになるため、比較回数も最大n回になります)。

木の左右のバランスがとれた状態のことを平衡な(balanced)状態といいます。特にすべての節において、左右の部分木に含まれる節の個数の差が0か1である状態を完全平衡(perfectly balanced)といいます。
完全平衡木は、同じ個数の節を持つ木の中で最も高さが低いので、2分検索木を常に完全平衡状態に保つことができれば比較回数を最小に抑えることができます。しかし、2分検索木に節を追加してから完全平衡に戻す処理はかなり複雑らしく、検索処理が多少早くなったくらいでは元をとることができないようです。
そこで、木の高さを最小にすることはあきらめて、"すべての節において、左右の部分木の高さの差が1以下"という条件をやや緩めた平衡性の定義が存在します。この平衡性の定義は、提案者Adel'son-Vel'skiiとLandisの名をとってAVL平衡と呼ばれているようです。AVL平衡木は、完全平衡木よりせいぜい50%しか高くならないことが証明されています。

ある節を挿入したときに平衡が崩れる可能性があるのは、挿入した節の祖先(ancestor;ある節から根までさかのぼるときに通った節)に限られるので、AVL平衡を保ちながら節を挿入する処理フローは次のようになります。

  1. 検索後、節を挿入する
  2. 検索した道筋に沿って根までさかのぼり、各節の平衡性を検査する
  3. 平衡性が崩れた節を見つけたら、適当に節を回して(入れ替えて)平衡性を回復する

一番重要なのが3番目の処理ですが、再平衡化のためにどのように節を回転させればよいかは、どのようなときに平衡性が崩れるかを考えてみれば自ずと明らかになります。根に節が1つぶら下がった最も単純な2分木を考えてみた場合、この木に節を追加することで左右の節の高さが1より大きくなるパターンは、以下の4パターンになります(ここで根の節をA、その子の節をBとしておきます)。

  1. Aの左側にBがあり、Bの左側に節が追加される
  2. Aの左側にBがあり、Bの右側に節が追加される
  3. Aの右側にBがあり、Bの左側に節が追加される
  4. Aの右側にBがあり、Bの右側に節が追加される

fig7-2-1.png

上に示した3つの節を持つ部分木において、節の高さの差が0か1になるようにするには、それぞれ次のように節を回転させればよいことになります。

  1. AはBの右側につなげ、Bを新たな根とする
  2. AはCの右側、BはCの左側につなげ、Cを新たな根とする
  3. BはCの右側、AはCの左側につなげ、Cを新たな根とする
  4. AはBの左側につなげ、Bを新たな根とする

fig7-2-2.png

ここでは2つの節のみを持つ部分木に新たな節を挿入した場合を考えましたが、節A,B,Cの外部節にも部分木がぶら下がっていて、かつAとCの部分木における高さの差が1である場合、節Cの部分木に新たな節が挿入されて、高さの差が1より大きくなるときのパターンと、その再平衡化も上に示した4つのみになります。すなわち

  1. Aの左側にBがあり、Bの左側の節Cにある部分木の高さが1増加する
    →AはBの右側につなげ、Bを新たな根とする(Bの右部分木はAの左部分木にする)
  2. Aの左側にBがあり、Bの右側の節Cにある部分木の高さが1増加する
    →AはCの右側、BはCの左側につなげ、Cを新たな根とする(Cの左部分木はBの右部分木、Cの右部分木はAの左部分木にする)
  3. Aの右側にBがあり、Bの左側の節Cにある部分木の高さが1増加する
    →BはCの右側、AはCの左側につなげ、Cを新たな根とする(Cの左部分木はAの右部分木、Cの右部分木はBの左部分木にする)
  4. Aの右側にBがあり、Bの右側の節Cにある部分木の高さが1増加する
    →AはBの左側につなげ、Bを新たな根とする(Bの左部分木はAの右部分木にする)

文章にしただけでは少々ややこしいですね。下の図を参考にしてください。

fig7-2-3.png

上の図では、1と2の2つのパターンしか示していませんが、3,4はそれぞれ1,2のパターンを左右反転させたものになります。

A,B,Cを回転させて再平衡化した後に、下にぶら下がっていた部分木が別の節へつなぎ直されている場合がありますが、再リンク後もそれぞれの節における大小関係が崩れていないことに注意してください。たとえば、1番目のパターンではBの右部分木(以降Pとします)はAの左部分木に再リンクされていますが、Pの全要素は一度Aの要素と比べて小さいと判断されており、Pの全要素<Aの要素が成立しているため、問題ありません。

上記再平衡化にはそれぞれ名前があって、

とそれぞれ呼ぶそうです。

AVL平衡化処理を加えた木検索処理のサンプルプログラムを以下に示します。

/* 2分検索木用構造体 */
struct BinaryTree {
  struct BinaryTree *left;  /* 左部分木のポインタ */
  struct BinaryTree *right; /* 右部分木のポインタ */
  int balance;              /* 節の平衡度 */
  int lr_flg;               /* 左右どちらの節が重くなったか？ */
  int data;                 /* データ */
} BINARY_SEARCH_TREE[TREE_SIZE];

static struct BinaryTree *ROOT_TREE; /* 根のポインタ */

/* 挿入する節のバッファ割り当て用ルーチン */
struct BinaryTree *TreeAlloc( Data )
int Data;
{
  static int TreeIndex = 0;

  if ( TreeIndex >= TREE_SIZE ) return( NULL );
  ( BINARY_SEARCH_TREE[ TreeIndex ] ).data = Data;
  ( BINARY_SEARCH_TREE[ TreeIndex ] ).balance = 0;
  ( BINARY_SEARCH_TREE[ TreeIndex ] ).left = NULL;
  ( BINARY_SEARCH_TREE[ TreeIndex ] ).right = NULL;
  return( &BINARY_SEARCH_TREE[ TreeIndex++ ] );
}

/* データ検索・挿入ルーチン */
struct BinaryTree *AVLTreeSearch( Data )
int Data;
{
  struct BinaryTree *Tree;
  struct BinaryTree *TreeStack[TREE_HEIGHT]; /* データ比較を行った節のポインタ配列 */
  int i;

  Tree = ROOT_TREE;
  i = 0;
  while( 1 ) {
    /* データは左側へ */
    if ( Data < Tree->data ) {
      Tree->lr_flg = -1;     /* 左部分木が重くなった */
      TreeStack[i++] = Tree; /* 比較を行った節のポインタをスタックへ */
      if ( Tree->left == NULL ) {
        if ( ( TreeStack[i] = Tree->left = TreeAlloc( Data ) ) == NULL )
          return( NULL );
        AVLCheck( TreeStack, &TreeStack[i-1] ); /* AVL平衡のチェック */
        return( Tree->left );
      } else
        Tree = Tree->left;
    /* データは右側へ */
    } else if ( Data > Tree->data ) {
      Tree->lr_flg = 1;      /* 右部分木が重くなった */
      TreeStack[i++] = Tree; /* 比較を行った節のポインタをスタックへ */
      if ( Tree->right == NULL ) {
        if ( ( TreeStack[i] = Tree->right = TreeAlloc( Data ) ) == NULL )
          return( NULL );
        AVLCheck( TreeStack, &TreeStack[i-1] ); /* AVL平衡のチェック */
        return( Tree->right );
      } else
        Tree = Tree->right;
    /* 一致した!! */
    } else return( Tree );
  }
}

/* AVL平衡のチェックルーチン */
void AVLCheck( StackStart, StackEnd )
struct BinaryTree **StackStart,**StackEnd;
{
  struct BinaryTree **Stack;

  for ( Stack = StackEnd ; Stack >= StackStart ; Stack-- ) {
    ( Stack[0] )->balance += ( Stack[0] )->lr_flg; /* 平衡度の更新 */
    /* 平衡度は0 ... 平衡性は改善されたからループを抜ける */
    if ( ( Stack[0] )->balance == 0 )
      break;
    /* 平衡度は1を越えた ... 再平衡化が必要 */
    if ( ( Stack[0] )->balance > 1 ) {
      if ( ( Stack[1] )->balance > 0 )
        RRSingleRotate( Stack );
      else
        RLDoubleRotate( Stack );
      break;
    /* 平衡度は-1を越えた ... 再平衡化が必要 */
    } else if ( ( Stack[0] )->balance < -1 ) {
      if ( ( Stack[1] )->balance > 0 )
        LRDoubleRotate( Stack );
      else
        LLSingleRotate( Stack );
      break;
    }
  }
}

/* 1レベル上位のリンクポインタを更新 */
void LinkUpperPointer( OldTree, NewTree )
struct BinaryTree **OldTree, **NewTree;
{
  if ( *OldTree == ROOT_TREE )
    ROOT_TREE = *NewTree;
  else if ( ( *( OldTree - 1 ) )->lr_flg > 0 )
    ( *( OldTree - 1 ) )->right = *NewTree;
  else
    ( *( OldTree - 1 ) )->left = *NewTree;
}

/* LL1重回転 */
void LLSingleRotate( TreeStack )
struct BinaryTree **TreeStack;
{
  struct BinaryTree *bt;

  bt = ( TreeStack[1] )->right;
  ( TreeStack[1] )->right = TreeStack[0];                /* B->right = A */
  ( TreeStack[0] )->left = bt;                           /* A->left = B->right */
  /* 1レベル上位のリンクポインタを更新 */
  LinkUpperPointer( &TreeStack[0], &TreeStack[1] );
  /* 平衡度のリセット */
  ( TreeStack[0] )->balance = 0;
  ( TreeStack[1] )->balance = 0;
}

/* RR1重回転 */
void RRSingleRotate( TreeStack )
struct BinaryTree **TreeStack;
{
  struct BinaryTree *bt;

  bt = ( TreeStack[1] )->left;
  ( TreeStack[1] )->left = TreeStack[0];                 /* B->left = A */
  ( TreeStack[0] )->right = bt;                          /* A->right = B->left */
  /* 1レベル上位のリンクポインタを更新 */
  LinkUpperPointer( &TreeStack[0], &TreeStack[1] );
  /* 平衡度のリセット */
  ( TreeStack[0] )->balance = 0;
  ( TreeStack[1] )->balance = 0;
}

/* LR2重回転 */
void LRDoubleRotate( TreeStack )
struct BinaryTree **TreeStack;
{
  struct BinaryTree *bt;

  bt = ( TreeStack[2] )->left;
  ( TreeStack[2] )->left = TreeStack[1];                 /* C->left = B */
  ( TreeStack[1] )->right = bt;                          /* B->right = C->left */
  bt = ( TreeStack[2] )->right;
  ( TreeStack[2] )->right = TreeStack[0];                /* C->right = A */
  ( TreeStack[0] )->left = bt;                           /* A->left = C->right */
  /* 1レベル上位のリンクポインタを更新 */
  LinkUpperPointer( &TreeStack[0], &TreeStack[2] );
  /* 平衡度のリセット */
  if ( ( TreeStack[2] )->balance > 0 ) {
    ( TreeStack[0] )->balance = 0;
    ( TreeStack[1] )->balance = -1;
  } else if ( ( TreeStack[2] )->balance < 0 ) {
    ( TreeStack[0] )->balance = 1;
    ( TreeStack[1] )->balance = 0;
  } else {
    ( TreeStack[0] )->balance = 0;
    ( TreeStack[1] )->balance = 0;
  }
  ( TreeStack[2] )->balance = 0;
}

/* RL2重回転 */
void RLDoubleRotate( TreeStack )
struct BinaryTree **TreeStack;
{
  struct BinaryTree *bt;

  bt = ( TreeStack[2] )->right;
  ( TreeStack[2] )->right = TreeStack[1];                /* C->right = B */
  ( TreeStack[1] )->left = bt;                           /* B->left = C->right */
  bt = ( TreeStack[2] )->left;
  ( TreeStack[2] )->left = TreeStack[0];                 /* C->left = A */
  ( TreeStack[0] )->right = bt;                          /* A->right = C->left */
  /* 1レベル上位のリンクポインタを更新 */
  LinkUpperPointer( &TreeStack[0], &TreeStack[2] );
  /* 平衡度のリセット */
  if ( ( TreeStack[2] )->balance > 0 ) {
    ( TreeStack[0] )->balance = -1;
    ( TreeStack[1] )->balance = 0;
  } else if ( ( TreeStack[2] )->balance < 0 ) {
    ( TreeStack[0] )->balance = 0;
    ( TreeStack[1] )->balance = 1;
  } else {
    ( TreeStack[0] )->balance = 0;
    ( TreeStack[1] )->balance = 0;
  }
  ( TreeStack[2] )->balance = 0;
}

まず、2分検索木構造体に加えられた新たな要素についてですが、balanceはその節の平衡度、lr_flgはデータ比較の結果、データが左右どちらの部分木へ移動したのかを示すフラグを表します(どちらも右部分木が重くなった場合を正としています)。
データの検索時(関数AVLTreeSearch)に、データ比較を行った節のポインタを配列TreeStackへ代入していますが、これは後で平衡性のチェックを行うときに必要となります。また、この時いっしょにlr_flgを更新しています。
データ挿入後の平衡性チェックは関数AVLCheckで行います。ここではまず平衡度を更新して、その結果によって処理を振り分けています。

平衡度が0
上位側の節における平衡度の変化はなくなったので、これ以上チェックを行う必要はなくループを抜ける

平衡度が1を越えた
再平衡化が必要となる
＊1レベル下位の節の平衡度が0の場合はすでにループを抜けているはずなので無視できます

平衡度が-1を越えた
再平衡化が必要となる

平衡度が+1,-1の場合は、今注目している節については許容範囲であるものの、この影響で上位の節の平衡性が崩れている可能性があるためチェックを続けなければなりません。また、1度平衡性を回復させたら、その上位側の節については平衡度の変化はないので、それ以上チェックを行う必要はなくてループを抜けることができます。
平衡性を改善するため節を回転する処理は、単純に節のポインタのつなぎ替えと平衡度のリセットを行っているだけですが、回転後に1つ上位の節とのリンクポインタも更新する必要があり、その処理を関数LinkUpperPointerで行っています。特に、回転させた節の中に根が含まれていた場合は根の節が入れ替わるため、節が根であったかどうかを調べる必要があることも注意しなければなりません。

上記サンプル・プログラムのソースコードを用意しました。上に示したものと全く同じものですが、木を表示するための簡単な関数も含まれています。一応Linux上でコンパイルして動作確認を行っています。

サンプル・プログラムをダウンロードする。
・LZH形式(avl.lzh)
・ZIP形式(avl.zip)

<参考文献>
  1. Oh!X 1992年12月号 X68000マシン後プログラミング 「探しもの」
  2. Oh!X 1993年7月号 X68000マシン後プログラミング 「木検索」

[Go Back]前に戻る [Back to HOME]タイトルに戻る