木構造

木構造（きこうぞう、tree structure）とは

  • 木構造とは、データ構造の一つで、一つの要素（ノード）が複数の子要素を持ち、一つの子要素が複数の孫要素を持ち、という形で階層が深くなるほど枝分かれしていく構造のこと。
  • 木が幹から枝、枝から葉に分岐していく様子に似ているためこのように呼ばれる。
  • ツリー構造ともいう。

データ構造の最小単位の名称

様々な呼び方がある（データ構造のモデルにより呼び方が異なる）

  • 要素
  • セル　・・・　リスト
  • ノード　・・・　木構造

木構造の構成要素

  • 節（ノード）：各要素（データ）。根でも葉でもないノードは節点という。
  • 根（ルート）：最上位のノード。木構造に一つだけ存在する。
  • 葉（リーフ）：最下位のノード。
  • 枝（ブランチ）：各ノードを関係づける線

親ノード、子ノード

ノードには親ノードと子ノードがある

２分木：子ノードの数を2個以下に限定した木構造

多分木：子ノードの数が3個以上の木構造

２分木

２分木には、さらに全２分木と完全２分木がある。

  • 全２分木：子ノードの数が必ず2個の２分木
  • 完全２分木：根から葉までの全ての深さが同じ、または1つしか違わない2分木

左部分木　右部分木

あるノードから見て左側の下階層を左部分木、右側の下階層を右部分木という

木構造　ポインタを使って表現

木構造はポインタを使ってリストのように表現することができる

走査（トラバース　traverse）　木の巡回法

  • 走査とは、木構造からノード値を取り出していく方法
  • 幅優先探索と深さ優先探索がある

幅優先探索

根から順に、同一レベルの左から右にノード値を取り出していく

深さ優先探索

探査はルートから次のように一筆書きで行う

  • 葉以外のノードは、3回通過する。どのタイミングでデータを取り出すかで、前順（先行順）、間順（中間順）、後順（後行順）がある
例

上図でノードBを取り出すタイミングが

A　B　C　前順（先行順）

A　C　B　間順（中間順）

A　C　D　B　後順（後行順）

例題1

図に示す２分木に対して走査を行い、節の値を出力する。前順、間順、後順、それぞれの方法の出力結果を書きなさい。

例題1　解答

前順　A⇒B⇒C⇒D⇒E

間順  C⇒B⇒D⇒A⇒E

後順  C⇒D⇒B⇒E⇒A

２分探索木（binary search tree）

  • ２分探索木とは「左部分木の値 ≦ 親ノードの値 ≦ 右部分木の値」という制約を持つ２分木
  • 要素の挿入・削除・検索を高速に行うことの出来る
  • 探索木とは、データを探索するための構造を持った木構造のこと

例題２

「5」を探索する場合、探索の進む経路の値を下記に書きなさい。

例題２　解答

10　→　７　→　４　→　５

例題２－２

「13」を探索する場合、探索の進む経路の値を書きなさい。

例題２－２　解答

10　→　15　→　11　→　13

２分探索木　登録（追加）

①登録（追加）する位置の探索をルートから始める。探索が不能になるまで探索を続ける。

②不能となった位置の末尾にデータを登録（追加）する。

例題3

例題3　解答

「8」を探索する　10　→　7　→　9　→　探索不能

「9」の末尾に「8」を登録する

２分探索木　削除

削除には３つのパターンがある

①子を1つも持たない場合

②子を1つだけ持っている場合

③子を2つ持っている場合

そのため、3つのパターンで処理を分ける。

①子を1つも持たない場合→そのノードを取り去る→該当する親のポインタをNULLにする

②子を1つだけ持っている場合 → 削除するノードに、そのノードが持っていた子を持ってくる

③子を2つ持っている場合 → 削除するノードを右部分木の最小の要素で置き換える

例題4

設問1　値「9」を削除するとどうなるか、変更点を図で書きなさい。

設問2　値「11」を削除するとどうなるか、変更点を図で書きなさい。

設問3　値「15」を削除するとどうなるか、変更点を図で書きなさい。

ヒープ(Heap)

■ヒープ(Heap)とは

  • 完全２分木の中で、どの親子をとっても親＜子(または親＞子)となっている
  • 子どうしの要素についての大小関係は問わない
  • ルートが最大または最小の値となる

ヒープ　検索

二分探索木のように「左の子＜親＜右の子」という関係がないので、データの検索はすべての要素を順次探索する。

ヒープ　登録（追加）

例題5

次のヒープに「７」を登録（追加）するとどうなるか？

①まず、最下段に左詰めで葉を追加する。

②ヒープ条件（親≦子）を満たすように葉から根に向けて値を交換する。

ヒープ　削除

例題6

次のヒープから「10」を削除するとどうなるか？

①削除したデータの位置に最後尾(末尾)のデータを持ってくる

②親＜子」の関係になるように、適正な位置まで順次、子と交換する

ヒープソート

  • ソートのアルゴリズムの一つ
  • データをヒープ構造にし、完成したらデータの先頭の値を取り出す。そしてまたヒープ構造を作り・・・という繰り返しでソートする手法

例題7

ヒープソートにより昇順にソートする。空欄を埋めなさい。

解答

平衡木（バランスツリー、B木）

葉の深さがなるべく等しくなるように構築された木を「平衡木」（バランスツリー、B木）と呼ぶ。

ＡＶＬ木（平衡２分木）

  • ２分探索木で要素の挿入・削除を行った後に、木の平衡が崩れた場合には再編成を行う
  • 各ノードにおいても、左右の部分木の高さが１以内の２分木に再編成する
  • ３人の考案者(Adelson-Velskii-Landis)の頭文字からＡＶＬ木と呼ばれる
  • 再編成は、ノードへのアクセス効率が低下しないように行う

※AVL木は、２分探索木のアクセス効率を低下しないように工夫した構造

 

まとめ　木構造の分類

■ノードの持つ子の個数での分類

  • ２分木
  • 多分木

※特に２分木（binary tree）がよく使われる

■ノード間に順序がある木構造・・・順序木（ordered tree）

  • ２分探索木 binary search tree
  • ヒープ・・・半順序木ともよぶ

■再編成を行う木構造・・・バランス木（平衡木）

  • ＡＶＬ木（平衡２分木）
  • Ｂ木

確認問題

１．木構造の構成要素の名称を埋めなさい。

２．ノードには（　a　）と（　ｂ　）がある。

３．子ノードの数を2個以下に限定した2分木を（　a　）、根から葉までの全ての深さが同じ、または1つしか違わない2分木を（　ｂ　）という。

４．あるノードから見て左側の下階層を（　a　）、右側の下階層を（　ｂ　）という。

５．走査（トラバース）には、（　a　）と（　ｂ　）がある。

６．幅優先探索は、（　a　）から順に、同一レベルの（　ｂ　）から（　ｃ　）にノード値を取り出していく。

７．深さ優先探索では、葉以外のノードは、3回通過する。どのタイミングでデータを取り出すかで、（　a　）、（　ｂ　）、（　ｃ　）がある。

８．２分木で「左部分木の値 ≦ 親ノードの値 ≦ 右部分木の値」という制約を持つ構造を、（　a　）という。

９．２分探索木は、要素の挿入・削除・検索を（　a　）に行うことの出来る。

１０．データを探索するための構造を持った木構造のことを（　a　）という。

１１．完全２分木の中で、どの親子をとっても親＜子(または親＞子)となっており、子どうしの要素についての大小関係は問わない構造を、（　a　）という。

１２．ヒープでは、ルートが（　a　）の値となる。

１３．データをヒープ構造にし、完成したらデータの先頭の値を取り出す。そしてまたヒープ構造を作り・・・という繰り返しでソートする手法を（　a　）という。

１４．葉の深さがなるべく等しくなるように構築された木を（　a　）と呼ぶ。

１５．二分探索木で、各ノードにおいても、左右の部分木の高さが１以内の２分木に再編成する構造を（　a　）という。

基本情報対策問題

１．２分木の走査の方法には、その順序によって次の三つがある。

(１)　前順：　節点、左部分木、右部分木の順に走査する。

(２)　間順：　左部分木、節点、右部分木の順に走査する。

(３)　後順：　左部分木、右部分木、節点の順に走査する。

図に示す２分木に対して走査を行い、節の値を出力する。前順、間順、後順、それぞれの方法の出力結果を書きなさい。（平成15年度・秋期　午前　改題）

２．節点1、2、…、n をもつ木を表現するために、大きさn の整数型配列A[1]、A[2]、…、A[n ]を用意して、節i の親の番号をA[i ]に格納する。節点k が根の場合はA[k]＝0とする。表に示す配列が表す木の葉の数は、幾つか。（平成22年度・秋期　午前）

ア　1        イ　3        ウ　5        エ　7

３．２分木の各ノードがもつ記号を出力する再帰的なプログラムProc(ノードn )は、次のように定義される。このプログラムを、図の２分木の根（最上位のノード）に適用したときの出力はどれか。（平成19年度・秋期　午前）

Proc(ノードn) {

n に左の子l があればProc(l )を呼び出す

n に右の子r があればProc(r )を呼び出す

n に書かれた記号を出力する

}

ア　b－c＊d＋a         イ　＋a＊－bcd

ウ　a＋b－c＊d　　エ　abc－d＊＋

４．すべての葉が同じ深さをもち、葉以外のすべての節点が二つの子をもつ２分木に関して、節点数と深さの関係を表す式はどれか。ここで、n は節点数、k は根から葉までの深さを表す。例に示す２分木の深さk は2である。（平成17年度・秋期　午前）

ア　n ＝ k (k ＋1)＋1　　　イ　n ＝ 2k＋3

ウ　n ＝ 2k＋1－1     　　　エ　n ＝ (k －1)(k ＋1)＋4

５．次の２分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで２分探索木を再構成するには、削除された節点の位置にどの要素を移動すればよいか。（平成25年度・春期　午前）

ア　9        イ　10      ウ　13      エ　14

６．次の２分探索木に12を追加したとき、追加された節12の位置を正しく表している図はどれか。（平成19年度・春期　午前）

７．2分探索木として適切なものはどれか。ここで、1～9の数字は、各ノード（節）の値を表す。（平成17年度・春期　午前）

８．ヒープソートの説明として，適切なものはどれか。

ア．ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。

イ．中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様な処理を繰り返す。

ウ．隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。

エ．未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。