2分木

分木  (教科書第10章)

リストは1つのデータをつなげていくデータ構造でした.2つ以上のデータ をつなげていくデータ構造は木構造とよばれます.その中でも2 本の枝をもっているのが2分木です.

いいかたを変えると,リストは腕が1本あり,それを1つの次のデータにつなげていきますが,2分木は腕が2本あります.

木構造にデータを格納する際に,順序性をもたせてデータ管理する木を順序木といいます.一般に順序木としての2分木 は,現在のデータ基準にして「それより大きいデータ」,「それより小さいデータ」をそれぞれ右または左に振り分けてつなげていきます.
本講義で は、小さいデータを左、大きいデータを右というように統一して考えます。

2分木の探索(2分木 からデータを探す)

2分木に格納されたデータから,あるデータを探そうとした場合,簡単にデータを探すことがで きます.
2分木において,目標となるノードを探す手順は以下のとおりです.

  1. ルー トを最初のノードにする
  2. 目標値がノードより小さければ左,大きければ右に移動
  3. 1,2の繰り返し

2 分木のデータの出力

2分木に 格納されたデータを出力する際には,以下のパターンがあります.

  • 横型探索 ・・・ 自 分と同世代のノードを横に辿って出力していきます.
  • 縦型探索 ・・・ 子ノードを辿っていきながら出力していきます.
      ・行きがけ順 ・・・ 出会ったときに即座に出力します
      ・通りがけ順 ・・・ 子ノードをまたぐ際に出力します。
      ・帰りがけ順 ・・・ 戻るときに出力します。

2分木を利用したデータ構造は,通りがけ順で出力するとソーティングされた形 で出力するという利点があります。


2分木におけるデータ(ノード)削除 (教科書p400~)
削除のパターン(場合分け)は3つ。詳細は教科書で。
  • 子ノードを持たない場合
  • 1つだけ子ノードを持つ場合
  • 2つの子ノードを持つ場合
     (1)削除したいノードの左部分木から最大値のノードを見つける
     (2)最大値を削除ノードへ代入
     (3)最大値のあったノードを削除



2分木実装するために再帰アルゴリズムについて理解しよう

2分木のプログラムを作成するときには,再帰アルゴリズムを知ってお くと便利です.(詳細は5章参照)

再帰 ・・・ ある事象が自分自身によって定義されていること.
        例)GNUの 定義



Comments