スライド 1

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

Download Report