データの二分木への格納法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/22 07:52 UTC 版)
二分木はプログラミング言語の基本的な要素を用いて構築することができる。データ型としてレコード型とポインタ型（参照型）をもったプログラミング言語では、典型的な方法では、何らかのデータと左右の子へのポインタからなるノードを組み合わせて木を構成する。場合によっては親へのポインタを用意することもある。参照する相手がない（左右どちらかあるいは両方の子がない）場合は、「何も参照していない」ことを示す特別な値 nil（nullのこと） にしておくか、事前に決めたあるノード（番兵と呼ぶ）を指すようにする。親への参照付きのデータ構築例をPascalによって示す。 type pNode = ^Node; {ノード型へのポインタ} Node = record data : (* 必要なデータをためる部分 *) left, parent, right : pNode {左の子、親、右の子へのポインタ} end;...var root, newnode : pNode;...begin new(root); root^.parent := nil; {根を植える。根には親がいない} new(newnode); {新しいノードをつくる} with newnode^ do begin left := nil; right := nil; {子はいない} parent := root {rootが親} end; root^.left := newnode; {左側の子に} new(newnode); {新しいノードをつくる} with newnode^ do begin left := nil; right := nil; {子はいない} parent := root {rootが親} end; root^.right := newnode {右側の子に}... 明示的な方法ではないが、配列に二分木を格納する方法もある。完全二分木ならば、この方法でもスペースを無駄にすることはない。根の添字を0とすると、この場合、添字 i のノードの子は添字 2i + 1 と 2i + 2 に格納され、そのノード自体の親は（あれば）添字 floor((i-1)/2) にある。配列を用いると記憶容量の節約になり、行きがけ順（先行順、preorder traversal）でデータを舐める場合特に参照の局所性が向上する。しかし、連続したメモリ空間を必要とし、木が大きくなる際に大きな処理時間を必要とする。また n 個のノードを持つ高さ h の木に対し、2h - n に比例したメモリを消費する。 MLのようなタグ付き共有体を備えた言語では、しばしばタグ付き共有体として二分木は構築される。それには二種類のノードが用いられ、一つはデータ、左の子、右の子を持った3-tupleのノードで、もう一つはデータも関数ももたない「葉」である（上記PascalやCのようなポインタ型をもった言語の nil に当たる）
※この「データの二分木への格納法」の解説は、「二分木」の解説の一部です。
「データの二分木への格納法」を含む「二分木」の記事については、「二分木」の概要を参照ください。
- データの二分木への格納法のページへのリンク
