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

●問 (2-3-4木の基本操作)

次の 2-3-4 木に 7, 10, 0 の順で要素を挿入したときの木の変化を，
1要素の挿入ごとに図示せよ．ただし，2-3-4木の操作のアルゴリズムは，
授業で説明されたものを使うこと．

               (4,6)
             ／  |  ＼
        (1,2,3) (5) (8,9)

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

●答 (2-3-4木の基本操作)

各要素を挿入したときの 2-3-4 木の変化を次に示す．

挿入前
               (4,6)
             ／  |  ＼
        (1,2,3) (5) (8,9)

7 の挿入後
               (4,6)
             ／  |  ＼
        (1,2,3) (5) (7,8,9)

10 の挿入後
               (4,6,8)
             ／  |  |  ＼
        (1,2,3) (5)(7) (9,10)

0 の挿入後
                   (6)
                ／     ＼
             (2,4)      (8)
           ／  |  ＼   ／  ＼
        (0,1) (3) (5) (7) (9,10)

[解説]

7 探索の失敗位置の葉 (8,9) が2要素以下なので，この葉に挿入する．

10 の探索時に3要素の頂点 (7,8,9) を訪れるので，中央値 8 を親 (4,6) へ
挿入し，残りを (7) と (9) へ分割してから，探索の失敗位置の葉 (9) へ挿入する．

0 の探索時には3要素の根 (4,6,8) と頂点 (1,2,3) を通るので，どちらも挿入前に
分割する．授業で解説されたアルゴリズムでは，探索時に通る3要素の頂点すべてを，
挿入前の通りがけに分割することに注意する．

参考までに，上記の2-3-4木への挿入に対応する2色木への挿入の結果を以下に示す．
ただし，2-3-4木に対応する2色木は複数あるので，2色木への挿入アルゴリズムとして
授業で解説されたものを使った実行結果を示す．また，フォントの都合上，
2種類の辺を区別する代わりに赤辺の入る頂点を [ ] で区別する．

挿入前
                 6
              ／   ＼
            [4]      9
           ／ ＼   ／
           2   5  [8]
         ／ ＼
        [1] [3]

7 の挿入後
                 6
              ／   ＼
            [4]      8
           ／ ＼   ／ ＼
           2   5  [7] [9]
         ／ ＼
        [1] [3]

10 の挿入後
                 6
              ／   ＼
            [4]     [8]
           ／ ＼   ／ ＼
           2   5   7   9
         ／ ＼          ＼
        [1] [3]         [10]

0 の挿入後
                   6
                ／   ＼
               4       8
             ／ ＼   ／ ＼
            [2]  5   7   9
           ／ ＼          ＼
           1   3          [10]
         ／
        [0]

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

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