━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題８
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (2分探索木の基本操作)

次の2分探索木に (1), (2), (3) の操作を実行した後の2分探索木をそれぞれ図示せよ．
(1), (2), (3) で一つずつ，三つの木を示すこと．

                50
              ／  ＼
            10      55
              ＼
               45
              ／
            35
          ／  ＼
        15      40

(1) 60, 25, 5, 20, 30 の順に挿入．ただし，常に葉に要素を追加すること．

(2) (1) の後に 40, 55 の順に(授業で扱ったアルゴリズムで)削除．

(3) (2) の後に 10 を(授業で扱ったアルゴリズムで)削除．

──────────────────────────────────────

●答 (2分探索木の基本操作)

授業で扱ったアルゴリズムで (1), (2), (3) の操作を実行してできる2分探索木を，
それぞれ以下に示す．

(1)
        50
      ／  ＼
    10      55
  ／  ＼      ＼
 5      45      60
      ／
    35
  ／  ＼
15      40
  ＼
    25
  ／  ＼
20      30

(2)
        50
      ／  ＼
    10      60
  ／  ＼
 5      45
      ／
    35
  ／
15
  ＼
    25
  ／  ＼
20      30

(3)
            50
          ／  ＼
        15      60
      ／  ＼
     5      45
          ／
        35
      ／
    25
  ／  ＼
20      30

[解説]

(1) 2分探索の失敗位置に要素を順次追加する．

(2) 削除要素(55)の子が一つなので，部分木(60)を削除位置(50の右)につなぐ．

(3) 削除要素(10)の子が二つなので，次に大きい値(15)で上書きし，空いた位置
(15のあった位置)に(25を根とする)部分木をつなぐ．授業で扱った削除のアルゴリズム
では，教科書のプログラムと同様に，削除要素の子が二つの場合にその次に大きい値で
置き換える．削除要素の直前の値で置き換えるようにアルゴリズムを変えても，
削除後にも2分探索木条件は保たれる．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/