アルゴリズムとデータ構造
補足資料13-3
「2分探索木からの節点の削除」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
探索木のオペレータ
• 探索木を探索する
• 探索木に節点を追加（挿入）する
• 探索木から節点を削除する
1. 端点（葉：leaf）の削除
2. 一つの子孫しか持たない節点の削除
3. 二つの子孫を持つ接点の削除
探索木のオペレータ
• 探索木を探索する
• 探索木に節点を追加（挿入）する
• 探索木から節点を削除する
1. 端点（葉：leaf）の削除
2. 一つの子孫しか持たない節点の削除
3. 二つの子孫を持つ接点の削除
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
7
2
9
1
NU
LL
6
NU
LL
8
NU
LL
4
5
NU
LL
NU
LL
NU
LL
delete(8, root)
3
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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 ){
8
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(8, t->right)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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 ){
8
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(8, t->right)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
q
delete(8, t->right)
if ( t == NULL )
printf(“見つかりませんでした\n”);
8
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
8
x
t
qelse if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”); if( t->right == NULL ){
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
q = t;
t = t->left;
t->left = delete( x, t->left );
t = t->right;
free(q);
else if ( x > t->key )
free(q);
} else if( t->left == NULL ){
t->right = delete( x, t->right );
} else {
q = t;
NU
NU
else{
t->left = del( t, t->left ); if( t->right == NULL ){
LL
LL
t = t->right;
}
free(q);
q = t;
}
} else {
t = t->left;
return (t);
t->left = del( t, t->left );
free(q);
}
} else if( t->left == NULL ){
}
q = t;
return (t);
t = t->right;
7
delete(8, t->right)
2
9
1
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
6
8
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
q
delete(8, t->right)
if ( t == NULL )
printf(“見つかりませんでした\n”);
8
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
8
x
t
qelse if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”); if( t->right == NULL ){
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
q = t;
t = t->left;
t->left = delete( x, t->left );
t = t->right;
free(q);
else if ( x > t->key )
free(q);
} else if( t->left == NULL ){
t->right = delete( x, t->right );
} else {
q = t;
NU
NU
else{
t->left = del( t, t->left ); if( t->right == NULL ){
LL
LL
t = t->right;
}
free(q);
q = t;
}
} else {
t = t->left;
return (t);
t->left = del( t, t->left );
free(q);
}
} else if( t->left == NULL ){
}
q = t;
return (t);
t = t->right;
7
delete(8, t->right)
2
9
1
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
6
8
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
q
delete(8, t->right)
if ( t == NULL )
printf(“見つかりませんでした\n”);
8
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
8
x
t
qelse if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”); if( t->right == NULL ){
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
q = t;
t = t->left;
t->left = delete( x, t->left );
t = t->right;
free(q);
else if ( x > t->key )
free(q);
} else if( t->left == NULL ){
t->right = delete( x, t->right );
} else {
q = t;
NU
NU
else{
t->left = del( t, t->left ); if( t->right == NULL ){
LL
LL
t = t->right;
}
free(q);
q = t;
}
} else {
t = t->left;
return (t);
t->left = del( t, t->left );
free(q);
}
} else if( t->left == NULL ){
}
q = t;
return (t);
t = t->right;
7
delete(8, t->right)
2
9
1
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
6
8
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
q
delete(8, t->right)
if ( t == NULL )
printf(“見つかりませんでした\n”);
8
NULL
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
8
x
t
qelse if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”); if( t->right == NULL ){
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
q = t;
t = t->left;
t->left = delete( x, t->left );
t = t->right;
free(q);
else if ( x > t->key )
free(q);
} else if( t->left == NULL ){
t->right = delete( x, t->right );
} else {
q = t;
NU
NU
else{
t->left = del( t, t->left ); if( t->right == NULL ){
LL
LL
t = t->right;
}
free(q);
q = t;
}
} else {
t = t->left;
return (t);
t->left = del( t, t->left );
free(q);
}
} else if( t->left == NULL ){
}
q = t;
return (t);
t = t->right;
7
delete(8, t->right)
2
9
1
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
6
8
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
q
delete(8, t->right)
if ( t == NULL )
printf(“見つかりませんでした\n”);
8
NULL
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
8
x
t
qelse if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”); if( t->right == NULL ){
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
q = t;
t = t->left;
t->left = delete( x, t->left );
t = t->right;
free(q);
else if ( x > t->key )
free(q);
} else if( t->left == NULL ){
t->right = delete( x, t->right );
} else {
q = t;
NU
NU
else{
t->left = del( t, t->left ); if( t->right == NULL ){
LL
LL
t = t->right;
}
free(q);
q = t;
}
} else {
t = t->left;
return (t);
t->left = del( t, t->left );
free(q);
}
} else if( t->left == NULL ){
}
q = t;
return (t);
t = t->right;
7
delete(8, t->right)
2
9
1
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
6
8
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
q
delete(8, t->right)
if ( t == NULL )
printf(“見つかりませんでした\n”);
8
NULL
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
8
x
t
qelse if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”); if( t->right == NULL ){
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
q = t;
t = t->left;
t->left = delete( x, t->left );
t = t->right;
free(q);
else if ( x > t->key )
free(q);
} else if( t->left == NULL ){
t->right = delete( x, t->right );
} else {
q = t;
NU
NU
else{
t->left = del( t, t->left ); if( t->right == NULL ){
LL
LL
t = t->right;
}
free(q);
q = t;
}
} else {
t = t->left;
return (t);
t->left = del( t, t->left );
free(q);
}
} else if( t->left == NULL ){
}
q = t;
return (t);
t = t->right;
7
delete(8, t->right)
2
9
1
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
6
8
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
q
delete(8, t->right)
if ( t == NULL )
printf(“見つかりませんでした\n”);
8
NULL
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
8
x
t
qelse if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”); if( t->right == NULL ){
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
q = t;
t = t->left;
t->left = delete( x, t->left );
t = t->right;
free(q);
else if ( x > t->key )
free(q);
} else if( t->left == NULL ){
t->right = delete( x, t->right );
} else {
q = t;
NU
NU
else{
t->left = del( t, t->left ); if( t->right == NULL ){
LL
LL
t = t->right;
}
free(q);
q = t;
}
} else {
t = t->left;
return (t);
t->left = del( t, t->left );
free(q);
}
} else if( t->left == NULL ){
}
q = t;
return (t);
t = t->right;
7
delete(8, t->right)
2
9
1
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
6
8
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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 ){
8
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(8, t->right)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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 ){
8
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(8, t->right)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
root
delete(8, root)
x
8
t
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);
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
端点（葉：leaf）の削除
main()
…
root = delete(8, root);
...
※ メンバ count は省略
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
探索木のオペレータ
• 探索木を探索する
• 探索木に節点を追加（挿入）する
• 探索木から節点を削除する
1. 端点（葉：leaf）の削除
2. 一つの子孫しか持たない節点の削除
3. 二つの子孫を持つ接点の削除
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
7
2
9
1
NU
LL
6
NU
LL
8
NU
LL
4
5
NU
LL
NU
LL
delete(6, root)
3
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
NU
LL
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
7
2
9
1
NU
LL
6
NU
LL
8
NU
LL
4
5
NU
LL
NU
LL
delete(6, root)
3
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
NU
LL
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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);
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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);
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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 ){
6
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(6, t->left)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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 ){
6
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(6, t->left)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
delete(6, root)
※ メンバ count は省略
root
delete(6, t->left)
x
6
t
q
if ( t == NULL )
printf(“見つかりませんでした\n”);
6
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
else if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
free(q);
if( t->right == NULL ){
6
x
t } else if( t->left
q == NULL ){
q = t;
q = t;
t = t->left;
t = t->right;
if ( t == NULL )
free(q);
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
} else {
q = t;
t->left
t->left = delete( x, t->left
); = del( t, t->left );
t = t->right;
}
else if ( x > t->key )
free(q);
} x, t->right );
t->right = delete(
} else {
return (t);
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
7
delete(6, t->left)
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
delete(6, root)
※ メンバ count は省略
root
delete(6, t->left)
x
6
t
q
if ( t == NULL )
printf(“見つかりませんでした\n”);
6
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
else if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
free(q);
if( t->right == NULL ){
6
x
t } else if( t->left
q == NULL ){
q = t;
q = t;
t = t->left;
t = t->right;
if ( t == NULL )
free(q);
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
} else {
q = t;
t->left
t->left = delete( x, t->left
); = del( t, t->left );
t = t->right;
}
else if ( x > t->key )
free(q);
} x, t->right );
t->right = delete(
} else {
return (t);
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
7
delete(6, t->left)
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
delete(6, root)
※ メンバ count は省略
root
delete(6, t->left)
x
6
t
q
if ( t == NULL )
printf(“見つかりませんでした\n”);
6
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
else if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
free(q);
if( t->right == NULL ){
6
x
t } else if( t->left
q == NULL ){
q = t;
q = t;
t = t->left;
t = t->right;
if ( t == NULL )
free(q);
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
} else {
q = t;
t->left
t->left = delete( x, t->left
); = del( t, t->left );
t = t->right;
}
else if ( x > t->key )
free(q);
} x, t->right );
t->right = delete(
} else {
return (t);
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
7
delete(6, t->left)
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
delete(6, root)
※ メンバ count は省略
root
delete(6, t->left)
x
6
t
q
if ( t == NULL )
printf(“見つかりませんでした\n”);
6
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
else if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
free(q);
if( t->right == NULL ){
6
x
t } else if( t->left
q == NULL ){
q = t;
q = t;
t = t->left;
t = t->right;
if ( t == NULL )
free(q);
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
} else {
q = t;
t->left
t->left = delete( x, t->left
); = del( t, t->left );
t = t->right;
}
else if ( x > t->key )
free(q);
} x, t->right );
t->right = delete(
} else {
return (t);
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
7
delete(6, t->left)
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
delete(6, root)
※ メンバ count は省略
root
delete(6, t->left)
x
6
t
q
if ( t == NULL )
printf(“見つかりませんでした\n”);
6
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
else if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
free(q);
if( t->right == NULL ){
6
x
t } else if( t->left
q == NULL ){
q = t;
q = t;
t = t->left;
t = t->right;
if ( t == NULL )
free(q);
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
} else {
q = t;
t->left
t->left = delete( x, t->left
); = del( t, t->left );
t = t->right;
}
else if ( x > t->key )
free(q);
} x, t->right );
t->right = delete(
} else {
return (t);
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
7
delete(6, t->left)
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
delete(6, root)
※ メンバ count は省略
root
delete(6, t->left)
x
6
t
q
if ( t == NULL )
printf(“見つかりませんでした\n”);
6
x
t
q
else if ( x < t->key )
t->left = delete( x, t->left );
if ( t == NULL )
else if ( x > t->key )
printf(“見つかりませんでした\n”);
t->right = delete( x, t->right );
else if ( x < t->key )
else{
t->left = delete( x, t->left );
if( t->right == NULL ){
else if ( x > t->key )
q = t;
t->right = delete( x, t->right );
t = t->left;
else{
free(q);
if( t->right == NULL ){
6
x
t } else if( t->left
q == NULL ){
q = t;
q = t;
t = t->left;
t = t->right;
if ( t == NULL )
free(q);
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
} else {
q = t;
t->left
t->left = delete( x, t->left
); = del( t, t->left );
t = t->right;
}
else if ( x > t->key )
free(q);
} x, t->right );
t->right = delete(
} else {
return (t);
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
7
delete(6, t->left)
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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 ){
6
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(6, t->left)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
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
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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 ){
6
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(6, t->left)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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 ){
6
x
t
q
q = t;
t = t->left;
if ( t == NULL )
free(q);
printf(“見つかりませんでした\n”);
} else if( t->left == NULL ){else if ( x < t->key )
q = t;
t->left = delete( x, t->left );
t = t->right;
else if ( x > t->key )
free(q);
t->right = delete( x, t->right );
} else {
else{
t->left = del( t, t->left ); if( t->right == NULL ){
}
q = t;
}
t = t->left;
return (t);
free(q);
7
delete(6, t->left)
} else if( t->left == NULL ){
q = t;
t = t->right;
free(q);
} else {
t->left = del( t, t->left );
}
}
return (t);
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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);
7
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
delete(6, root)
x
6
t
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);
7
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
一つの子孫しか持たない節点の削除
main()
…
root = delete(6, root);
...
※ メンバ count は省略
root
7
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
探索木のオペレータ
• 探索木を探索する
• 探索木に節点を追加（挿入）する
• 探索木から節点を削除する
1. 端点（葉：leaf）の削除
2. 一つの子孫しか持たない節点の削除
3. 二つの子孫を持つ接点の削除
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
7
2
1
NU
LL
9
delete(7, root)
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
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
左部分木の
最右要素で
置き換える
6
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
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
7
2
1
NU
LL
9
delete(7, root)
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
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
delete(7, root)
x
7
t
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);
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
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
delete(7, root)
x
7
t
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);
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
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
delete(7, root)
x
7
t
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);
t
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
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
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
delete(7, root)
x
7
t
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);
t
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
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
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
7
t
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);
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
delete(7, root)
x
t
7
2
9
1
del(t, t->left)
dstt
t
NU
LL
6
NU
LL
NU
LL
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
8
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
7
t
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);
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
delete(7, root)
x
t
7
2
9
1
del(t, t->left)
dstt
t
NU
LL
6
NU
LL
NU
LL
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
8
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
7
t
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);
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
delete(7, root)
x
t
6
2
9
1
del(t, t->left)
dstt
t
NU
LL
6
NU
LL
NU
LL
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
8
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
7
t
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);
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
delete(7, root)
x
t
6
2
9
1
del(t, t->left)
dstt
t
NU
LL
6
NU
LL
NU
LL
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
8
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
7
t
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);
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
delete(7, root)
x
t
6
2
9
1
del(t, t->left)
dstt
t
NU
LL
6
NU
LL
NU
LL
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
8
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
7
t
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);
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
delete(7, root)
x
t
6
2
9
1
del(t, t->left)
dstt
t
NU
LL
6
NU
LL
NU
LL
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
8
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
7
t
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);
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
delete(7, root)
x
t
6
2
9
1
del(t, t->left)
dstt
t
NU
LL
6
NU
LL
NU
LL
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
8
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
delete(7, root)
x
7
t
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);
t
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
6
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
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
delete(7, root)
x
7
t
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);
t
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
6
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
del(t, t->left)
…
root = delete(7, root);
...
root
dstt
delete(7, root)
x
7
t
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);
t
※ メンバ count は省略
q
if ( t->right != NULL )
t->right = del( dstt, t->right );
else{
dstt->key = t->key; dstt->count = t->count;
q = t;
t = t->left;
free(q);
}
return (t);
6
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
delete(7, root)
x
7
t
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);
6
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
delete(7, root)
x
7
t
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);
6
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
delete(7, root)
x
7
t
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);
6
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL
二つの子孫を持つ接点の削除
main()
…
root = delete(7, root);
...
※ メンバ count は省略
root
6
2
9
1
NU
LL
8
NU
LL
NU
LL
4
3
NU
LL
5
NU
LL
NU
LL
NU
LL
10
NU
LL
NU
LL
NU
LL

スライド 1

スライド 1

年金受給権者所在不明届

集合の表現