こんにちは😀
今回は、システムの構成で使用するツリー構造に関してまとめました。
階層構造を持つデータで広く使われ、データの探索や整列などの用途にも使われるデータ構造を、ツリー構造と言います。
ハードディスクなどの補助記憶装置のファイルシステムやインターネットのドメイン名などは、このツリー構造を用いて効率よく管理しています。
2分木とは
ツリー構造を構成する各要素には以下のように名前が付いています。
根（ルート）
最上位の節点を指します。
枝（ブランチ）
各節点や葉を繋ぎます。
節（ノード）
根から枝によって繋がる部分です。
節点とも言います。
葉（リーフ）
末端の節点になります。
こうしたツリー構造のうち、節から伸びる枝が２本以下であるものを２分木（にぶんぎ）と言います。
節からぶら下がる部分を部分木と言い、左右それぞれを左部分木と右部分木と呼びます。
枝で直接繋がっているもの同士は、上にある節を「親」、下にある節を「子」と言ったりします。
完全２分木とは
葉以外の節が全て2つの子を持ち、根から葉までの深さが一様に等しい２分木を、完全２分木と言います。
完全２分木の持つ葉の数は、２分木の階層の深さから算出することができます。
葉の数＝2^深さ
また、葉を除く節の数は、次の式で求めることができます。
節の数＝2^深さ-1
２分探索木とは
親に対する左部分木と右部分木の関係が、「左の子＜親＜右の子」となる２分木を、２分探索木と言います。
このツリー構造には以下の特性があります。
・親の左側にある節は全て親よりも小さなデータになります。
・親の右側にある節は全て親よりも大きなデータになります。
この特性により、２分探索木ではデータの探索を容易に行うことができます。
探索対象データを節の中身と比較して、探索対象の方が小さければ左へ、大きければ右へ移動します。
これを節ごとに繰り返すことで目的のデータにたどり着きます。
２分探索木に節点を追加する場合、以下の手順を行います。
①追加要素と節点を根から比較します。
②追加要素が小さければ左へ、大きければ右へ降ります。
③上記までを繰り返し、比較する先がなければそこへ追加します。
また、節点の削除は以下のやり方で行います。
ケース１：末端の葉を削除する場合
葉を削除します。
ケース２：1つしか子を持たない節点を削除する場合
対象の節点を削除した後、その位置に子である節点を移動させます。
ケース３：2つの子を持つ節点を削除する場合
対象の節点を削除した後、右部分木の中の最小の要素（もしくは左部分木の中の最大の要素）を、その位置に移動させます。
今回の一言・・・
このようなツリー構造は、ファイルの構造だけでなくプログラムのソースのフォルダ構成にも使用されます。
検索などのほしいデータを探す場合に参考になる考え方になります。
ここまで読んでくれてありがとう。
では、また次回。
コメント