情報処理のWeb教科書―IPA情報処理試験対策のお供に!

木構造―種類のやさしい説明、多分木、b木、b+木、幅優先探索など

トップ 情報処理の知識体系 テクノロジ系 基礎理論 アルゴリズムとプログラミング アルゴリズムとデータ構造 データ構造の種類 木構造

木構造の種類についてまとめています。根、葉、枝などの用語のやさしい説明から、順序木、2分木、多分木、b木、b+木、バランス木などの考え方やイメージ、計算量、ヒープ、幅優先探索など、情報処理の過去問と合わせてまとめました。

▲記事トップへ

目次

この記事の目次です。

1. 木構造とは

2. 木構造に関する用語

3. 木構造の種類

4. 多分木

5. B木

6. B+木

7. ヒープ

8. 幅優先探索

木構造に関連したIPA情報処理試験の過去問題

もっと知識を広げるための参考

更新履歴

1. 木構造とは

木構造とは、グラフ理論という数学の1分野の木の構造をしたデータ構造のことを言います。 英語で「tree structure」とつづります。木構造のことを単に「木」と呼ぶこともあります。

2. 木構造に関する用語

木に関する用語を見ていきます。

3. 木構造の種類

子ノード数での分類した2分木と多分木、すべての葉について、深さがほぼ等しいバランス木、ヒープ、デジタル木など多数の分類方法があります。 以降の章で、順序木、2分木、多分木、b木、b+木、バランス木、ヒープなどの木構造の種類をまとめています。

4. 多分木

多分木とは、兄弟の数がn以上である順序木のことをいいます。

順序木

節にデータを格納するとき、一定の順序で格納してある木を順序木といいます。

2分木

葉以外の節が2つまたはそれ以下の子を持つような順序木を2分木といいます。

節が持つこの数で順序木の種類を分類するとき、この最大数をkとすると、2分木はk=2、一般的にk≧2の場合、多分木といいます。

5. B木

B木とは、木構造をもつデータ構造の1つで、多分木を基にしたバランス木です。 節を複数持つことができる木構造で、階層の深さが同じになるように、ノードの分割と併合を行います。

B木はバランス多分木ともいい、枝が複数ある木構造のうち、根からすべての葉の深さが同じで、枝が一方向に偏らないような 構造の木のことをいいます。

B木の条件

B木は、次のような制約を持ちます。

B木のイメージ

以下はB木のイメージです。 各節点に4個のキーを格納し、5本の枝を出し、根の深さがレベル2まであるB木になります。 このB木には、レベル0がキー4個、レベル1がキー20個、レベル2がキー100個、合計124個のキーが格納されています。

各節点に4個のキーを格納し、5本の枝を出し、根の深さがレベル2まであるB木
図 各節点に4個のキーを格納し、5本の枝を出し、根の深さがレベル2まであるB木

B木の応用例

B木は、階層型データベースなどで利用されるデータ構造です。

補足

バランス木について補足です。

バランス木

バランス木とは、節の追加や削除が発生するごとに、木構造全体を再調整する機能を持つ木です。 特定の部分木だけが伸びることを防ぐために、バランス木の各部分木は左と右の深さの情報を持っています。

6. B+木

B+木は、B木から派生したB木の変種でキーを指定することで挿入・検索・削除が効率的に行える木構造の一種です。

B+木インデックスを格納するノードへのアクセス回数のオーダ

B+木インデックスのが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオーダを表す式はlogXです。

1つの接点にm個の枝があるB+木があるとします。 根から順に範囲を狭めながら探索していきますが、B+木のバランスの取れた木ですので、深さが1つ深まると探索対象が1/mに減ることが見積れます。 最終的に探索範囲が1、つまり「X/mのt乗=1」となるまで探索するのが最悪の探索回数となります。

これをtの式に直すと、「t=logmX」となります。 オーダーで考える場合には、対数の底は考える必要ないのでlogXとなります。

7. ヒープ

データ構造やヒープ領域とは何かなど、ヒープをテーマに情報をまとめています。

詳細

8. 幅優先探索

木の節をなぞることを木の探索あるいは走査、巡回といいます。 なぞり方を大きく分類すると、幅優先探索と深さ優先探索に分けられます。 ここでは幅優先探索について見ていきます。

幅優先探索とは

幅優先探索とは、木構造の始点から近い順に1つずつ調べていく探索法のことを言います。

幅優先探索のなぞり方

幅優先探索のなぞり方は、木のレベル0から始めて、同じレベルの左から右になぞり、右端まで来たら下のレベルに移って、同じようになぞります。

木構造に関連したIPA情報処理試験の過去問題

以下では木構造に関連したIPA情報処理試験の過去問とその解説をまとめています。

もっと知識を広げるための参考

更新履歴

戻る

スポンサーリンク

情報処理の知識体系

各試験の問題と解説

ランダム出題・採点アプリ

プログラミング

スポンサーリンク