二分木探索

理系ネタ J

今まで自分の研究用コードのあちこちで二分木を使ってたけど、再利用がうまくできなかったんでシンプルで応用の効くクラスを作っておこうと思った。具体的用途は、整数が何個かの組から定義される Hoge があり、これのリストを管理したい。たとえばFEMメッシュの場合は Hogeとして辺、面、四面体などが考えられ、それが含む頂点の番号の組でidentifyできる。そしてHoge構造体には座標とか、辺ならばそれを含む面へのポインタ、四面体ならば４つの面へのポインタなどを保持したい。そして整数の組をあたえればそれに対応した Hoge を返すクラス Btree を作りたい。

たとえば Delaunay 分割と呼ばれる、頂点リストを線で結んで空間を四面体に分割する Watson アルゴリズムは以下のようになる。

・頂点全部を含む四面体を作成
    for(v=全ての頂点)
    {
	for(f=全ての四面体表面三角形)
	    f->flag=0;

	for(t=全ての四面体)
	{
	    if (vがtの外接円の内部にある)
	    {
		for (f=tの４つの表面三角形)
		{
                    f->flag++;
                }
                delete t;               
	    }
	    
	}

	for(f=全ての四面体表面三角形)
	{
	    if (f->flag == 2)
		delete f;
	    else if (f->flag ==1)
	    {
		四面体のリスト += new 四面体(頂点 v, 面 fの３頂点);
		面のリスト += 新しい面３つ、 面(頂点v, 面fの２頂点)*3種類
	    }
	}//f
    }//v
}//end

class Btree
{
    public:
	void *Find(int *key);
	void Delete(int *key);
	void Insert(int *key, void *iptr);
	Btree(int n_key);
	~Btree();
    private:
	int nkey;
	BtData *Root;
	BtData *FindAux(int *key, BtData ***prev);
	void DeleteNode(BtData *p);
}

int main()
{
    Btree *bt = new Btree(4);

    Tetra *t;
    int vertexlist[4] = {1,2,3,4};

    t = bt->Find(vertexlist);
    if (t == NULL)
    {
	t = new Tetra(vertexlist, ... ,...);
	bt->Insert(vertexlist, t);
    }

    ...



    bt->Delete(vertexlist);
    delete bt;
}

ノードを消す場合の処理、Wikipediaの説明が参考になったけど、
http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
このコード、引数の書き方がよく分からない。たとえば left==NULL の時の処理、rightもNULLだったら自分を消して親から自分へのポインタをNULLにしないといけない。そのためには親から自分へのポインタのポインタ、**nodeを引数にしないといけない。これはそういう書き方になってるんだろうか。

FindAux の Node ***prev てのはサーチしてなかった場合、新しく挿入すべきノード(Node)を指している親のポインタ(*Node)を書き換えるためにそのポインタのアドレス(**Node)が必要なのでその変数**Nodeを用意してそのアドレス(***Node)を渡している。頂きました！星三つです！なんかもっとうまい書き方あるのか。
あー関数の戻り値を**Node にしてノード自体はその指し示すもの、と計算すればNULLの場合も含めてOKだな。

for(t=全ての四面体)、てのをどう実装するか。クラスの中から出なくてよければ再帰で一発だが、それだと応用が利かない。リスト void**List をまとめて取ってくる、という手もあるが、どうも美しくないな。
for(t= 木の一番左;t!=NULL; t=次のt)ということだ。一番左は簡単だが、「次のt」をどうするか。
現在のtのkeyを+1だけした、たぶん実在しないkeyをまず探す。見つかればOK。ない場合、どこか外れで止まる。このkeyをノードｍとして追加した場合、その次の値を持つノードをｎとすると、ｍはn->left->RightMost();になる。ということは、外れにいくまでに最後にleftを選んだ時の親が求める次のノードだ。
訂正：現在のkeyをまず探す。そのノードでright!=NULL ならright->LeftMost() が次の値を持つノード。right=NULLならここに来るまでに最後にleftを取った時の親が次の値を持つノード。
for(t= Bt->LeftMost();t!=NULL; t=Bt->FindNext(t->key))となるか。


応用としてさっそくこいつを疎行列の計算に使ってみた。
こんな感じかな。

#include "bitree.h"

class Kij
{
    public:
	int ij[2];
	double mat;
	Kij(int i, int j);
};

Kij::Kij(int i, int j)
{
    if (i<j)
    {
	ij[0]=i;
	ij[1]=j;
    }
    else
    {
	ij[1]=i;
	ij[0]=j;
    }
    mat=0;
}

Btree *bt;

void AddMat(int i, int j, double m0)
{
    int key[2];
    key[0]=i;
    key[1]=j;
    Kij *kij = bt->Find(key);
    if (kij==NULL) kij = new Kij(i,j);

    kij->mat += m0;
}