■トゥリー(樹木構造)■

↑

リストとトゥリー

リストの場合はデータが横1列に並んでおり、各データには「前のデータ」と「後ろのデータ」がある。

これに対して、トゥリーというのは、1個のデータ(根,root)から枝分かれしていき、各データにちょうど1個の親(parent)と複数の子供(child)があるようなデータ構造を言う。(ただし根だけは親を持たない)

★トゥリー構造において、

(1)出発点になっているデータを根(root)と呼ぶ。普通トゥリーは根を一番上に書く。

(2)直接線でつながっているデータは親子関係にあるという。トゥリーにおいて根以外のデータは唯一つの親を持つ。各データの子供が2個以下のトゥリーは特に二分木(Binary Tree)と呼ばれる。

(3)親と子をつなぐ線を枝(edge)と呼ぶ。又、各データを節(node)と呼ぶ。

(4)一番下位のデータ、つまり子供を持たないデータを葉(Leaf)と呼ぶ。


トゥリー構造をコンピュータ上で実現する場合、リストと同様にポインターを用いることが多い。(用いない方法もある。)

【Cコーディング例】二分木

typedef struct {
    long   code;
    char*  name;
} KST;
typedef struc {
    KST    kst;
    int    parent;
    int    child1;
    int    child2;
} KSTNODE;

int kscnt;
int ksaloc;
KSTNODE* ks;
char* ksbuf;

ksaloc = KSALOCFIRST; ksbuf = (char*)malloc(KSBUFFIRST); ks = (KSTNODE*)malloc(ksaloc * sizeof(KSTNODE));

★特殊な名称を持つトゥリー

探索木(Search Tree )
二分木の一種で親と二人の子供の値を比較した時、必ず、左の子供 < 親 < 右の子供 となっている物。大量のデータを分類するのに使用する。探索木の上で値の小さい順にデータをたどることをTree Walkingと言う。
ヒープ・トゥリー(Heap Tree )
二分木の一種で親データの値が必ず子供の値より大きい(小さい)トゥリー。ヒープソートという高速ソートに使用される。このトゥリーは普通ポインターを使わずに管理される。(詳細はその内ソートの解説のところで書きます)
Bトゥリー(B Tree)
各節において、子供の値は左から順に小さいように並んでいて、親の値は一番右側の子供の値(つまり最大値)と一致するようになっているトゥリーを言う。古いiSAM・VSAMファイルに代わる索引管理方法として、1970年代から普及してきた。データベースの索引としてよく使われる。

(2001.2.5)

(C)copyright ffortune.net 1995-2016 produced by ffortune and Lumi.
お問い合わせはこちらから