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

こんにちは😀

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

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

2分木とは

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

根（ルート）

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

枝（ブランチ）

各節点や葉を繋ぎます。

節（ノード）

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

葉（リーフ）

末端の節点になります。

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

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

完全２分木とは

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

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

葉の数＝2^深さ

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

節の数＝2^深さ-1

２分探索木とは

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

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

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

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

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

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

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

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

ケース１：末端の葉を削除する場合

葉を削除します。

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

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

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

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

今回の一言・・・

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

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

【IT入門一覧はこちら】