アルゴリBにおける二分探索木のまとめ0(準備編)

まずは必要な知識をまとめておきます。
知ってる人からすれば特に重要なことは書いてないです。

記号表について

二分探索木の話に入る前にまず記号表について少しまとめたいと思います。(そんな大事な話でもなく、特に難しくもないので飛ばしても大丈夫です。)

記号表(Symbol Table)とは？

キーとそのキーに対応した情報を持ったデータ構造の集まり。
　例)住民票：”名前(キー)”→”住所(情報)”の集まり

また、あるキーに対応した情報を返す(田中さん(キー)の住所(情報))ことや、キーの値に応じて記号表の内容を整列(五十音順等)することが可能。

記号表抽象データ型とは？

記号表の中のある一つのデータ構造(汎用性を持たせるため"抽象"データ型)

実装

実装は構造体を用いることで簡単に行うことができる。
(STable = Symbol Tableの略)

C言語における記号表の実装例

typedef struct{
    char name[10];    //この内容がキー(名前)
    char address[10]; //この内容が情報(住所)
} STable;

あくまで抽象データ型であるため、実際に上記の構造体を使う場合は

STable s[2] = {
    {"tanaka", "tokyo"}, //田中さんは東京在住
    {"yamada", "osaka"}  //山田さんは大阪在住
};

のようにそれぞれのキーと情報を代入する必要がある。

程度の理解で問題ないと思います。
(必要そうなら追記します。とりあえずメインの話に戻ります。)

木構造

そもそも探索とは？

探索
記号表の中から探索キーと一致するキーを持つすべての項目を探すこと。

逐次探索
構造体の配列等を用いて実装した記号表において、先頭(添え字0)のキーから順に調べていき、それぞれが探索キーと一致するかどうかを調べる探索方法。

欠点→操作において時間がかかる。

解決策・・・？
木構造を用いる。
→二分探索木(今回のメイン)、2-3-4木(まだ)、赤黒木(まだ)　など

木構造とは

下の図のようにそれぞれのノード(節点)が枝分かれしていくようにつながっている構造。
f:id:rei_624:20181020214941p:plain
(数字はそれぞれのノードが持つキーを表しています。)

・一番大元のノード(ルート=根)を除いてすべてのノードはただ一つの親ノードを持つ。
・各ノードは0個以上の子ノードを持つ。
・木構造を描く時は(一般的に？)親ノードを上に、子ノードを下に描いていく。

↓用語説明↓
ノード　　：節点。データを持つ部分。
ブランチ　：枝。ノードとノードを結んでいる線。
ルート　　：根。一つの木に一つのみ存在する。全てのノードの先祖ノードにあたる。
リーフ　　：葉。枝分かれしていった最後のノードで、子を持たない。
親(ノード) ：ブランチで結ばれたノード同士において上に存在するノード。
子(ノード) ：ブランチで結ばれたノード同士において下に存在するノード。
兄弟ノード：同じ親を持つノード同士。
先祖ノード：あるノードから見て、その親ノードやさらに先の親ノード全て。
子孫ノード：あるノードから見て、その子ノードやさらに先の子ノード全て。
部分木　　：あるノードを根とし、そのノードの持つ全ての子孫ノードを含んだ木。

高さ：この講義では少し特殊なのでまとめ1で書きます。
深さ：こちらもまとめ1で書きます。

呼び方は人によって少し違うこともあると思います。

木構造を使うと何がいいの

探索にかかる平均の時間が短くなる。
新しい項目の挿入にかかる平均の時間が短くなる。

ただし、すべての場合において効率がいいわけではない。
→例）整列済みの配列での選択はO(1)など

木構造の実装(に必要な物)

講義スライドに則って下記のようなItemという構造体をデータとして持つようなノードを考えます。(＝記号表抽象データ型です。)

typedef struct{
    int key;
    char information[10];
} Item;

一つのノードが持つべき情報は以下の3つです。(ここでは使用している木構造が二分木であるものとします。)
・上記の構造体(データ本体)
・左の子へのブランチ
・右の子へのブランチ

ここで、ブランチをプログラム上で実現するためには次のノードへのポインタを用いればいいです。(矢印とはつまり次のノードの場所を指しているのです。)
これらのことから一つのノードもまた構造体で実装できることがわかります。

以下がノードを実現するための構造体です。

struct Node{
    Item item;
    Node* l;
    Node* r;
    int N;
};

Nは自分を根とした部分木の内部節点(子を持つノード)の個数です。必ずしも必要な値ではないですが、演算に使用することが多いので一緒に書いておくと便利です。

また、Node*のように書くのではなく、スライドのようにtypedefでNode*にlinkという名前を付けるのも楽になると思います。(以下説明なしにリンクという単語を用います。)

typedef struct Node* link;
struct Node{
    Item item;
    link l;
    link r;
    int N;
};

注意

ノードは構造体として作成しましたが、基本的に用いるのは構造体のポインタ、つまりリンクです。
これはなぜかというと、最初からリンクを用いることでそれぞれのブランチ先を指すときに代入しやすくなるためです。仮に次のノードを構造体で作っていた場合、一度その構造体の中身を指すポインタを別に作ってから代入する必要があります。

構造体そのものと違って直接代入して作成することが今はできませんが、次回その辺の関数についても書きたいと思います。今後あるノードを用いるときは基本的にリンクを使って作成していきます。

まとめ

今回は二分探索木のまとめに入るにあたって必要な知識をまとめました。とりあえず覚えておくべき知識としては、

木構造とは大雑把にどんなものなのか
木構造の実装に必要な物は何か
ノードはどのように表していくか

この辺だと思います。次回は二分探索木についてと、挿入・探索の実装までを書きます。

某大学の講義録

個人用備忘録です。間違いの可能性あり。