Download presentation
Presentation is loading. Please wait.
1
アルゴリズムとデータ構造 補足資料13-4 「2分探索木の追加・削除（ダイジェスト）」
横浜国立大学 理工学部 数物・電子情報系学科 富井尚志
2
探索木のオペレータ（ダイジェスト） 探索木を探索する 探索木に節点を追加（挿入）する 探索木から節点を削除する 端点（葉：leaf）の削除
一つの子孫しか持たない節点の削除 二つの子孫を持つ接点の削除
3
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5}
4
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 NULL NULL
5
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 NULL 2 NULL NULL
6
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 NULL NULL NULL NULL
7
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 root NULL NULL NULL
8
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 root NULL NULL NULL
9
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 root NULL NULL NULL
10
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 root NULL NULL
11
探索木の成長 {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 4 root NULL NULL
12
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 NULL NULL NULL NULL NULL NULL NULL 4 NULL 3 NULL NULL
13
探索木の成長 root {7, 2, 9, 1, 6, 8, 10, 4, 3, 5} 7 2 9 1 6 8 10 NULL NULL NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL
14
探索木の枝刈り delete( 8, root ) 端点、または、 一つの子孫しか持たない接点の削除 7 2 9 1 6 8 10 4 3
NULL 1 6 8 10 NULL NULL NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL
15
探索木の枝刈り delete( 7, root ) 二つの子孫を持つ接点の削除 左部分木の 最右要素で 置き換え 7 2 9 1 6 10
NULL 1 6 10 NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL
16
探索木の枝刈り delete( 7, root ) 二つの子孫を持つ接点の削除 左部分木の 最右要素で 置き換え 6 2 9 1 6 10
値をコピー 2 9 NULL 1 6 10 NULL NULL NULL NULL NULL 左部分木の 最右要素 4 3 5 NULL NULL NULL NULL
17
探索木の枝刈り delete( 7, root ) 二つの子孫を持つ接点の削除 左部分木の 最右要素で 置き換え 6 2 9 1 6 10
NULL 1 6 10 NULL NULL NULL NULL NULL 左部分木の 最右要素→削除 4 3 5 NULL NULL NULL NULL
18
探索木の枝刈り 6 2 9 1 10 4 3 5 root NULL NULL NULL NULL NULL NULL NULL NULL
19
探索木の成長 7 を追加 6 2 9 1 10 4 3 5 root NULL NULL NULL NULL NULL NULL NULL
20
探索木の成長 7 を追加 6 動的データ構造： 追加や削除が生じても、 構造を変えながらデータを 保持できる 2 9 1 7 10 4 3
root 7 を追加 6 動的データ構造： 追加や削除が生じても、 構造を変えながらデータを 保持できる 2 9 1 7 10 NULL NULL NULL NULL NULL NULL 4 3 5 NULL NULL NULL NULL
Similar presentations
