【応用情報技術者試験】木構造について 勉強日記 俺用メモ!

こんばんはきよです!

今回は木構造について勉強したことをメモしていきたいと思います。

■参考文献(アフィリエイトリンクです!良かったら購入してください!)

平成30年度【春期】【秋期】応用情報技術者 合格教本 (情報処理技術者試験)

かなり詳しく書かれているのでぜひ!

スポンサーリンク




■木構造とは

・データ(要素)同士の階層的な関係を表現するためのデータ構造

・最上位の階層を根(root)という

・要素のことを節(node)という、節は一つの親を持つ

・要素と要素を繋ぐ部分を枝(branch)という

・子の無い要素を葉(leaf)という

・節から出る枝が2本の木構造を2分木構造という

・節から出る枝がそれ以上の木構造を多分木構造という

■完全二分木

・葉以外の節が全て2つの子を持つ

・根から葉までの深さが全て等しい

・葉の個数は、根から葉までの深さを求めると出せる(深さ = H = 3の場合)

– 2^3 = 2 * 2 * 2 = 8

・葉以外の節の個数

– 2^H -1

■2分探索木

・親から出る2つの節(node)で大小の値を持たせる

・木の性質を用いて、データ探索ができる

・大小で比較していくので、半分ずつ絞られていく

1.走査(巡回法)

・幅優先探索

– 根から始まり、隣接する2つの節を順番に探索する

– 階層ごとにみていく感じ

– 左から右に見ていく

・深さ優先探索

– 根から始まり、子の無いノードまで探索する

– 到達後は一つずつ戻り未探索から再度探索する

左部分木は根より小さい

右部分木は根より大きい

– 先行順,中間順,後行順 の巡回方法がある

– 先行順 = 根→左部分木の左のノードを順に見る葉に到達したら右へ

– 中間順 = 左部分木の一番小さい葉から始まり大きいデータを見ていく(昇順)

– 後行順 = 左部分木の一番小さい葉から同じ階層のデータを見て右部分木を見ていく

2.節の挿入と削除

・挿入

– 根から順に探索し、辿る部分木がなくなったところに挿入する

・削除

– 削除対象が葉の場合は、そのまま削除

– 削除対象が1つの子しか持たない場合は、子と入れ替えて削除

– 削除対象が2つの子を持つ場合は、左部分木の最大値の節か、右部分木の最小値の節を入れ替える

■バランス木

・2分木は左右の大小を見ながら探索していく

・左右のバランスが取れた木は探索効率が良い

・根から葉まで左右のバランスが取れた木をバランス木(平衡木)という

・バランスを保つように再構成できる

■B木

・多分木構造(平衡木)

・OracleやPostgreSQLなどデータベースのindexの仕組みに使われている

・基本的な探索方法は、2分木と同じ

・1つの節に複数のキーを持てる

・節内では昇順で並んでいる

・子へのポインタを保持して、データを探索する

・左より小さい 左より大きく、右より小さい 右より大きい のように木構造になる

プログラムを書く身としては、大事な部分でした。

B木はもっと勉強が必要だなと感じました。

最後にまたアフィリエイトリンク貼らせてくださいorz

■参考文献(アフィリエイトリンクです!良かったら購入してください!)
平成30年度【春期】【秋期】応用情報技術者 合格教本 (情報処理技術者試験)

以上、よろしくお願いいたします。

スポンサーリンク




シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク




%d人のブロガーが「いいね」をつけました。