C/C++ - 構造的プログラミング編 第6回 〜連想配列〜

赤黒木基本構造体

平衡性

前回実装してみた探索木ヘッダについては、mScan() 以外の全てのメソッドが protected となっていることから 分かるように、実は、この時点では大きな問題があります。

例えば、常に右子にばかりインスタンスを追加するような状況になると、結局のところ、線形リストと同じ状態となります。

このような状況を避けるために、前回書いたメンバのうち、pRank と dIsRed というものを使って、 ヘッダの子インスタンス群の平衡性を制御できるように拡張してみます。

メンバ

前回の探索木基本構造体を継承して、メンバ関数を追加します。

struct CPbasicBinary : CPbasicSearch{
 CPbasicBinary*& mParent(void);
 CPbasicBinary*& mLeft(bool noThrow=true);
 CPbasicBinary*& mRight(bool noThrow=true);
 void mSingleRotate(void);
 void mDoubleRotate(void);
};

最初の3つのメンバ関数についてですが、キャストの手間を省くために、 CPbasicSearch の同名のメンバ関数の戻り値を自身に変えているだけです。 mParent() だけを書くなら、単純にこう実装します。

CPbasicBinary*& CPbasicBinary::mParent(void){
 return *reinterpret_cast(&CPbasicSearch::mParent());
}

回転操作

平衡化の基本操作として、回転操作なるものが定義されます。

void CPbasicBinary::mSingleRotate(void){
 CPbasicBinary *ppp=0,*pp=0,*p=0;
 p=mParent();
 pp=p->mParent();
 ppp=pp->mParent();
 if(pp->mGetState(dIsLeft)) ppp->mAddLeft(p);
 else ppp->mAddRight(p);
 if(mGetState(dIsLeft)){
  pp->mAddLeft(p->pNext);
  p->mAddRight(pp);
 }else{
  pp->mAddRight(p->pChildren);
  p->mAddLeft(pp);
 }
 p->mParent()=ppp;
}

簡単に言い切ってしまえば、この操作により、this->p->pp->ppp という1つの列が、 this/pp->p->ppp という分岐のある列に変更されます。

mDoubleRotate() は単純に、この操作を2回行うように定義します。

void CPbasicBinary::mDoubleRotate(void){
 CPbasicBinary* p=mParent();
 if(mGetState(dIsLeft)) mLeft()->mSingleRotate();
 else mRight()->mSingleRotate();
 p->mSingleRotate();
}

平衡二分探索木

ヘッダクラス

前回の CSstdSearch を継承して、平衡探索二分木ヘッダクラス CVSet を次のように宣言します。

class CVSet : CSstdSearch{
 CPbasicBinary* pCurrent;
 void mRebalanceOnInsert(CPbasicBinary* tTarget);
public:
 CVSet(void);
 CPbasicBinary& mInsert(CPbasicBinary* rInstance);
 bool mSearch(CPbasicBinary& rTarget);
 CPbasicBinary& mCurrent(void);
};

CSstdSearch では CPbasicSearch* が返ってくるため、NIL であるかのチェックなどをカプセル化するため、 一時的に pCurrent というプロパティに格納しておきます。

そういった都合で戻り値の型を変更するため、オーバーライドせずに、private で継承して CSstdSearch のメソッドを そのまま隠蔽しています。

平衡化操作

mInsert() メソッドで行う操作は、先程説明したように、CSstdSearch::mInsert() を呼び出し、 それを pCurrent に代入することとなりますが、その後に、平衡化作業を行います。

void CVSet::mRebalanceOnInsert(CPbasicBinary* v){
 CPbasicBinary *p=0, *pp=0, *w=0;
 p=v->mParent();
 if(p->mIsRoot()) return;
 pp=p->mParent();
 int pState=p->mGetState();
 if(pState&p->dIsRed){
  if((w=(pState&p->dIsLeft)?pp->mRight():pp->mLeft())&&
  (w->mGetState(w->dIsRed))){
   ++pp->pRank;
   if(!pp->mIsRoot()&&pp->mParent()->mGetState(pp->dIsRed))
   mRebalanceOnInsert(static_cast<CPbasicBinary*>(pp));
  }else{
   if(v->mGetState(v->dIsLeft)){
    if(pState&p->dIsLeft) v->mSingleRotate();
    else v->mDoubleRotate();	
   }else{
    if(pState&p->dIsLeft) v->mDoubleRotate();
    else v->mSingleRotate();	
   }
  }
 }
}

6行目にあるように、追加インスタンスに対して、その親が dIsRed があると検出されるのを合図に、 平衡化を行います。簡単に分類すると、9,11行目のように連鎖的に親方向の pRank を上昇させる方法と、 14,15/17,18 行目にあるように回転操作を行う方法とに分けられます。

挿入操作と探索操作

この平衡化操作を合わせて、挿入操作は結局次のように実装されます。

CPbasicBinary& CVSet::mInsert(CPbasicBinary* rInstance){
 mRebalanceOnInsert(pCurrent=static_cast<CPbasicBinary*>(
  CSstdSearch::mInsert(rInstance))
 );
 return *pCurrent;
}

このように平衡化作業を行うことで、mSearch() は常に対数オーダーで実行されます。

bool CVSet::mSearch(CPbasicBinary& rTarget){
 pCurrent=static_cast<CPbasicBinary*>(
  CSstdSearch::mSearch(rTarget)
 );
 return pCurrent->pRank>0;
}

連想配列

連想配列とは、添字の型が任意の配列を指します。C 配列の添字は、0 スタートの unsigned int 連続値ですが、 難しいことを考えずに、ここでは添字を int 型離散値に拡張してみます。

連想配列インスタンス

キューのところで、CPintData なるものを試しに作ってはみましたが、CPbasicBinary にまで対応したほんの少しだけ まともな基本構造体を定義しておきます。CPbasicBinary を継承するため、自動的に CPbasicTree を継承することになり、 結局のところ、CVSet だけでなく、CPintData の代わりとして、CVQueueや CVList にも使うことが出来ます。

struct CPbasicIndex : CPbasicBinary{
 int pID;
 inline CPbasicIndex(int rID=-1):pID(rID){}
 inline int mCompare(CPbasicSearch& rRhs){
  CPbasicIndex* rhs=dynamic_cast<CPbasicIndex*>(&rRhs);
  return rhs?pID-rhs->pID:-1;
 }
};

簡単に実装の方針を言うならば、この CPbasicIndex の pID を unsigned int の代わりとなる 配列の添字とみなすこととして、後は、インスタンスを平衡探索二分木上に配置すれば完了ですが、 ここで、添字以外にもう1つ、順序関係には関係ない int 型メンバを持つ構造体を継承して定義しておきます。

 
struct CPindexedObject : CPbasicIndex{
 int pObj;
 inline CPindexedObject(int rID=-1, int rObj=0):
  CPbasicIndex(rID), pObj(rObj){}
}; 

連想配列クラス

結局、int[N] という C 配列と同じように動作するが、添字が int 型離散値となるようなものを作ろうとしているので、 簡単にインターフェースを書くと、こうなります。

class IArray{
public:
 virtual ~IArray(void){}
 virtual int& operator[](int tIndex)=0;
};

当然、添字オペレータの引数は、int 型の添字で返ってくるものが、その添字の位置にある int& 型の値でなければ ならないわけですね。

このインターフェースを実装するために使うのが、前回の CVSet というわけですね。

class CRArray : CVSet, virtual public IArray{
public:
 CRArray(void);
 ~CRArray(void);
 int& operator[](int tIndex);
};

挿入操作と参照操作

挿入とは、結局のところ、添字とデータから CPindexedObject* インスタンスを生成する プロセスをカプセル化した上で、そのインスタンスを追加する作業なわけですから、

CVSet::mInsert(new CPindexedObject(rIndex,rObj));

とすれば完了です。

参照する場合は、添字から CPbasicIndex& オブジェクトを作り平衡二分探索木を探索します。 もし見つかったらこれをキャストして、pObj メンバを返します。

if(CVSet::mSearch(CPbasicIndex(tIndex)))
return static_cast<CPindexedObject&>(CVSet::mCurrent()).pObj;

結局のところ、添字オペレータにはこの両方の機能を持たせます。つまり、その添字が存在しているならば それを参照し、なければそのまま挿入します。

int& CRArray::operator[](int tIndex){
 return CVSet::mSearch(CPbasicIndex(tIndex))?
 static_cast<CPindexedObject&>(CVSet::mCurrent()).pObj:
 static_cast<CPindexedObject&>(
  CVSet::mInsert(new CPindexedObject(tIndex))
 ).pObj;
}

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