Sett12
Fra Hiofwiki
Innhold |
Gruppe N
// Med lettere kopiering av noen oppgaver fra andre, samt litt peaking på google og i boka :-)
Oppgave 1
Ta utgangspunkt i følgende AVL-tre med verdiene 1,2,3,...,10:
4
/ \
/ \
2 8
/ \ / \
1 3 6 9
/ \ \
5 7 10
Etter innsetting (i denne rekkefølgen) av verdiene 11,12,13,...,20:
==>11:
4
/ \
/ \
2 8
/ \ / \
/ \ / \
1 3 6 9
/ \ / \
5 7 10 11
==>12:
8
/ \
/ \
4 9
/ \ / \
/ \ / \
2 6 10 11
/ \ / \ \
1 3 5 7 12
==>13:
8
/ \
/ \
4 9
/ \ / \
/ \ / \
2 6 10 12
/ \ / \ / \
1 3 5 7 11 13
==>14:
8
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
2 6 10 13
/ \ / \ / \ \
1 3 5 7 9 11 14
==>15:
8
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 11 9 13 15
==>16:
8
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
2 6 11 14
/ \ / \ / \ / \
1 3 5 7 9 10 13 15
\
16
==>17:
8
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
2 6 11 14
/ \ / \ / \ / \
1 3 5 7 9 10 13 16
/ \
15 17
==>18:
8
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
2 6 11 16
/ \ / \ / \ / \
1 3 5 7 9 10 14 17
/ \ \
13 15 18
==>19:
8
/ \
/ \
/ \
4 12
/ \ / \
/ \ / \
2 6 11 16
/ \ / \ / \ / \
1 3 5 7 9 10 14 18
/ \ / \
13 15 17 19
==> 20:
8
/ \
/ \
/ \
4 16
/ \ / \
/ \ / \
2 6 12 18
/ \ / \ / \ / \
1 3 5 7 10 14 17 19
/ \ / \ \
9 11 13 15 20
Oppgave 2
Ta utgangspunkt i følgende AVL-tre:
30
/ \
/ \
20 70
/ \ / \
10 25 50 80
/ \
40 60
Vis hvordan treet blir seende ut ved innsetting av følgende tall:
45 55 65 75
Hver av disse innsettingene skal gjøres i det opprinnelige treet som er "tegnet" ovenfor.
==>45:
30
/ \
/ \
20 50
/ \ / \
10 25 40 70
/ / \
45 60 80
==>55:
50
/ \
/ \
30 70
/ \ / \
20 40 60 80
/ \ /
10 25 55
==>65:
30
/ \
/ \
20 60
/ \ / \
10 25 50 80
/ / \
40 65 80
==>75:
30
/ \
/ \
20 70
/ \ / \
10 25 50 80
/ \ /
40 60 75
Oppgave 3
Følgende AVL-tre er gitt:
30
/ \
/ \
20 50
/ / \
10 40 60
\ \
45 70
Ta utgangspunkt i dette treet og tegn hvordan det blir etter innlegging av verdiene: (i) 75 og deretter 80 (ii) 75 og deretter 65 (iii) 75, 35 og 47 (iv) 75, 35 og 32
(i) 75 og deretter 80
30
/ \
/ \
20 50
/ / \
10 40 70
\ / \
45 60 75
50
/ \
/ \
30 70
/ \ / \
20 40 60 75
/ \ \
10 45 80
(ii) 75 og deretter 65
30
/ \
/ \
20 50
/ / \
10 40 70
\ / \
45 60 75
50
/ \
/ \
30 70
/ \ / \
20 40 60 75
/ \ \
10 45 65
(iii) 75, 35 og 47
30
/ \
/ \
20 50
/ / \
10 40 70
\ / \
45 60 75
30
/ \
/ \
20 50
/ / \
10 40 70
/ \ / \
35 45 60 75
40
/ \
/ \
30 50
/ \ / \
20 35 45 70
/ \ / \
10 47 60 75
(iv) 75, 35 og 32
30
/ \
/ \
20 50
/ / \
10 40 70
\ / \
45 60 75
30
/ \
/ \
20 50
/ / \
10 40 70
/ \ / \
35 45 60 75
40
/ \
/ \
30 50
/ \ / \
20 35 45 70
/ / / \
10 32 60 75
Oppgave 43
16.1
34
/ \
/ \
3|17 65
/ | \ / \
1 12 32 45 87
16.3
12 | 32 | 45
/ | | \
1|3 17 34 65|87
16.5
17 | 34
/ | \
1|3|11|12|15 19|23|32|33 39|45|47|55|65|67|87
