Binary Tree(2分木)
木
リストは1つのデータをつなげていくデータ構造でした.2つ以上のデータ をつなげていくデータ構造は木構造とよばれます.その中でも2 本の枝をもっているのが2分木です.いいかたを変えると,リストは腕が1本あり,それを1つの次のデータにつなげていきますが,2分木は腕が2本あります.
木構造にデータを格納する際に,順序性をもたせてデータ管理する木を順序木といいます.一般に順序木としての2分木 は,現在のデータ基準にして「それより大きいデータ」,「それより小さいデータ」をそれぞれ右または左に振り分けてつなげていきます.
本講義で は、小さいデータを左、大きいデータを右というように統一して考えます。
2分木の探索(2分木 からデータを探す)
2分木に格納されたデータから,あるデータを探そうとした場合,簡単にデータを探すことがで きます.
2分木において,目標となるノードを探す手順は以下のとおりです.
- ルー トを最初のノードにする
- 目標値がノードより小さければ左,大きければ右に移動
- 1,2の繰り返し
2 分木のデータの出力
2分木に 格納されたデータを出力する際には,以下のパターンがあります.
- 横型探索 ・・・ 自 分と同世代のノードを横に辿って出力していきます.
- 縦型探索 ・・・ 子ノードを辿っていきながら出力していきます.
- ・行きがけ順 ・・・ 出会ったときに即座に出力します
- ・通りがけ順 ・・・ 子ノードをまたぐ際に出力します。
- ・帰りがけ順 ・・・ 戻るときに出力します。
2分木を利用したデータ構造は,通りがけ順で出力するとソーティングされた形 で出力するという利点があります。
2分木におけるデータ(ノード)削除 (教科書p400~)
削除のパターン(場合分け)は3つ。詳細は教科書で。
- 子ノードを持たない場合
- 1つだけ子ノードを持つ場合
- 2つの子ノードを持つ場合
- (1)削除したいノードの左部分木から最大値のノードを見つける
- (2)最大値を削除ノードへ代入
- (3)最大値のあったノードを削除
2分木実装するために再帰アルゴリズムについて理解しよう
2分木のプログラムを作成するときには,再帰アルゴリズムを知ってお くと便利です.(詳細は5章参照)
再帰 ・・・ ある事象が自分自身によって定義されていること.
例)GNUの 定義