前回、連結リストの操作をトレースしました。今回は、科目Bのデータ構造の続きとして、「二分木・木構造」を整理します。
木構造とは
木構造とは、データどうしを、親と子のような上下関係でつなげていくデータ構造です。以前整理した連結リストが、データを一直線につなげていたのに対して、木構造は、１つのデータから複数のデータへと枝分かれしていく点が特徴です。
木構造の一番上にあるデータを「根(ルート)」、末端にあるデータを「葉(リーフ)」と呼びます。木を逆さまにしたような形で表現されることが多く、根が上、葉が下に描かれます。
二分木とは
二分木とは、木構造の中でも、それぞれのデータ(ノード)が、最大で２つの子(左の子・右の子)しか持たない、という制限がついたものです。
科目Bでは、この二分木の中でも、「左の子は親より小さい値、右の子は親より大きい値」というルールで並べられた「二分探索木」がよく出題されます。このルールがあることで、以前整理した二分探索と同じように、目的の値を効率よく探し出すことができます。
二分探索木を探索する
二分探索木から目的の値を探すときは、次のような手順で進めます。
- 根(ルート)の値と目的の値を比較する
- 目的の値のほうが小さければ左の子へ、大きければ右の子へ進む
- 目的の値と一致するノードが見つかるまで、これを繰り返す
以前整理した二分探索が「配列の範囲を半分に絞り込む」考え方だったのに対して、二分探索木は「左右どちらに進むかを、ノードごとに判断していく」という考え方になります。どちらも、「比較して、探す範囲(または進む方向)を絞り込む」という発想の根っこは同じだと感じました。
木構造のたどり方(走査)
木構造をすべて確認する方法として、「深さ優先探索」と「幅優先探索」という考え方があります。
- 深さ優先探索:できるだけ深く(葉に近く)進んでから、戻って別の枝を探す
- 幅優先探索:根に近いノードから順番に、階層ごとに確認していく
自分は、深さ優先探索を「行き止まりまで進んでから戻る」、幅優先探索を「同じ階層を横並びで確認してから、一段下がる」というイメージで区別するようにしています。
学習してみた感想
木構造は、連結リストのイメージ(一直線につながる矢印)に、「枝分かれ」という要素が加わることで、最初は図を描くだけでも時間がかかりました。それでも、二分探索木の「左右どちらに進むか」という判断は、以前学んだ二分探索の考え方とつながっていたおかげで、比較的スムーズに理解できました。
次回は、ハッシュ表の仕組みと衝突対策を整理します。
