◆ ２分木、２分探索木
２分木とは、親ノードが子ノードを２つ以下持つ木構造の事です。
イメージ的には横の図です。
これで子ノードが２つ以上だと 多分木 または ｎ分木 と言われるようになります。
親の無いノードを root 子の無いノードを reaf（葉） と言います。
特に要素には、制約みたいなものがなく大小関係など関係なくデータを入れていくようです。
|
|
 |
２分探索木とは、２分木に制約が付いたものです。
各要素は「左の子 ＜ 親 ＜ 右の子」になっておかないといけません。
イメージ的には左の図です。
データの検索を目的にしている木構造で、
ルートから検索を開始し、検索対象の値が要素より大きければ右子ノードへ、
小さければ左子ノードへと検索を繰り返します。
|
◆ Ｂ木
Ｂ木とは、バランス木の略でデータの効率的な格納に用いられます。
２分探索木の発展型で、主にハードディスクやDBMSなど（ Oracle や PostgreSQL などでも）のファイルシステムに使用されています。
特徴的には、左右のノードが対象になるようにソートをし直すという特徴があります。
イメージ的には下の図です。（１つのノードに４つのデータが格納できるという例で）
オレンジの部分はポインタの格納領域で、子ノードのポインタアドレスが格納されます。
（出題される可能性あり）
ノード内は必ずソートされて格納されます。
更に追加すると下の様なイメージで再編成をします。
データが増えてくると、親ノードのデータも含めてどんどん再編成されていきます。
Ｂ木の目的は、子ノードのバランスを取るようにデータ配置を行う事によって、最大探索回数を最小に抑えると言う目的で作られています。
ノード数がｎの場合、ノードの高さが O(log2 N) になるのでノードの探索が速くなるという事です。
情報処理試験では、おそらく意味のみで出題されるかも知れません。
◆ ヒープ木
２分探索木と違って、親と子のノードが上下関係になります。
Ｂ木と違って、ポインタアドレスなどが不要で、「添字」というもの使用して配列による管理が可能な手法です。
これはアルゴリズムの問題も度々でるので、ソート処理の内容はアルゴリズムの方で記述しようと思います。
イメージ的には横の様な感じです。
ここで気をつけないといけないの事は、葉が必ず左の方から付くという事です。
要は図で言いますと「４」の要素の下に葉がなく、「６」の要素に葉があるという事はありません。
（アルゴリズム編でその辺りを記述しようと思います。）
|
|
|