データ構造・アルゴリズム論 I
2-3-4 木の操作手順
山田 俊行
http://www.cs.info.mie-u.ac.jp/~toshi/
2014 年 11 月
1
2-3-4 木への挿入
要素 22 の挿入前
30
15
10
40 60
20 25
35
45 50 55
65
2
2-3-4 木への挿入
探索終点である葉に挿入 (2 要素以下の頂点に挿入可能)
30
40 60
15
10
20 25
35
45 50 55
65
3
ts2-3-4 木への挿入
探索終点である葉に挿入 (2 要素以下の頂点に挿入可能)
30
40 60
15
10
20 22 25
35
45 50 55
65
4
2-3-4 木への挿入
要素 44 の挿入前
30
40 60
15
10
20 22 25
35
45 50 55
65
5
2-3-4 木への挿入
1. 探索で見付けた 3 要素頂点を，分割して中央値を親に移動
30
15
10
20 22 25
40 60
35
45 50 55
65
6
2-3-4 木への挿入
1. 探索で見付けた 3 要素頂点を，分割して中央値を親に移動
30
40 50 60
15
10
20 22 25
35
45
55
65
7
2-3-4 木への挿入
2. 探索終点である葉に挿入 (分割後の終点は 2 要素以下)
30
15
10
20 22 25
40 50 60
35
45
55
65
8
25
2-3-4 木への挿入
2. 探索終点である葉に挿入 (分割後の終点は 2 要素以下)
30
40 50 60
15
10
20 22 25
35
44 45
55
65
9
2-3-4 木への挿入
要素 33 の挿入前
15 35 50
10
20 25 30
40 45
55
10
2-3-4 木への挿入
1. 探索で通る各 3 要素頂点を，分割して中央値を親に移動
15 35 50
10
20 25 30
40 45
55
11
2-3-4 木への挿入
1. 探索で通る各 3 要素頂点を，分割して中央値を親に移動
35
15
10
50
20 25 30
40 45
55
12
2-3-4 木への挿入
1. 探索で通る各 3 要素頂点を，分割して中央値を親に移動
35
50
15
10
20 25 30
40 45
55
13
2-3-4 木への挿入
1. 探索で通る各 3 要素頂点を，分割して中央値を親に移動
35
50
15 25
10
20
30
40 45
55
14
2-3-4 木への挿入
2. 探索終点である葉に挿入
35
50
15 25
10
20
30
40 45
55
15
2-3-4 木への挿入
2. 探索終点である葉に挿入
35
50
15 25
10
20
30 33
40 45
55
16
2-3-4 木の操作手順
挿入
1. 探索で通る各 3 要素頂点を，分割して中央値を親に移動
2. 探索終点である葉に挿入
17
2-3-4 木の操作手順
削除
前処理 (2 分探索木からの削除と同様)
1. 探索して葉以外にあれば，次の値を削除値の位置に移動
2. 葉 (削除位置か移動後の空き位置) で削除の本処理を開始
本処理 (2-3-4 木条件を満たすよう，根へ向けて木を再構成)
• 削除位置が複数要素をもつなら，単に要素を削除
• 削除位置が 1 要素で，兄か弟が複数要素をもてば，
兄/弟 → 親 → 削除位置 と要素を移動
• 削除位置が 1 要素で，兄弟とも 1 要素なら，
親の要素を 兄/弟 へと移して統合し，
◦ 親が根なら，親を削除して終了
◦ 親が根以外なら，親を削除位置として本処理を反復
18