【キュー】
　　　キューとは、窓口（例えば銀行等のキャッシュディスペンサー）をイメージしてもらえればいい。
　　　次の図のように表すことができる。

　　　　　　　　　─────
　　　　　　入口　　　　　　　出口
　　　　　　　　　─────

　　　これに１，３，５，７の順に数字を格納していくと、キューの中は次のように変化していく。

　　　　　────　────　─────　───────　─────────
　　　　　　（空）→　　１　→　３　１　→　５　３　１　→　８　５　３　１
　　　　　────　────　─────　───────　─────────

　　　次に、データを取り出すと、入れた順に取り出される。
　　　これをＦＩＦＯ（Last-In First-Out　先入れ先出し）という。

　　　　　───────
　　　　　　８　５　３　　→　１が取り出される
　　　　　───────
　　　　　───────
　　　　　　８　５　　　　→　３が取り出される
　　　　　───────
　　　　　───────
　　　　　　８　　　　　　→　５が取り出される
　　　　　───────


　　　このようにＦＩＦＯの処理に適しているのは、キューである。


【スタック】
　　　再帰的な手続きを実行するとき、必要なデータを記憶しておくのに最も適切なデータ構造である。
　　　スタックにデータＡ，Ｂ，Ｃ，Ｄをこの順に格納した後、スタックから連続して取り出すときの
　　　動作を次の図に示す。

　　　　　　Ｐｕｓｈ　Ａ　　Ｐｕｓｈ　Ｂ　　Ｐｕｓｈ　Ｃ　　Ｐｕｓｈ　Ｄ
　　　　　━┯━━━┯━　━┯━━━┯━　━┯━━━┯━　━┯━━━┯━
　　　　　　│　Ａ　│　→　│　Ｂ　│　→　│　Ｃ　│　→　│　Ｄ　│
　　　　　　└───┘　　　├───┤　　　├───┤　　　├───┤
　　　　　　　　　　　　　　│　Ａ　│　　　│　Ｂ　│　　　│　Ｃ　│
　　　　　　　　　　　　　　└───┘　　　├───┤　　　├───┤
　　　　　　　　　　　　　　　　　　　　　　│　Ａ　│　　　│　Ｂ　│
　　　　　　　　　　　　　　　　　　　　　　└───┘　　　├───┤
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│　Ａ　│
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　└───┘

　　　　　　　　　Ｐｏｐ　　　　　　　Ｐｏｐ　　　　　　　Ｐｏｐ
　　　　　（Ｄが取り出される）（Ｃが取り出される）（Ｂが取り出される）
　　　　　　━━┯━━━┯━━　━━┯━━━┯━━　━━┯━━━┯━━
　　　　　→　　│　Ｃ　│　　→　　│　Ｂ　│　　→　　│　Ａ　│
　　　　　　　　├───┤　　　　　├───┤　　　　　└───┘
　　　　　　　　│　Ｂ　│　　　　　│　Ａ　│
　　　　　　　　├───┤　　　　　└───┘
　　　　　　　　│　Ａ　│
　　　　　　　　└───┘

　　　このような動きをＬＩＦＯ（Last-In First-Out　後入れ先出し）といい、これに適しているのが
　　　スタックである。


【２分探索木】
　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　│ａ│
　　　　　　　　　　　　└┬┘
　　　　　　　　　┌───┴───┐
　　　　　　　　┌┴┐　　　　　┌┴┐
　　　　　　　　│　│　　　　　│　│
　　　　　　　　└┬┘　　　　　└┬┘
　　　　　　　左部分木　　　　　右部分木

　　　　２分探索木では、どの要素をとっても次の式が成立つ。

　　　　（左部分木の要素の最大値）＜ａ＜（右部分木の要素の最小値）

　　　例）
　　　　ａが６の場合
　　　　　　　左部分木の要素の最大値＝５
　　　　　　　右部分木の要素の最小値＝７　になる

　　　例）
　　　　ａが１２場合
　　　　　　　左部分木の要素の最大値＝１１
　　　　　　　右部分木の要素の最小値＝１　になる



　　　　　　　　　　　　　　(17)
　　　　　　　　　　　　　／　　＼
　　　　　　　　　　　　／　　　　＼
　　　　　　　　　　(15)　　　　　　(19)
　　　　　　　　　／　＼　　　　　　／　＼
　　　　　　　　／　　　＼　　　　／　　　＼
　　　　　　　(14)　　　(16)　　(18)　　　(20)



【完全２分木】
　　　　　　　　　　　　　○
　　　　　　　　　　┌──┴──┐
　　　　　　　　　　○　　　　　○
　　　　　　　　┌─┴─┐　┌─┴─┐
　　　　　　　　○　　　○　○　　　○　ｋ＝３

　　　完全２分木は、上図のように全ての節点（○で表している）が最下層を除いて
　　　全て２つの節点を下に持っているような「木」である。
　　　第ｋ層めの節点の数は　２＾（ｋ−１）　で表される。
　　　第１層〜第ｋ層までの節点の数の合計は
　　　　　　　　　　１＋２＋４＋８＋・・・＋２＾（ｋ−１）
　　　で表される。これは等比級数の和になるため
　　　（２＾（（ｋ−１）＋１）−１）／（２−１）＝２＾ｋ−１となる。

　　　例）
　　　　次の２分木で表される算術式はどのようになるか。

　　　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　　　｜−｜
　　　　　　　　　　　　　　└┬┘
　　　　　　　　　┌─────┴─────┐
　　　　　　　　┌┴┐　　　　　　　　　┌┴┐
　　　　　　　　｜＋｜　　　　　　　　　｜÷｜
　　　　　　　　└┬┘　　　　　　　　　└┬┘
　　　　　　　┌─┴─┐　　　　　　　┌─┴─┐
　　　　　　┌┴┐　┌┴┐　　　　　┌┴┐　┌┴┐
　　　　　　｜Ａ｜　｜×｜　　　　　｜＋｜　｜Ｆ｜
　　　　　　└─┘　└┬┘　　　　　└┬┘　└─┘
　　　　　　　　　┌─┴─┐　　　┌─┴─┐
　　　　　　　　┌┴┐　┌┴┐　┌┴┐　┌┴┐
　　　　　　　　｜Ｂ｜　｜Ｃ｜　｜Ｄ｜　｜Ｅ｜
　　　　　　　　└─┘　└─┘　└─┘　└─┘　

　　　　　　　　順に式を組み立てていくと
　　　　（１）　ＢとＣと×から　　　　　Ｂ×Ｃ
　　　　（２）　Ａと（１）と＋から　　　Ａ＋Ｂ×Ｃ
　　　　（３）　ＤとＥと＋から　　　　　Ｄ＋Ｅ
　　　　（４）　（３）とＦと÷から　　　（Ｄ＋Ｅ）÷Ｆ
　　　　（５）　（２）と（４）と−から　Ａ＋Ｂ×Ｃ−（Ｄ＋Ｅ）÷Ｆ
　　　　　　　　となる。



【Ｂ木 (バランス：BALANCE)】
　　　探索木の一種で分かれていった木の構造の深さなどがほぼ同じで、挿入や削除を
　　　してもそれぞれの木のバランスを調整できる。　
　　　２分木に比較すると、ひとつの頂点から出る枝が多いので、データ量が多く
　　　なっても階層がさほど深くならない、平衡（バランス）をとりやすいという
　　　特徴がある。

　　　さらにＢ木は次のような特徴がある。
　　　　・索引順編成のように、あふれ領域を使用する必要がない。動的な索引保守を
　　　　　行う。
　　　　・ページ使用率は50％以上あり、格納効率が良い。索引順編成のように偏在
　　　　　することがない。
　　　　・直接アクセスには向いているが、順次アクセスの効率はよくない。

　　　Ｂ木を用いてデータを格納するとき、階層の深さが同じになるように
　　　ノードの分割・併合を行う。

　　　Ｂ木を用いたデータの格納は、階層型データベースなどで使用される。


　　　　　　　　　　　　　　　　　　　○
　　　　　　　　　　　　　　　　　　／　＼
　　　　　　　　　　　　　　　　　／　　　＼
　　　　　　　　　　　　　　　　／　　　　　＼
　　　　　　　　　　　　　　　／　　　　　　　＼
　　　　　　　　　　　　　　／　　　　　　　　　＼
　　　　　　　　　　　　　○　　　　　　　　　　　○
　　　　　　　　　　　　／　＼　　　　　　　　　／　＼
　　　　　　　　　　　／　　　＼　　　　　　　／　　　＼
　　　　　　　　　　○　　　　　○　　　　　○　　　　　○
　　　　　　　　　／　＼　　　／　＼　　　／　＼　　　／　＼
　　　　　　　　○　　　○　○　　　○　○　　　○　○　　　○

　　　データの追加などにより階層の深さに差が出てきたときには、ノードを分割
　　　したり併合したりして、各ノード（○）の下に２つのノードが来るようにしな
　　　がら深さを揃えるようにする。


　　　例）
　　　　図の各接点の値には，Ａ４＜Ａ２＜Ａ６＜Ａ５＜Ａ７＜Ａ１＜Ａ３の大小関係が成り立っている。
　　　　この関係を持つ木を２分探索木という。
　　　　　　　　　　　　　　　　　┌───┐
　　　　　　　　　　　　　　　　　│　Ａ１│
　　　　　　　　　　　　　　　　　└─┬─┘
　　　　　　　　　　　　　┌─────┴─────┐
　　　　　　　　　　　┌─┴─┐　　　　　　　┌─┴─┐
　　　　　　　　　　　│　Ａ２│　　　　　　　│　Ａ３│
　　　　　　　　　　　└─┬─┘　　　　　　　└───┘
　　　　　　　┌─────┴─────┐
　　　　　┌─┴─┐　　　　　　　┌─┴─┐
　　　　　│　Ａ４│　　　　　　　│　Ａ５│
　　　　　└───┘　　　　　　　└─┬─┘
　　　　　　　　　　　　　┌─────┴─────┐
　　　　　　　　　　　┌─┴─┐　　　　　　　┌─┴─┐
　　　　　　　　　　　│　Ａ６│　　　　　　　│　Ａ７│
　　　　　　　　　　　└───┘　　　　　　　└───┘