2-1-2ツリー構造

• ツリー構造

　ツリー構造は、データ間の関係を階層的に表現したデータ構造です。この階層関係を図示すると、あたかも木が枝分かれしているように見えることから、ツリー構造といいます。このようなデータ構造は、オペレーティングシステムにおける階層ディレクトリで使われています。
　データの構造は、ここのデータを示す○の部分をノード(節)、もっとも上位のレベルにある唯一のノードはルート(根)といいます。また、あるノードとそのすぐ下のノードとは親子関係で表します。

• 2分木

　ノードからブランチの数が2本以下、つまり最大でも2つの子しか持たないツリー構造を2分木といいます。中でもルートからすべてのリーフまでの経路の長さ(階層)が等しい2分木を完全2分木といいます。
　2分木のデータ構造は、左のポインタ部、データ部、右のポインタ部によって構成されています。左のポインタ部は左の子のデータ位置を示し、右のポインタ部は右の子のデータ位置を示します。

• 2分探索木

　2分探索木は、2分木の各ノードに要素(データ)を持たせたもので、
①親のデータより小さいデータは左の子にあり、
②親のデータより大きいデータは右の子にある、
という関係が成り立ったものをいいます。2分探索木を用いるとデータ検索を容易に行うことが出来ます。

• AVL木

　AVL木は、1962年にAdel'sonVerl'skiiとLandisが考案したことから、考案者の頭文字を取って、AVL木と呼ばれています。
　AVL木は、どのノードにおいても、その左右の部分木のレベルの差が1以下という条件を満たす2分検索木をいいます。探索効率は悪くありませんが、現在では次に解説するB木の方が実用的に使われています。

• B木

　B木は、探索効率が良く、実用価値が非常に高いデータ構造で、外部記憶装置における探索に適しています。
　AVL木は2分木をベースにしていましたが、B木はm分木をベースにしたものです。m分木とは、ノードが最大m個(m≧2)の子を持つことが出来るツリー構造で、多分木ともいいます。また、この探索木を多分探索木と呼びます。
①ルートはリーフであるか、あるいは2～m個のこを持つ。
②ルート、リーフ以外のノードは、m/2個(小数点切り上げ)を持つ
③ルートからすべてのリーフまでの深さがすべて等しい。
という3つの条件を満たすm分木をm階のB木といいます。
　2分探索木では、すべてのノードにデータを持っていましたが、B木ではデータを持つのはリーフのみで、リーフ以外のノードはキーだけを持つデータ構造になっています。