数式が読み込まれない場合は1回再読み込みしてみてください。基本情報-テクノロジ系-データ構造とアルゴリズムこんにちは、ももやまです。今回は期末試験や基本情報に頻出する2分探索木について説明していきたいと思います。練習1練習2練習3練習4練習5練習68.練習問題の答え解答1解答2解答3解答4解答5解答66を持ってきた場合8を持ってきた場合9.さいごに1.2分木2分探索木について説明する前にデータ構造の1つである2分木(木構造)について簡単にですが説明したいと思います。詳しい記事はこちらに用意してあるので興味がある人はご覧ください。用語復習まず、2分木で頻繁に出てくる用語の復習をしておきましょう。[ノード]○の部分を節もしくはノードと呼びます。上の図の場合、D1〜D7までの節があります。節には、各種データが入っています。○と○(節と節)を結ぶ線のことを枝と呼びます。親・子あるノード(節)から見て1つ上のノードのことを親、1つ下のノードのことを子と呼びます。D5の親、D4(とD5)はD2の子です。最上位のノード(節)を根と呼びます。親子で表現すると、親を持たないノードが根となります。最下位のノード(節)を葉と呼びます。親子で表現すると、子を持たないノードが葉となります。部分木ある節からぶら下がる部分を部分木と呼びます。節の左側にぶら下がっている部分を左部分木、右側にぶら下がっている部分を右部分木と呼びます。3つで表現することができます。用いることができます。右の子の場所(ポインタ)};2.2分探索木とは親の左側のノードの値が必ず親よりも小さく、右側のノードの値が必ず親よりも大きくなっている2分木のことを2分探索木と呼びます。2分探索木では、下の図のようにどの親に対しても値が必ず左の子<親<右の子となっています。左の子だけでなく、左部分木のすべてのノードの値が親よりも小さくなる特性があります。右部分木のすべてのノードの値も同様に親よりも大きくなる特性があります。左部分木のそれぞれのノード<親<右部分木のそれぞれのノードの関係も成立します。よって、上の図にある2分探索木のそれぞれのノードに入る値の範囲は下のようになります。3.2分探索木を用いた探索2分探索木では、それぞれのノードに対し、「左部分木のそれぞれのノード<基準ノード<右部分木のそれぞれのノード」が成り立つので、データの探索を簡単に行うことができます。実際に上の木構造から「10が入ったノード」を探してみましょう。2分探索木による探索は、根からスタートします。最初は根が基準となります。目標データと基準の大小を比べます。今回は、(目標データ)<(基準)なので、目標データは左部分木にあることがわかります。基準を左に動かします。目標データと基準の大小を比べます。すると、(目標データ)>(基準)なので、目標データは右部分木にあることがわかります。今度は基準を右に動かします。すると、(目標)=(新基準)となるので探索が成功し、探索終了です。逆に目標データと基準の大小を比べて基準を動かす際に移動するノードが見つからなければ探索失敗となります。探すプログラムは、下のように書くことができます。データがなければNULL}2分探索木を用いるプログラムでは、再帰処理を行うことがほとんどです。再帰を理解できていない人はこちらの記事で復習しておきましょう。4.2分探索木のノード追加つぎは元々の木構造を崩さずに2分探索木にデータを追加する方法について説明したいと思います*1。下の木構造に「20が入ったノード」を追加してみましょう。2分探索木に追加する場合も、探索するときと同様に根のノードから順番にチェックしていきます*2。今回は追加データのほうが大きいので、基準を右に移動します。追加データと基準データの大小をチェックすると、追加データのほうが大きいので基準を右に移動しようとします。右側には節がありませんね。ここに20を追加します。すると、元の形を崩さずにデータを簡単に入れることができますね!5.2分探索木のノード削除2分探索木にあるノードをなるべく木構造を崩さずに削除する方法についても説明しておきましょう。追加のときとは異なり、削除するノードについている子の数によって削除手順が変わります。削除するノードに子がないとき(葉の場合)削除するノードに子がない場合は簡単です。ノードを削除して終わりです。10が入ったノードを削除すると、木構造は下の図のようになります。削除するノードの子が1つのとき削除するノードの子が1つのときは、子がないときに比べて少し処理が複雑になります。ノードの削除に加え、「削除したノード」の部分木をまるごと元々ノードがあった部分に移動させる必要があります。19が入ったノードを削除すると、木構造は下の図のようになります。削除するノードの子が2つのとき削除するノードの子が2つになると、子がないときに比べてさらに処理が複雑になります。ノードの削除に加え、元々ノードがあった部分に削除したノードの左部分木の最大値(削除したノードの値より1つ小さい値のノード削除したノードの右部分木の最小値(削除したノードの値より1つ大きい値のノード)のどちらかを移動させる必要があります。今回は、15が入ったノードを削除する際に右部分木の最小値を交換することにします。すると、木構造は下のようになります。木構造のすべてのノードを1回だけチェック(訪問)することを走査と呼びます。走査については下の記事で別に説明しているのでぜひご覧ください。www.momoyama-usagi.com7.練習問題では、6問ほど練習しましょう。後ろの4問は基本情報などの過去問となっています。練習1下の2分探索木から「9が入ったノード」を削除したとき、2分探索木はどうなるかを図示しなさい。練習2下の2分探索木から「15が入ったノード」を削除したとき、2分探索木はどうなるかを図示しなさい。子が2つあるノードを削除したあとは右部分木の最小値を用いること。練習32分探索木になっている2分木はどれか。午前問6]練習4次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。6の順にデータを与えたときにできる2分探索木はどれか。午前問5]練習6次の2分探索木からルートノード7を削除し、再び7を追加した2分探索木はどれか。午前問9]8.練習問題の答え解答1まず、9が入ったノードを削除します。つぎに、9が入ったノードの部分木を丸ごと移動させます。解答2「15が入ったノード」は子が2つなので、削除したノードの部分に「右部分木の最小値」が移動します。移動するときに19の部分木が崩れないように注意しましょう。よって「19のノード」を削除したときの2分探索木は上の図となります。解答3解答:イそれぞれのノードを親としたときに、「左部分木のそれぞれのノード<親<右部分木のそれぞれのノード」が必ず成立しているのが2分探索木の特徴です。イ以外の2分探索木には、値の制約がおかしいノードがあるため誤りです。1つ大きい値を持ってくる必要があります。1つ小さい値であれば11、1つ大きい値であれば13となるので、選択肢がある13を移動させればよい。解答5解答:エ下のような順番で2分木が挿入される。よって、答えはエとなる。小さい値を削除した位置に持ってくる必要がある。(この時点でウの選択肢が論外なことがわかる)6を持ってきた場合6を持ってくる場合、もともと7があった位置に6を移動させるつぎに、消した7を木構造が崩れないように追加する。8を持ってきた場合8を持ってくる場合、もともと7があった位置に8を移動させるつぎに、消した7を木構造が崩れないように追加する。この2つのどちらかが答えとなる。選択肢イは、6を持ってきた場合の木構造と一致する。9.さいごに今回は、データ構造の1つである2分木を用いている2分探索木についてまとめました。削除も基本情報ではよく出てくるので確認していきましょう。2分探索木の走査(列挙)について説明していきたいと思います。*1:余談ですが、空の木にデータを入れるときは「根を入れるデータのノード」にするだけでOKです。*2:追加するデータが基準データよりも大きければ右側へ、小さければ左側に基準を移動します。システムオートマトンPrologCLOSEサイト内検索を行います。はてなブログPro数学と情報が得意な大学生です。累計:リアルタイム現在の閲覧者数:。