Løsningsforslag uke 16, oppgavesett 12
Fra Hiofwiki
Oppgaver til uke 16 -- AVL-trær og B-trær Oppgave 1 - Insetting i AVL-trær 1.Ta utgangpunkt i følgende AVL-tre med verdiene 1,2,3,...,10:
4
/ \
/ \
2 8
/ \ / \
1 3 6 9
/ \ \
5 7 10
Tegn hvordan treet blir seende ut etter innsetting (i denne rekkefølgen) av verdiene 11,12,13,...,20. (11)
4
/ \
/ \
2 8
/ \ / \
1 3 6 9
/ \ \
5 7 10
\
11
8
/ \
/ \
4 9
/ \ \
/ \ \
2 6 10
/ \ / \ \
1 3 5 7 11
8
/ \
/ \
/ \
4 10
/ \ / \
2 6 9 11
/ \ / \
1 3 5 7
(12)
8
/ \
/ \
/ \
4 10
/ \ / \
2 6 9 11
/ \ / \ \
1 3 5 7 12
(13)
8
/ \
/ \
/ \
4 10
/ \ / \
2 6 9 11
/ \ / \ \
1 3 5 7 12
\
13
8
/ \
/ \
/ \
4 10
/ \ / \
2 6 9 12
/ \ / \ / \
1 3 5 7 11 13
(14)
8
/ \
/ \
/ \
4 10
/ \ / \
2 6 9 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 13
/ \ / \ / \ \
1 3 5 7 9 11 14
\
15
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
(16)
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
\
16
(17)
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
\
16
\
17
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 16
/ \
15 17
(18)
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 16
/ \
15 17
\
18
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 16
/ \ / \ / \ / \
1 3 5 7 9 11 14 17
/ \ \
13 15 18
(19)
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 16
/ \ / \ / \ / \
1 3 5 7 9 11 14 17
/ \ \
13 15 18
\
19
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 16
/ \ / \ / \ / \
1 3 5 7 9 11 14 18
/ \ / \
13 15 17 19
(20)
8
/ \
/ \
/ \
4 12
/ \ / \
2 6 10 16
/ \ / \ / \ / \
1 3 5 7 9 11 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
2.Ta utgangpunkt 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 70
/ \ / \
10 25 50 80
/ \
40 60
\
45
30
/ \
/ \
20 50
/ \ / \
10 25 40 70
\ \
60 80
/
45
50
/ \
/ \
30 70
/ \ \
20 40 80
/ \ \
10 25 60
/
45
50
/ \
/ \
30 70
/ \ \
20 60 80
/ \ \
10 25 40
\
45
50
/ \
/ \
60 70
/ \
30 80
/ \
20 40
/ \ \
10 25 45
60
/ \
/ \
30 70
/ \ \
20 40 80
/ \ \
10 25 45
(55)
60
/ \
/ \
30 70
/ \ \
20 40 80
/ \ \
10 25 45
\
55
60
/ \
/ \
40 70
/ \ \
30 45 80
/ \
20 55
/ \
10 25
40
/ \
/ \
30 60
/ / \
20 45 70
/ \ \ \
10 25 55 80
40
/ \
/ \
20 60
/ \ / \
10 30 45 70
/ \ \
25 55 80
(65)
40
/ \
/ \
20 60
/ \ / \
10 30 45 70
/ \ / \
25 55 65 80
(75)
40
/ \
/ \
20 60
/ \ / \
10 30 45 70
/ \ / \
25 55 65 80
/
75
60
/ \
/ \
40 70
/ \ / \
20 45 65 80
/ \ \ /
10 30 55 75
/
25
3.Følgende AVL-tre er gitt:
30
/ \
/ \
20 50
/ / \
10 40 60
\ \
45 70
Ta utgangpunkt i dette treet og tegn hvordan det blir etter innlegging av verdiene: (i) 75 og deretter 80 (ii) 75 og deretter 65 (ii) 75, 35 og 47 (iv) 75, 35 og 32
(i,ii,iii,iv) (75)
30
/ \
/ \
20 50
/ / \
10 40 60
\ \
45 70
\
75
30
/ \
/ \
20 50
/ / \
10 40 70
\ / \
45 60 75
(i)(80)
30
/ \
/ \
20 50
/ / \
10 40 70
\ / \
45 60 75
\
80
50
/ \
/ \
30 70
/ \ / \
20 40 60 75
/ \ \
10 45 80
(ii)(35)
30
/ \
/ \
20 50
/ / \
10 40 70
/ \ / \
35 45 60 75
(ii)(47)
30
/ \
/ \
20 50
/ / \
10 40 70
/ \ / \
35 45 60 75
\
47
50
/ \
/ \
30 70
/ \ / \
20 40 60 75
/ / \
10 35 45
\
47
50
/ \
/ \
40 70
/ \ / \
30 45 60 75
/ / \
20 35 47
/
10
40
/ \
/ \
30 50
/ \ / \
20 35 45 70
/ \ / \
10 47 60 75
(iii)(65)
30
/ \
/ \
20 50
/ / \
10 40 70
\ / \
45 60 75
/
65
30
/ \
/ \
20 70
/ / \
10 50 75
/ \
40 60
\ \
45 65
70
/ \
/ \
30 75
/ \
20 50
/ / \
10 40 60
\ \
45 65
70
/ \
/ \
50 75
/ \
30 60
/ \ \
20 40 65
/ \
10 45
50
/ \
/ \
30 70
/ \ / \
20 40 60 75
/ \ \
10 45 65
(iv)(35)
30
/ \
/ \
20 50
/ / \
10 40 70
/ \ / \
35 45 60 75
(32)
30
/ \
/ \
20 50
/ / \
10 40 70
/ \ / \
35 45 60 75
/
32
50
/ \
/ \
30 70
/ \ / \
20 40 60 75
/ / \
10 35 45
/
32
50
/ \
/ \
40 70
/ \ / \
30 45 60 75
/ \
20 35
/ /
10 32
40
/ \
/ \
30 50
/ \ \
20 45 70
/ / / \
10 35 60 75
/
32
40
/ \
/ \
30 50
/ \ \
20 35 70
/ / \ / \
10 32 45 60 75
40
/ \
/ \
30 70
/\ /\
20 35 50 75
/ / \ \
10 32 45 60
4.For n=1,2,... (og så lenge du orker) tegn et AVL tre med n noder som er slik at ingen AVL trær med de samme verdiene har større dybde. Sammenlign dybden til dette "verst mulige" AVL-treet med verdiene til 1.45*log(n).
Oppgave 2 - Sjekking av om binære trær er AVL-trær
Lag en rekursiv metode:
boolean erAVL(node rot);
som sjekker om et vanlig binært tre oppfyller balansekravene til et AVL-tre. Bruk et enkelt tre der data i nodene bare er et heltall.
public boolean erAVL(node rot) {
boolean ret = true;
try {
rot.heightBalenced(rot);
} catch (Exception e) {
ret = false;
}
return ret;
}
int heightBalenced(node rot) throws Exception{
int lb = 0, rb =0;
if (rot.left!=null) lb = heightBalenced(rot.left) +1;
if (rot.right!=null) rb = heightBalenced(rot.right) +1;
if ((lb-rb)!=0&&(lb-rb)!=-1&&(lb-rb)!=1)
throw new Exception("Unbalanced tree, element " + rot.element + " should not be " + (rb - lb));
if (lb>rb) return lb;
return rb;
}
Bruker følgende som node
public class node<T> {
protected T element;
protected node<T> left, right;
node (T obj){
element = obj;
left = null;
right = null;
}
}
Oppgave 3 - B-trær Fra lærebokas "Excersises" til kapittel 16: Oppgavene 16.1, 16.3 og 16.5. 16.1
32
/ \
/ \
3 65
/ \ / \
1 12,17 34,45 87
16,3
12,34
/ | \
/ | \
1,3 17,32 45,65,87
16,5
17,34
/ | \
/ | \
/ | \
1,3,11,12,15,17 19,23,32,33 39,45,47,,55,65,67,87
