C/C++ - 構造的プログラミング編 第5回 〜探索二分木〜

基本探索木構造体

線形リスト内のインスタンスは、pNext と pPrev を使っていましたが、 残る pParent と pChildren の使い方を考えてみます。例えば、次のような構造体を考えて見ます。

メンバ

struct CPbasicSearch : CPbasicTree{
 CPbasicSearch*& mParent(void);
 CPbasicSearch*& mLeft(void);
 CPbasicSearch*& mRight(void);

 void mAddLeft(CPbasicTree* rInstace);
 void mAddRight(CPbasicTree* rInstance);
 void mAddExternal(void);

 virtual int mCompare(CPbasicSearch& rRhs);
 CPbasicBinary** mScan(CPbasicSearch* rTarget);

 int pRank;
 enum CDbasicBinary{
   dIsLeft=0x00010000, dIsInner=0x00020000, dIsRed=0x00040000
  };
 bool mIsRoot(void);
 int mGetState(void);
 bool mGetState(CDbasicBinary stateFlag);
 CPbasicSearch(void);
};

追加されたメンバ関数の多くが、4つの自己参照構造体の振る舞い方を プロシージャ化したもので、大きく分けて、上のように4種類に分かれます。

インスタンスの参照

最初の3つは、二分木という構造における、親インスタンス・左子インスタンス・右子インスタンスへの アクセスを抽象化したものになります。

CPbasicSearch*& CPbasicSearch::mParent(void){
 return *reinterpret_cast<CPbasicSearch**>(pPrev?&pPrev:&pParent);
}
CPbasicSearch*& CPbasicSearch::mLeft(void){
 return *reinterpret_cast<CPbasicSearch**>(&pChildren);
}
CPbasicSearch*& CPbasicSearch::mRight(void){
 return *reinterpret_cast<CPbasicSearch**>(&pNext);
} 

左子インスタンスを pChildren、右子インスタンスを pNext に関連付けているわけですが、 親インスタンスは、単純に pParent ではなく、pPrev にもその役割を持たせています。

インスタンスの追加

次の3つがインスタンスの追加を意味するものとして定義されます。

void CPbasicBinary::mAddLeft(CPbasicTree* tTarget){
 pChildren=tTarget;
 tTarget->pParent=this;
 tTarget->pPrev=0;
}
void CPbasicBinary::mAddRight(CPbasicTree* tTarget){
 pNext=tTarget;
 tTarget->pPrev=this;
 tTarget->pParent=0;
} 
void CPbasicSearch::mAddExternal(void){
 pRank=1;
 mAddLeft(new CPbasicSearch);
 mAddRight(new CPbasicSearch);
}

mAddLeft() と mAddRight() ですが、見ての通り、左子に追加する場合は pChildren に参照させ、 左子の pParent に自身をつなぎます。また、右子に追加する場合、pNext に参照させ、 右子の pPrev に自身をつなぎます。必ず、pParent か pPrev の一方を NULL とすることで、 左子なのか右子なのかを判断します。

続いて、mAddExternal() ですが、左子と右子に CPbasicSearch インスタンスを追加しています。 この作業の意味ですが、これまでリストの終端を NULL で代行していましたが、 これに、CPbasicSearch::mParent() を使って復帰する機能を持たせた NIL を構築するためのメンバ関数です。

説明を後回しにしていますが、コンストラクタに pRank=0 を代入させておくことで、NIL の pRank を 0 としておくと、 pRank=0 となるインスタンスの親は NIL でないデータとなります。

インスタンスの順序関係

続いて出てくるものが、仮想メンバ関数 mCompare() で、その名前の通り、CPbasicSearch インスタンス同士の 順序の比較を行います。virtual とあるように、オーバーライドすることが要求されます。

その定義ですが、引数のインスタンスの順序がより後ならば負の値が、前ならば正の値が返ります。 そして、もしも順序が同じならば、 0 を返すように定義をします。

この定義のもと、mScan() というメンバ関数を次のように定義します。

CPbasicSearch** CPbasicSearch::mScan(CPbasicSearch* rTarget){
 return reinterpret_cast<CPbasicSearch**>(
  mCompare(*rTarget)<0?&pNext:&pChildren
 );
}

これによって、mCompare() と 左子、右子の関係が関連付けられます。 見ての通り、引数の順序がより後ならばそれは右子に、前ならば左子に関連付けられます。

インスタンスの状態

残りのメンバは、インスタンスがどのような状態にあるかを客観的に評価します。 簡単に以下の表にまとめます。

dIsLeft   :  自身が左子である
dIsInner  :  自身が NIL でない
dIsRed    :  自身の pRank が親の pRank と等しい
mIsRoot() :  自身、または自身の親がヘッダである

mGetState() は、dIsLeft/dIsInner/dIsRed を引数とすれば、その条件に合致すれば true を返し、 引数を入れなければ、それらのフラグの論理和を返します。

探索二分木

ここまでのメンバを使って、ヘッダを実装してみます。

探索木基底クラス

class CSstdSearch : protected CPbasicTree{
 CPbasicSearch* mScan(
  CPbasicSearch* rTarget, CPbasicSearch* rHint=0
 );
protected:
 CSstdSearch(void);
 virtual ~CSstdSearch(void);
 CPbasicSearch* mInsert(CPbasicSearch* rInstance);
 CPbasicSearch* mSearch(CPbasicSearch& rTarget);
};

これまでの説明から、CPbasicSearch インスタンスでは必ず、mCompare() による順序関係があることを前提としています。 この順序関係をもとに、左側により前方にあるインスタンスを、右側により後方にあるインスタンスを持たせることで、 左と右とで比較しながら目的のインスタンスを探します。

インスタンスの探索

探索操作ですが、実のところ、CPbasicSearch::mScan() にその操作は集約されています。 簡単に言えば、mScan() を mCompare() が非ゼロの値を返す間繰り返せばいいわけですね。

CPbasicSearch* CSstdSearch::mScan(
 CPbasicSearch* rTarget, CPbasicSearch* rHint){
 CPbasicSearch* itr=rHint?rHint:
 static_cast<CPbasicSearch*>(pChildren);
 if(itr->pRank>0){
  if(!rHint&&!itr->mCompare(*rTarget)) return itr;
  CPbasicSearch** pitr=itr->mScan(rTarget);	
  while((*pitr)->pRank>0&&(*pitr)->mCompare(*rTarget)){
   itr=*pitr;
   pitr=itr->mScan(rTarget);
  }
  return *pitr;
 }else return rHint?rHint:static_cast<CPbasicSearch*>(pChildren);
}

複雑に見えますが、要するに、5行目と7行目が本質的な操作となります。 もし、見つからなければ、5行目にあるように、NIL にたどり着き、pRank==0 の条件にかかって終了します。

mSearch() メソッドは、単純にこの mScan() を呼び出すように実装します。

インスタンスの挿入

この mScan() メソッドを使うことで、もし、NIL が返ってきた場合、その位置が挿入しようとする位置となります。

CPbasicSearch* CSstdSearch::mInsert(CPbasicSearch* rInstance){
 rInstance->mAddExternal();
 CPbasicSearch* itr=mScan(rInstance);
 while(itr->pRank>0) itr=mScan(rInstance,itr);
 if(itr->mGetState(itr->dIsLeft)){
  itr=static_cast<CPbasicSearch*>(itr->pParent);
  delete itr->pChildren;
  itr->mAddLeft(rInstance);
 }else{
  itr=static_cast<CPbasicSearch*>(itr->pPrev);
  delete itr->pNext;
  itr->mAddRight(rInstance);
 }
 return rInstance;
}

本質的には、2行目と、7,11 行目がそれに相当するわけですが、1行目で NIL を追加し、 4行目で、左子としての NIL なのか右子としての NIL なのかを判定しています。


文章作成 : yukki-ts (-+-twilight serenade-+- [stage])