ハジカラ 〜はじめからでも、プログラミング勉強〜

入門向けに、IT関連(javaやKotlin)をコツコツ書いたり検証したりします。

Home » IT入門 » 【IT入門】ツリー構造に関して②

【IT入門】ツリー構造に関して②

calendar

reload

【IT入門】ツリー構造に関して②

こんにちは😀

今回は、前回の続きでツリー構造をまとめます。
前回は主に2分木をみてみました。

今回は2分木を元にした他のツリー構造もみてみましょう。

スポンサーリンク

ヒープとは

「親要素が子要素の値以上である」もしくは「子要素が親要素の値以上である」という関係にある2分木を、ヒープと言います。
半順序木とも呼ばれます。

AVL木とは

どの節においても左部分木と右部分木の高さの差が1以下という関係にある2分木を、AVL木と言います。
2分探索木の一種になります。
Adelson-Velskii and Landis’の略だそうです。

左右にバランスがとれているため、探索候補をほぼ半分づつに絞り込んで行けます。
そのため、探索候補の絞り込みに無駄がなく、計算量を抑制することができます。

AVL木では、節の挿入や削除によって左部分木と右部分木のバランスが崩れる時は、条件を満たすように木の再編成を行います。

2分木の走査順序とは

2分木に含まれるデータを対象として探索を行う場合、その木構造を辿り節点をもれなく巡回する必要が出てきます。
このように、順に対象を調べていくことを走査と言います。

深さ優先順

根から始まり、子があれば子を優先して走査する方法になります。
葉に行き着く1つ上の節点に戻り他方の子を辿ります。

幅優先順

上の階層から順に、左→右と階層内の節点を走査する方法になります。
階層内の節点を走査し終わらせると、下の階層へと移ります。

深さ優先順の場合、走査した節点の値をどのタイミングで取り出すかについては、さらに以下の3つのパターンに分かれます。

先行順(行きがけ順)

節点→左部分木→右部分木の順に値を取り出すパターンになります。
各節点の値を初めて通りがかったタイミングで取り出すことになります。

中間順(通りがけ順)

左部分木→節点→右部分木の順に値を取り出すパターンになります。
左部分木を掘り下げ終わり、右部分木に移るタイミングで節点の値を取り出す動きをします。

後行順(帰りがけ順)

左部分木→右部分木→節点の順に値を取り出すパターンになります。
子を掘り下げ終わって、親に戻るタイミングで節点の値を取り出す動きになります。

今回の一言・・・

前回は二分木をみましたが、それを元に様々なツリー構造があることがわかりました。
システムやプログラムの仕組みを把握する上でも、このあたりの理解も深めていきます。

ここまで読んでくれてありがとう。
では、また次回。

IT入門一覧はこちら】

この記事をシェアする

コメント

コメントはありません。

down コメントを残す