木構造

キーワード

木構造、２分木、２分探索木、ヒープ

木構造

木構造（ツリー構造）とは、データの階層構造の一つで、図のように木を逆にしたように形式になります。根、節、葉には、データが対応しています。

２分木

特に、節から出る枝が２本の場合（データの関係によっては、★印のように枝が１本の場合もあります）を２分木（バイナリツリー）といいます。

２分探索木

さらに、データのキー項目の大小により並べておき、探索を容易にした構造を、２分探索木といいます。この場合、
　　　左の子＜親＜右の子
となるようにします（なお、データの特徴や探索の用途によっては、これとは異なる規則にする場合もあります）。

２分探索木の更新

上図において、「左の子＜親＜右の子」の規則に従いながら、データの挿入や削除を行うことを考えます。

値が１５のデータを挿入
①の２０と比較すると小さいので、②と比較します。②よりも大なので「右の子」になります。下左図になります。
④（１２）を削除
単に④を外して、②から⑧と⑨をつないだのでは、②（１５）＜⑨（１４）になってしまい、規則に反します。下中図のようにする必要があります。
さらに、②と⑨を入れ替えて下右図にするのは、単なる更新ではなく再編成であると考えるのが妥当でしょう。

２分探索木による探索回数

更新以前の図で、Ｘ＝１４のデータを探索する場合は、次のようになります。

ルート①と比較する。Ｘ＜①なので、左の子②へ
Ｘ＜②なので、左の子④へ
Ｘ＞④なので、右の子⑨へ
Ｘ＝⑨なので、検索終了

Ｘ＝１６（存在しない）の場合

ルート①と比較する。Ｘ＜①なので、左の子②へ
Ｘ＜②なので、右の子へ行きたいのだが存在しないので、検索終了

このように、最大４回（すなわち階層の深さ）の比較で検索することができます。
（なお、ここではルートから探索していますが、最も階層の深い節からスタートしたり、最も離れた節からスタートするなど、多様な探索方法があります）

２分探索木とリスト構造

木構造を、そのままファイルに実装することはできません。図のように、左側の子、右側の子のデータが格納されているポインタを持つリスト構造にして、表のような配列にして格納します。

　格納　　　左の子への　自分の　右の子への
ポインタ　　ポインタ　　キー値　ポインタ
　　１　　　　　２　　　　２０　　　３
　　２　　　　　４　　　　１５　　　０
　　３　　　　　５　　　　２８　　　６
　　４　　　　　７　　　　１２　　　８
　　５　　　　　０　　　　２４　　　０
　　６　　　　　０　　　　３０　　　０
　　７　　　　　０　　　　１０　　　０
　　８　　　　　０　　　　１４　　　０

完全２分木

例えば、７０→６０→５０→４０→３０→３０→２０→１０→５５→５２→５７→７５の順序でデータが出現し、そのまま２分木にすると、右の「不適切な構造」のようになります。これではＸ＝１０を探すには、７回の比較が必要になります。それに対して「理想的な構造」にすれば４回の比較ですみます。探索を最適にするには、根から各葉までの高さができるだけ等しくすることが求められます。
そのような２分木を完全２分木といいます。完全２分木の場合、節の個数Ｎと階層Ｍの間には、
　　　Ｎ＝１＋２＋２²＋ … ＋２^M＝２^Ｍ＋１
　　　Ｍ＝log₂（Ｎ＋１)－１
の関係があります。すなわち、探索に要する計算量のオーダーは、Ｏ(logＮ) になります。挿入や削除に要する計算量も同じです。
　完全２分木にするには、木構造を作成するときに、データの全体を小さい順に並べて、
　　　全体の中央値をルートにする
　　　左側半分のうちの中央値を左の子にする
　　　右側半分のうちの中央値を右の子にする
ことを繰り返すことにより作成できます。
　しかし、その後、追加や削除を繰り返すうちに、次第に「理想的な」状態からずれたものになってしまいます。それで、処理効率を改善するために、必要に応じて木構造を再編成することがあります。

ヒープ

完全２分木を配列で表現するデータ構造をヒープといいます。ヒープを用いた探索のことをヒープ探索、ソートのことをヒープソートといいます。ヒープ探索の計算量はＯ(logＮ) 、ヒープソートの計算量はＯ(Ｎ logＮ) になります。

演算木

数式を２分木で表現することができます。それを演算木といいます。一般の数式表現を２分木で表現して、逆ポーランド記法にすることができます。
　例えば、数式Ａ＋Ｂ×（Ｃ＋Ｄ）＋Ｅは、演算の優先順位を（　）で明示すれば、
　　　（（Ａ＋（Ｂ×（Ｃ＋Ｄ）））＋Ｅ）
になります。
　最も深い（　）を、演算子を親の節、被演算数値を左の葉、演算数値を右の葉とする部分木にします。それを組み合わせると演算木ができます。そして、この演算木を葉のほうから後行順に表記すると、

　　　（（Ａ＋（Ｂ×（Ｃ＋Ｄ）））＋Ｅ）
　　　　　　　　　　└─①─┘
　　　　　　　　　　　ＣＤ＋
　　　　　　　└───②───┘
　　　　　　　　　　ＢＣＤ＋×
　　　　└─────③─────┘
　　　　　　　　　ＡＢＣＤ＋×＋
　　　└─────④─────────┘
　　　　　　　　　ＡＢＣＤ＋×＋Ｅ＋
となり、逆ポーランド記法の
　　　ＡＢＣＤ＋×＋Ｅ＋
になります。

Ｂ木、Ｂ＋木

木構造を発展させたデータ構造にＢ木やＢ＋木があります。これらは、データベースに広く用いられていますが、ここでは省略します。