探索木のオペレータ

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

「 2 分探索木からの節点の削除」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

探索木のオペレータ

• 探索木を探索する

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

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

1. 端点（葉： leaf ）の削除

2. 一つの子孫しか持たない節点の削除 3. 二つの子孫を持つ接点の削除

探索木のオペレータ

• 探索木を探索する

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

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

1. 端点（葉： leaf ）の削除

2. 一つの子孫しか持たない節点の削除 3. 二つの子孫を持つ接点の削除

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

delete(8, root)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t ^NULL q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t ^NULL q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t ^NULL q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t ^NULL q

delete(8, t->right)

L NUL

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N10

U L L

N U L L N9

U L L

7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right) L NUL

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N10

U L L

N U L L N9

U L L

7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t q

delete(8, t->right)

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N10

U L L

N U L L N9

U L L

7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N10

U L L

N U L L N9

U L L

7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁸ t

delete(8, root)

q

端点（葉： leaf ）の削除

main()

…

root = delete(8, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N10

U L L

N U L L N9

U L L

7

※ メンバ count は省略

探索木のオペレータ

• 探索木を探索する

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

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

1. 端点（葉： leaf ）の削除

2. 一つの子孫しか持たない節点の削除 3. 二つの子孫を持つ接点の削除

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

main()

…

root = delete(6, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

delete(6, root)

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

main()

…

root = delete(6, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

ゴールのイメージ

6 _N

U L L

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

main()

…

root = delete(6, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

delete(6, root)

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

main()

…

root = delete(6, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁶ t q

delete(6, root)

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

main()

…

root = delete(6, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁶ t q

delete(6, root)

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

main()

…

root = delete(6, root);

...

root

N1

U L L

N U L L

4

N3

U L L

N U L L

N5

U L L

N U L L

6 _N

U L L

2

N8

U L L

N U L L

N10

U L L

N U L L

9 7

※ メンバ count は省略

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁶ t q

delete(6, root)

if ( t == NULL )

printf(“見つかりませんでした\n”);

else if ( x < t->key )

t->left = delete( x, t->left );

else if ( x > t->key )

t->right = delete( x, t->right );

else{

if( t->right == NULL ){

q = t;

t = t->left;

free(q);

} else if( t->left == NULL ){

q = t;

t = t->right;

free(q);

} else {

t->left = del( t, t->left );

} } return (t);

x ⁶ t q

delete(6, t->left)