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

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

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

calendar

reload

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

こんにちは😀

今回は、システムの構成で使用するツリー構造に関してまとめました。

階層構造を持つデータで広く使われ、データの探索や整列などの用途にも使われるデータ構造を、ツリー構造と言います。
ハードディスクなどの補助記憶装置のファイルシステムやインターネットのドメイン名などは、このツリー構造を用いて効率よく管理しています。

スポンサーリンク

2分木とは

ツリー構造を構成する各要素には以下のように名前が付いています。

根(ルート)

最上位の節点を指します。

枝(ブランチ)

各節点や葉を繋ぎます。

節(ノード)

根から枝によって繋がる部分です。
節点とも言います。

葉(リーフ)

末端の節点になります。

こうしたツリー構造のうち、節から伸びる枝が2本以下であるものを2分木(にぶんぎ)と言います。
節からぶら下がる部分を部分木と言い、左右それぞれを左部分木と右部分木と呼びます。

枝で直接繋がっているもの同士は、上にある節を「親」、下にある節を「子」と言ったりします。

完全2分木とは

葉以外の節が全て2つの子を持ち、根から葉までの深さが一様に等しい2分木を、完全2分木と言います。

完全2分木の持つ葉の数は、2分木の階層の深さから算出することができます。

葉の数=2^深さ

また、葉を除く節の数は、次の式で求めることができます。

節の数=2^深さ-1

2分探索木とは

親に対する左部分木と右部分木の関係が、「左の子<親<右の子」となる2分木を、2分探索木と言います。

このツリー構造には以下の特性があります。

・親の左側にある節は全て親よりも小さなデータになります。
・親の右側にある節は全て親よりも大きなデータになります。

この特性により、2分探索木ではデータの探索を容易に行うことができます。

探索対象データを節の中身と比較して、探索対象の方が小さければ左へ、大きければ右へ移動します。
これを節ごとに繰り返すことで目的のデータにたどり着きます。

2分探索木に節点を追加する場合、以下の手順を行います。

①追加要素と節点を根から比較します。
②追加要素が小さければ左へ、大きければ右へ降ります。
③上記までを繰り返し、比較する先がなければそこへ追加します。

また、節点の削除は以下のやり方で行います。

ケース1:末端の葉を削除する場合

葉を削除します。

ケース2:1つしか子を持たない節点を削除する場合

対象の節点を削除した後、その位置に子である節点を移動させます。

ケース3:2つの子を持つ節点を削除する場合

対象の節点を削除した後、右部分木の中の最小の要素(もしくは左部分木の中の最大の要素)を、その位置に移動させます。

今回の一言・・・

このようなツリー構造は、ファイルの構造だけでなくプログラムのソースのフォルダ構成にも使用されます。
検索などのほしいデータを探す場合に参考になる考え方になります。

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

IT入門一覧はこちら】

この記事をシェアする

コメント

コメントはありません。

down コメントを残す