探索木のオペレータ（ダイジェスト）

アルゴリズムとデータ構造 補足資料

「

分探索木の追加・削除（ダイジェスト）」

横浜国立大学

理工学部

数物・電子情報系学科

富井尚志

探索木のオペレータ（ダイジェ スト）

•

探索木を探索する

•

探索木に節点を追加（挿入）する

•

探索木から節点を削除する

1.

端点（葉：

）の削除

2.

一つの子孫しか持たない節点の削除

二つの子孫を持つ接点の削除

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

N7

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7 _N

U L L N2

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

N2

U L L

N U L L

N9

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

2 _N

U L L

N9

U L L

N U L L N1

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

2 _N9

U L L

N U L L N1

U L L

N U L L

N6

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

2 9 _N

U L L N1

U L L

N U L L

N6

U L L

N U L L

N8

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

2 9

N1

U L L

N U L L

N6

U L L

N U L L

N8

U L L

N U L L

N10

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

2 9

N1

U L L

N U L L

6 _N

U L L

N8

U L L

N U L L

N10

U L L

N U L L N4

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

2 9

N1

U L L

N U L L

6 _N

U L L

N8

U L L

N U L L

N10

U L L

N U L L

4 _N

U L L N3

U L L

N U L L

探索木の成長

root

{7, 2, 9, 1, 6, 8, 10, 4, 3, 5}

7

2 9

N1

U L L

N U L L

6 _N

U L L

N8

U L L

N U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

探索木の枝刈り

root

7

2 _N9

U L L N1

U L L

N U L L

6 _N

U L L

N8

U L L

N U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

delete( 8, root )

端点、または、

一つの子孫しか持たない接点の削除

探索木の枝刈り

root

7

2 _N9

U L L N1

U L L

N U L L

6 _N

U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

delete( 7, root )

左部分木の 最右要素で 置き換え

二つの子孫を持つ接点の削除

探索木の枝刈り

root

6

2 _N9

U L L N1

U L L

N U L L

6 _N

U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

delete( 7, root )

値をコピ ー

左部分木の 最右要素 左部分木の

最右要素で 置き換え

二つの子孫を持つ接点の削除

探索木の枝刈り

root

6

2 _N9

U L L N1

U L L

N U L L

6 _N

U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

delete( 7, root )

左部分木の

最右要素→削除 左部分木の

最右要素で 置き換え

二つの子孫を持つ接点の削除

探索木の枝刈り

root

6

2 _N9

U L L N1

U L L

N U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

探索木の成長

root

6

2 _N9

U L L N1

U L L

N U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

7

を追加

探索木の成長

root

6

2 9

N1

U L L

N U L L

N10

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

7

を追加

N7

U L L

N U L L

動的データ構造：

追加や削除が生じても、

構造を変えながらデータを

保持できる