• 検索結果がありません。

探索木のオペレータ

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "探索木のオペレータ"

Copied!
68
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 68 ページ )

全文

(1)

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

「 2 分探索木への節点の追加」

(2)

探索木のオペレータ

• 探索木を探索する

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

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

(3)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

(4)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

(5)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

(6)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

search(7, NULL) : 呼出1

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 7 t NULL

(7)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

search(7, NULL) : 呼出1

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 7 t

(8)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

search(7, NULL) : 呼出1

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 7 t

7 1

(9)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

search(7, NULL) : 呼出1

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 7 t

7

N U L L

N U L L

1

(10)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

search(7, NULL) : 呼出1

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 7 t

7

N U L L

N U L L

1

(11)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root NULL

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

(12)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 7 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

(13)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

(14)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

(15)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 2 t

(16)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 2 t

2 が入るのは、

7 の左部分木

(17)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 2 t

2 が入るのは、

7 の左部分木

search(2, NULL) : 呼出 3

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

x 2 t NULL

(18)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 2 t

2 が入るのは、

7 の左部分木

search(2, NULL) : 呼出 3

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 2 t

(19)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 2 t

2 が入るのは、

7 の左部分木

search(2, NULL) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

x 2 t

2 1

(20)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 2 t

2 が入るのは、

7 の左部分木

search(2, NULL) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 2 t

2

N U L L

N U L L

1

(21)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 2 t

2 が入るのは、

7 の左部分木

search(2, NULL) : 呼出 3

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

x 2 t

2

N U L L

N U L L

1

(22)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 2 t

2 が入るのは、

7 の左部分木

2

N U L L

N U L L

1

(23)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 2 t

2 が入るのは、

7 の左部分木

2

N U L L

N U L L

1

(24)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

search(2, root) : 呼出 2

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 2 t

2 が入るのは、

7 の左部分木

2

N U L L

N U L L

1

(25)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2 が入るのは、

7 の左部分木

2

N U L L

N U L L

1

(26)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2 が入るのは、

7 の左部分木

2

N U L L

N U L L

1

(27)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 2 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2 が入るのは、

7 の左部分木

2

N U L L

N U L L

1

(28)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

(29)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

(30)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t

(31)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 9 t

9 が入るのは、

7 の右部分木

(32)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t

9 が入るのは、

7 の右部分木

search(9, NULL) : 呼出 5

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t NULL

(33)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 9 t

9 が入るのは、

7 の右部分木

search(9, NULL) : 呼出 5

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

x 9 t

(34)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t

9 が入るのは、

7 の右部分木

search(9, NULL) : 呼出 5

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t

9 1

(35)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 9 t

9 が入るのは、

7 の右部分木

search(9, NULL) : 呼出 5

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

x 9 t

9

N U L L

N U L L

1

(36)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t

9 が入るのは、

7 の右部分木

search(9, NULL) : 呼出 5

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t

9

N U L L

N U L L

1

(37)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7

N U L L

1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 9 t

9 が入るのは、

7 の右部分木

9

N U L L

N U L L

1

(38)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 9 t

9 が入るのは、

7 の右部分木

9

N U L L

N U L L

1

(39)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

search(9, root) : 呼出 4

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 9 t

9

N U L L

N U L L

1

(40)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 9 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

(41)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

(42)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

(43)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 1 t

1 が入るのは、

7 の左部分木

(44)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

(45)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

2 の左部分木

(46)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

2 の左部分木

search(1, NULL) : 呼出 8

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t NULL

(47)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

2 の左部分木

search(1, NULL) : 呼出 8

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

x 1 t

(48)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

2 の左部分木 1

1

search(1, NULL) : 呼出 8

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

(49)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

2 の左部分木 1

1

search(1, NULL) : 呼出 8

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

x 1 t

(50)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

2 の左部分木 1

N U L L

N U L L

1

search(1, NULL) : 呼出 8

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

(51)

探索木 (search tree)

main()

root = NULL;

while( ( y=get_data() )!= EOD ) root = search( y, root )

…

y 1 root

int a[] = { 7, 2, 9, 1, 6, 9, 8, …}

7 1

2

N U L L

N U L L

1

9

N U L L

N U L L

1

search(1, root) : 呼出 6

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

x 1 t

1 が入るのは、

7 の左部分木

search(1, t->left) : 呼出 7

if ( t == NULL ) {

t = (struct tree *)malloc(sizeof(struct tree));

t->key = x; t->count = 1;

t->left = NULL; t->right = NULL;

}

else if ( x < t->key )

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

else if ( x > t->key )

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

else

(t->count)++;

return (t);

x 1 t

1 が入るのは、

2 の左部分木

参照

今ダウンロードする ( PPTX - 68 ページ - 362.48 KB )

関連したドキュメント

Release Bulletin for PowerBuilder 2017 R2 - PowerBuilder® 2017 R2

PowerSever ( PB Edition ) は、 Appeon PowerBuilder 2017 R2 日本語版 Universal Edition で提供される PowerServer を示しており、 .NET IIS

Release Bulletin for InfoMaker 2017 R2 - InfoMaker® 2017 R2

Appeon and other Appeon products and services mentioned herein as well as their respective logos are trademarks or registered trademarks of Appeon Limited.. SAP and other SAP

EliBagnoandMordechaiNovickSLC78,March28,2017 G ( r , r , n ) Alengthfunctionforthecomplexreflectiongroup

There is a bijection between left cosets of S n in the affine group and certain types of partitions (see Bjorner and Brenti (1996) and Eriksson and Eriksson (1998)).. In B-B,

We cannot use LAN in the hall

“Breuil-M´ezard conjecture and modularity lifting for potentially semistable deformations after

逮 捕 に 伴 う 搜 索 ・ 押 収 の 法 理 と 携 帯 電 話 内 デ ー タ の 捜 索

California （スマートフォンの搜索の事案） と、 United States v...

幸せの探求

エッジワースの単純化は次のよう な仮定だった。すなわち「すべて の人間は快楽機械である」という

第１回東京都北区資源循環推進審議会 議事録

○○でございます。私どもはもともと工場協会という形で活動していたのですけれども、要

１ 風致地区のあらまし

り、高さ３ｍ以上の高木 1 本、高さ１ｍ以上の中木２ 本、低木 15