0
0
1
1
1
0
0110
Gli alberi binari sono contenitori efficienti
0
0
1
1
1
0
0110
Da notare la ricorsione:
quello che si fa
per 0110
lo si ripete per 110
MARIO
SANDRA
ELISA
VALERIO
BRUNO
FABIO
CARLO
ANDREA
FILIPPO
EMILIA
ALBERTO
ANNA
PAOLO
DANIELA
FRANCO
MINO
ROBERTO
NICOLA
MICHELE
ALBERO BINARIO DI RICERCA
STEFANO
UGO
ELENA
MARIO
SANDRA
ELISA
VALERIO
BRUNO
FABIO
CARLO
ANDREA
FILIPPO
EMILIA
ALBERTO
ANNA
PAOLO
DANIELA
FRANCO
MINO
ROBERTO
NICOLA
MICHELE
ALBERO BINARIO DI RICERCA
STEFANO
UGO
MARIO
ELENA
SANDRA
ELISA
VALERIO
BRUNO
FABIO
CARLO
ANDREA
FILIPPO
EMILIA
ALBERTO
ANNA
PAOLO
DANIELA
FRANCO
MINO
ROBERTO
NICOLA
MICHELE
ALBERO BINARIO DI RICERCA
STEFANO
UGO
MARIO
SANDRA
ELISA
ELENA
VALERIO
BRUNO
FABIO
CARLO
ANDREA
FILIPPO
EMILIA
ALBERTO
ANNA
PAOLO
DANIELA
FRANCO
MINO
ROBERTO
NICOLA
MICHELE
ALBERO BINARIO DI RICERCA
STEFANO
UGO
MARIO
SANDRA
ELISA
VALERIO
BRUNO
FABIO
PAOLO
ELENA
CARLO
ANDREA
FILIPPO
EMILIA
ALBERTO
ANNA
DANIELA
FRANCO
MINO
ROBERTO
NICOLA
MICHELE
ALBERO BINARIO DI RICERCA
STEFANO
UGO
MARIO
SANDRA
ELISA
VALERIO
BRUNO
FABIO
CARLO
ANDREA
PAOLO
FILIPPO
EMILIA
MINO
ROBERTO
STEFANO
ELENA
ALBERTO
ANNA
DANIELA
FRANCO
NICOLA
MICHELE
ALBERO BINARIO DI RICERCA
UGO
MARIO
SANDRA
ELISA
VALERIO
BRUNO
FABIO
CARLO
ANDREA
FILIPPO
EMILIA
DANIELA
ALBERTO
PAOLO
ANNA
FRANCO
MINO
ROBERTO
NICOLA
MICHELE
ELENA
ALBERO BINARIO DI RICERCA
STEFANO
UGO
F
R
F
E
E
E
H
T
M
H
M
B
C
B
N
Z
P
B
B
B
P
F
R
F
E
E
E
H
T
M
H
M
B
C
B
N
Z
P
B
B
B
P
Dati n giocatori, come costruire il tabellone ?
Dati n giocatori, quante sono le partite ?
Disponendo di molti campi, quanto dura il torneo ?
Disponendo di m campi, quanto dura il torneo ?
Dati n giocatori, quante sono le partite ?
trovare un invariante
per ogni partita c’è una vittoria e una sconfitta
ogni giocatore (tranne il vincitore del torneo) perde esattamente una volta
il numero di partite è uno meno del numero di giocatori
F
R
foglie = giocatori
F
E
nodi interni = partite
E
E
H
T
M
# nodi interni =
# foglie - 1
H
M
B
C
B
N
Z
P
B
B
B
P
e le vittorie come sono distribuite ?
esiste una qualche regolarità o no?
il vincitore vince sempre
c’è qualcuno che non vince mai (cioè gioca una sola volta e perde)?
vittorie
partite =
esattamente uno?
almeno uno che non vince esiste
A
B
B
C
C
D
D
E
E
e le vittorie come sono distribuite ?
esiste una qualche regolarità o no?
il vincitore vince sempre
c’è qualcuno che non vince mai (cioè gioca una sola volta e perde)?
vittorie
partite =
nessuno vince (tranne uno)
A
A
B
A
C
A
D
A
E
data una distribuzione arbitraria di vittorie, esiste un tabellone che la rappresenta ?
7 vittorie in totale
8 giocatori
A, B - 3 vittorie; C - 1 vittoria; D, E, F, G, H 0 vittorie
A
A
A
A
A
B
C
A
D
D
C
B
A
C
F
F
G
H
B
C
A
E
E
C
D
A
B
E
F
B
B
G
G
H
B
B
H
B
Disponendo di molti campi, quanto dura il torneo ?
7+11+5+13+6+8+4+10+9+15+12+6+8+16
7
11
5
13
6
8
4
10
9
15
12
6
18
36
18
64
14
28
14
130
24
42
18
66
8
24
16
tempo logaritmico
con sufficienti processori
35
19
22
7
17
21
10
9
15
3
6
6 1 8 1 7 9 2 2 5 6 3
8
12
19
22
7
17
21
10
9
15
3
6
6 1 8 1 7 9 2 2 5 6 3
Rimozione del massimo
8
12 7
4
3
19
22
7
17
21
10
9
15
3
6
6 1 8 1 7 9 2 2 5 6
Rimozione del massimo
8
12 7
4
22
19
3
7
17
21
10
9
15
3
6
6 1 8 1 7 9 2 2 5 6
Rimozione del massimo
8
12 7
4
22
19
21
7
17
3
10
9
15
3
6
6 1 8 1 7 9 2 2 5 6
Rimozione del massimo
8
12 7
4
22
19
21
10
7
17
15
9
3
3
6
6 1 8 1 7 9 2 2 5 6
Rimozione del massimo
8
12 7
4
22
19
21
10
7
17
15
9
9
3
6
8
12 7
4
6 1 8 1 7 3 2 2 5 6
Rimozione del massimo
costo log n
35
19
22
7
17
21
10
9
15
3
6
8
12 7
6 1 8 1 7 9 2 2 5 6 3 18
Aggiungere un elemento
4
35
19
22
7
17
21
10
9
15
3
6
8
18 7
6 1 8 1 7 9 2 2 5 6 3 12
Aggiungere un elemento
4
35
19
22
7
18
21
10
9
15
3
6
8
17 7
4
6 1 8 1 7 9 2 2 5 6 3 12
Aggiungere un elemento
costo log n
22
19
21
10
7
17
15
9
9
3
6
6 1 8 1 7 3 2 2 5 6
35
8
12 7
4
19
21
10
7
17
15
9
9
3
6
6 1 8 1 7 3 2 2 5 6
35
22
8
12 7
4
6
19
21
10
7
17
15
9
9
3
6
6 1 8 1 7 3 2 2 5
35
22
8
12 7
4
21
19
6
10
7
17
15
9
9
3
6
6 1 8 1 7 3 2 2 5
35
22
8
12 7
4
21
19
15
7
17
6
10
9
9
3
6
6 1 8 1 7 3 2 2 5
35
22
8
12 7
4
21
19
15
9
10
7
9
6
17
3
6
6 1 8 1 7 3 2 2 5
35
22
8
12 7
4
21
19
15
9
10
7
9
7
17
3
6
6 1 8 1 6 3 2 2 5
35
22
8
12 7
4
5
19
15
9
10
7
9
7
17
3
6 1 8 1 6 3 2 2
35
22
21
6
8
12 7
4
19
15
5
9
10
7
9
7
17
3
6 1 8 1 6 3 2 2
35
22
21
6
8
12 7
4
19
15
17
10
7
5
9
9
7
3
6 1 8 1 6 3 2 2
35
22
21
6
8
12 7
4
19
15
17
9
10
7
9
7
12
3
6 1 8 1 6 3 2 2
35
22
21
6
8
5
7
4
alberi genealogici
padre
nonno
madre
nonna
nonno
nonna
piccolo conto
3 generazioni per secolo
30 generazioni fino all’anno 1000
un miliardo !
non esistevano tanti abitanti
?
1) molti antenati sono la stessa persona
2) abbiamo tutti antenati comuni
A
B
C
D
E
G
H
I
J
K
M
N
F
A
B
C
D
E
F
G
H
I
L
M
Codice Morse (apparentemente) binario
A
B
C
D
E
F
G
H
I
J
K
L
M
01
1000
1010
100
0
0010
110
0000
00
0111
101
0100
11
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
10
111
0110
1101
010
000
1
001
0001
011
1001
1011
1100
Codice Morse (apparentemente) binario
A
B
C
D
E
F
G
H
I
J
K
L
M
01
1000
1010
100
0
0010
110
0000
00
0111
101
0100
11
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
10
111
0110
1101
010
000
1
001
0001
011
1001
1011
1100
Codice Morse (apparentemente) binario
A
B
C
D
E
F
G
H
I
J
K
L
M
01
1000
1010
100
0
0010
110
0000
00
0111
101
0100
11
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
10
111
0110
1101
010
000
1
001
0001
011
1001
1011
1100
Codice Morse (apparentemente) binario
A
B
C
D
E
F
G
H
I
J
K
L
M
01
1000
1010
100
0
0010
110
0000
00
0111
101
0100
11
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
10
111
0110
1101
010
000
1
001
0001
011
1001
1011
1100
Codice Morse (apparentemente) binario
A
B
C
D
E
F
G
H
I
J
K
L
M
01
1000
1010
100
0
0010
110
0000
00
0111
101
0100
11
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
10
111
0110
1101
010
000
1
001
0001
011
1001
1011
1100
arrivo domani
01010010000001111 10011111011000
0101001000000111110011111011000
entelesomitongi
00
011
0100
0101
100
110
1010 1011
010100100000011111001111101100
111
Codice di Huffman
a
e
m
p
r
t
z
16
25
12
6
10
8
2
Codice di Huffman
a
e
m
p
r
t
z
16
25
12
6
10
8
2
minimi
z
p
Codice di Huffman
a
e
m
(pz)
r
t
16
25
12
8
10
8
minimi
t
z
p
Codice di Huffman
a
e
m
(pzt)
r
16
25
12
16
10
minimi
t
z
p
m
r
Codice di Huffman
a
e
(mr)
(pzt)
16
25
22
16
minimi
a
t
z
p
m
r
Codice di Huffman
(apzt)
e
(mr)
32
25
22
minimi
a
e
t
z
p
m
r
Codice di Huffman
(apzt)
(emr)
a
e
m
p
r
t
z
32
47
a
16
25
12
6
10
8
2
e
t
z
p
m
r
00
11
100
0101
101
011
0100