1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Come rappresentare tutti i membri della famiglia in un computer?

2
00:00:10,790 --> 00:00:12,390
Si potrebbe semplicemente usare una lista,

3
00:00:12,390 --> 00:00:14,400
ma c'è una chiara gerarchia qui.

4
00:00:14,400 --> 00:00:17,110
>> Diciamo che stiamo cominciando con la bisnonna, Alice.

5
00:00:17,110 --> 00:00:19,030
Ha 2 figli, Bob

6
00:00:19,030 --> 00:00:21,310
e tuo nonno, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ha 3 figli,

8
00:00:23,190 --> 00:00:26,730
tuo zio, Dave, tua zia, Eva, e tuo padre, Fred.

9
00:00:26,730 --> 00:00:28,750
Tu sei unico figlio di Fred.

10
00:00:28,750 --> 00:00:30,950
>> Perché organizzare i vostri familiari in questo modo

11
00:00:30,950 --> 00:00:34,010
essere migliore di rappresentazione semplice elenco?

12
00:00:34,010 --> 00:00:36,630
Una ragione è che questa struttura gerarchica,

13
00:00:36,630 --> 00:00:39,660
chiamato 'albero,' contiene più informazioni rispetto a un semplice elenco.

14
00:00:40,540 --> 00:00:43,520
Sappiamo che i rapporti familiari tra tutti

15
00:00:43,520 --> 00:00:45,440
solo esaminando l'albero.

16
00:00:45,440 --> 00:00:47,250
Inoltre, può accelerare

17
00:00:47,250 --> 00:00:50,010
look-up tempo tremendamente, se i dati vengono ordinati albero.

18
00:00:50,010 --> 00:00:53,850
>> Non si può trarre vantaggio da questa qui, ma staremo a vedere un esempio di questo al più presto.

19
00:00:53,850 --> 00:00:56,150
Ogni persona è rappresentata da un nodo sull'albero.

20
00:00:56,680 --> 00:00:58,370
I nodi possono avere nodi figlio

21
00:00:58,370 --> 00:01:00,350
così come un nodo padre.

22
00:01:00,350 --> 00:01:02,390
Questi sono i termini tecnici,

23
00:01:02,390 --> 00:01:05,220
anche quando si utilizzano alberi a cose oltre le famiglie.

24
00:01:05,220 --> 00:01:07,940
Nodo di Alice ha 2 figli e non dei genitori,

25
00:01:07,940 --> 00:01:11,500
mentre il nodo di Charlie ha 3 figli e 1 genitore.

26
00:01:11,500 --> 00:01:14,330
>> Un nodo foglia è uno che non ha figli

27
00:01:14,330 --> 00:01:16,410
sul bordo esterno della struttura.

28
00:01:16,410 --> 00:01:18,520
Il nodo più alto della struttura, il nodo radice,

29
00:01:18,520 --> 00:01:20,240
non ha padre.

30
00:01:20,240 --> 00:01:23,170
>> Un albero binario è un particolare tipo di albero,

31
00:01:23,170 --> 00:01:26,720
in cui ogni nodo ha al massimo 2 bambini.

32
00:01:26,720 --> 00:01:30,490
Ecco l'struct di un nodo di un albero binario in C.

33
00:01:31,560 --> 00:01:34,530
Ogni nodo ha alcuni dati associati

34
00:01:34,530 --> 00:01:36,520
e 2 puntatori ad altri nodi.

35
00:01:36,520 --> 00:01:38,110
>> Nel nostro albero genealogico,

36
00:01:38,110 --> 00:01:40,900
i dati associati era il nome di ogni persona.

37
00:01:40,900 --> 00:01:43,850
Qui è un int, anche se potrebbe essere qualsiasi cosa.

38
00:01:44,510 --> 00:01:46,200
Come si è visto,

39
00:01:46,200 --> 00:01:48,990
un albero binario non sarebbe una buona rappresentazione per una famiglia,

40
00:01:48,990 --> 00:01:51,960
poiché le persone hanno spesso più di 2 bambini.

41
00:01:51,960 --> 00:01:53,510
>> Un albero binario di ricerca

42
00:01:53,510 --> 00:01:56,380
è uno speciale tipo di albero binario ordinato

43
00:01:56,380 --> 00:01:58,090
che ci permette di guardare rapidamente i valori.

44
00:01:58,740 --> 00:02:00,050
Avrete notato

45
00:02:00,050 --> 00:02:02,010
che ogni nodo sotto la radice di un albero

46
00:02:02,010 --> 00:02:04,620
è la radice di un altro albero, chiamato 'sottoalbero.'

47
00:02:04,960 --> 00:02:07,090
Qui, la radice dell'albero è 6,

48
00:02:07,090 --> 00:02:09,860
e il suo bambino, 2, è la radice di un sottoalbero.

49
00:02:09,860 --> 00:02:11,870
>> In un albero binario di ricerca

50
00:02:11,870 --> 00:02:15,790
tutti i valori di un nodo è sottoalbero destro

51
00:02:15,790 --> 00:02:18,690
è maggiore del valore del nodo. Qui: 6.

52
00:02:18,690 --> 00:02:22,640
Beh, i valori in sottoalbero sinistro di un nodo

53
00:02:24,540 --> 00:02:26,890
sono inferiori al valore del nodo.

54
00:02:26,890 --> 00:02:28,620
Se abbiamo bisogno di gestire i valori duplicati,

55
00:02:28,620 --> 00:02:31,760
possiamo cambiare uno di questi per una disuguaglianza sciolto,

56
00:02:31,760 --> 00:02:34,410
il che significa valori identici può cadere sia a sinistra oa destra,

57
00:02:34,410 --> 00:02:37,400
fintanto che siamo coerenti su di esso tutta.

58
00:02:37,400 --> 00:02:39,620
Questo albero è un albero binario di ricerca

59
00:02:39,620 --> 00:02:41,540
perché segue queste regole.

60
00:02:42,320 --> 00:02:46,020
>> Ecco come sarebbero se ci siamo rivolti tutti i nodi in strutture C.

61
00:02:46,880 --> 00:02:48,410
Si noti che se un bambino non è presente,

62
00:02:48,410 --> 00:02:50,340
il puntatore è nullo.

63
00:02:50,340 --> 00:02:53,270
Come si fa a verificare se 7 è nella struttura?

64
00:02:53,270 --> 00:02:55,020
Partiamo alla radice.

65
00:02:55,020 --> 00:02:58,690
Seven è superiore a 6, quindi se è nella struttura, deve essere a destra.

66
00:02:59,680 --> 00:03:03,650
Poi, è inferiore a 8, quindi deve essere lasciato.

67
00:03:03,650 --> 00:03:06,210
Qui, abbiamo trovato 7.

68
00:03:06,210 --> 00:03:08,160
Ora, controlleremo per 5.

69
00:03:08,160 --> 00:03:11,500
Five è minore di 6, quindi deve essere a sinistra.

70
00:03:11,500 --> 00:03:13,460
Cinque è maggiore di 2,

71
00:03:13,460 --> 00:03:15,010
quindi deve essere giusto,

72
00:03:15,010 --> 00:03:18,100
ed è anche superiore a 4, quindi deve essere di nuovo a destra.

73
00:03:18,100 --> 00:03:20,300
Tuttavia, non c'è bambino qui.

74
00:03:20,300 --> 00:03:22,000
Il puntatore è nullo.

75
00:03:22,000 --> 00:03:24,270
Questo significa che 5 non è in nostro albero.

76
00:03:24,270 --> 00:03:27,250
>> Siamo in grado di cercare l'albero binario con il seguente codice:

77
00:03:28,430 --> 00:03:31,140
Ad ogni nodo, controlliamo per vedere se abbiamo trovato

78
00:03:31,140 --> 00:03:33,020
il valore che stiamo cercando.

79
00:03:33,020 --> 00:03:35,740
Se non lo trovi, si determina se deve essere

80
00:03:35,740 --> 00:03:38,990
sulla sinistra o destra e verificare che sottoalbero.

81
00:03:38,990 --> 00:03:41,160
Questo ciclo continuerà l'albero

82
00:03:41,160 --> 00:03:44,190
finché non vi è il nodo figlio sinistro o destro.

83
00:03:45,190 --> 00:03:48,600
>> Ricordate che 5 non era nella struttura.

84
00:03:48,600 --> 00:03:50,460
Come lo inseriamo?

85
00:03:50,460 --> 00:03:52,370
Il processo è simile alla ricerca.

86
00:03:52,370 --> 00:03:54,830
Abbiamo scorrere verso il basso l'albero a partire da 6,

87
00:03:54,830 --> 00:03:57,040
sinistra a 2,

88
00:03:57,040 --> 00:03:59,140
diritto a 4,

89
00:03:59,140 --> 00:04:02,500
e di nuovo a destra, ma 4 non ha figli da questa parte.

90
00:04:02,500 --> 00:04:06,090
Questa sarà la nuova posizione per 5,

91
00:04:06,090 --> 00:04:08,500
e si inizia senza figli.

92
00:04:09,020 --> 00:04:12,220
>> Qual è la velocità di operazioni su un albero binario di ricerca?

93
00:04:12,220 --> 00:04:15,410
Ricordare che Bigohnotation cerca di fornire un limite superiore.

94
00:04:15,410 --> 00:04:17,390
Nel caso peggiore,

95
00:04:17,390 --> 00:04:19,480
il nostro albero potrebbe essere semplicemente una lista concatenata

96
00:04:19,480 --> 00:04:22,220
il che significa che l'inserimento, cancellazione e ricerca

97
00:04:22,220 --> 00:04:25,380
potrebbe richiedere tempo proporzionale al numero di nodi dell'albero.

98
00:04:25,380 --> 00:04:27,380
Questo è O (n).

99
00:04:27,380 --> 00:04:30,690
>> Ad esempio, la seguente è una valida albero binario di ricerca.

100
00:04:31,850 --> 00:04:34,020
Tuttavia, se cerchiamo di trovare 9,

101
00:04:34,020 --> 00:04:36,760
dobbiamo attraversare ogni nodo.

102
00:04:36,760 --> 00:04:39,120
E non è migliore di una lista concatenata.

103
00:04:39,120 --> 00:04:41,410
Idealmente, vorremmo tutti i nodi

104
00:04:41,410 --> 00:04:44,120
del nostro albero binario di ricerca di avere 2 bambini.

105
00:04:44,120 --> 00:04:46,370
In questo modo, inserimento, cancellazione e ricerca

106
00:04:46,370 --> 00:04:50,190
avrebbe preso, nella peggiore delle ipotesi, O (log n).

107
00:04:50,190 --> 00:04:52,470
L'albero di prima potrebbe essere più equilibrata,

108
00:04:52,470 --> 00:04:54,140
come questo.

109
00:04:54,140 --> 00:04:57,980
Ora, guardando a qualsiasi valore ha, al massimo, 3 gradini.

110
00:04:57,980 --> 00:04:59,460
Questo albero è bilanciato,

111
00:04:59,460 --> 00:05:01,190
significato che è ha una profondità minima

112
00:05:01,190 --> 00:05:03,680
rispetto al numero di nodi.

113
00:05:03,680 --> 00:05:06,300
>> Alla ricerca di un valore in un albero binario di ricerca bilanciato

114
00:05:06,300 --> 00:05:09,540
è simile alla ricerca binaria su un array ordinato.

115
00:05:09,540 --> 00:05:12,290
Infatti, se non abbiamo bisogno di inserire o eliminare elementi,

116
00:05:12,290 --> 00:05:15,150
si comportano allo stesso modo.

117
00:05:15,150 --> 00:05:17,600
Tuttavia, una struttura ad albero è meglio

118
00:05:17,600 --> 00:05:19,530
per gli inserimenti di movimentazione ed eliminazioni

119
00:05:20,360 --> 00:05:22,670
>> Il mio nome è Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Questo è CS50.