Binary Tree(2分木)

リストは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の 定義