基礎理論～グラフ理論（木構造）～

初めに

グラフ理論2ということで、何を書くかって言うと、木構造について。

前回は

です。

木構造も、グラフの一種です。点があって、それを結ぶ辺がある。これは立派なグラフの形。

木構造というのは、1つの点からn個の点に対して辺があり、その接続先の点からまたn個の点に向けて辺が結ばれる形です。樹形図が想像しやすいでしょう。

この点の数などによって分類分けがされます。

どんなときにこれが使われるのか？というと、データ探索のときですね。

木構造の一番最上位の点(根やルートと呼ぶ)から、「さーて目的のデータはどこにあるかなー」と、伸びる辺をたどって各点(節やノードと呼ぶ)を探索します。

基本的に、各ノードの中には数値が入っておりその数値を見て次の検索先を決めていきます。

根からの深さ、各節と親の節の上下関係などによってこのグラフって、名称が変わります。それを紹介します。

（塾の合間だったから字は汚いです）

木構造 pic.twitter.com/1r8lCbxrVR
— こなさん(空瓶)@鬱SE講師 (@sorabin_) 2019年6月29日

子の節と親の節の間に、

子＞親

もしくは

子＜親

が存在するものを ヒープ と呼びます。

左の子、親、右の子の節の間に、以下の制約が存在します。

左の子の節の値＜親の節の値＜右の節の値

これを 二分探索木 と呼びます。

現在の節より大きい値を探すのか、小さい値を探すのか？で右へ行くのか、左へ行くのか決めるようなものになります。

出題頻度も高く、「こういうデータを探すとき、どういう形で値を探しますか？」って出てきますね。

二分探索木のうち、根から最下層の節までの深さの差が、０ or １のものを AVL木 と呼びます。

根以外の節は、同じ数の子を持つ木を B木といいますね。