1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Com representar tots els membres de la seva família en un ordinador?

2
00:00:10,790 --> 00:00:12,390
Podríem simplement utilitzar una llista,

3
00:00:12,390 --> 00:00:14,400
però hi ha una jerarquia clara aquí.

4
00:00:14,400 --> 00:00:17,110
>> Diguem que estem començant amb la seva besàvia, Alice.

5
00:00:17,110 --> 00:00:19,030
Té 2 fills, Bob

6
00:00:19,030 --> 00:00:21,310
i el seu avi, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie té 3 fills,

8
00:00:23,190 --> 00:00:26,730
seu oncle, Dave, la seva tia, Eva i el seu pare, Fred.

9
00:00:26,730 --> 00:00:28,750
Vostè és fill únic de Fred.

10
00:00:28,750 --> 00:00:30,950
>> Per què l'organització dels membres de la família d'aquesta manera

11
00:00:30,950 --> 00:00:34,010
ser millor que la representació simple llista?

12
00:00:34,010 --> 00:00:36,630
Una raó és que aquesta estructura jeràrquica,

13
00:00:36,630 --> 00:00:39,660
anomenat un "arbre", conté més informació que una simple llista.

14
00:00:40,540 --> 00:00:43,520
Sabem que les relacions familiars entre tots

15
00:00:43,520 --> 00:00:45,440
simplement mitjançant l'examen de l'arbre.

16
00:00:45,440 --> 00:00:47,250
A més, es pot accelerar

17
00:00:47,250 --> 00:00:50,010
look-up temps tremendament, si les dades de l'arbre està ordenat.

18
00:00:50,010 --> 00:00:53,850
>> No podem prendre avantatge d'això aquí, però anem a veure un exemple d'això aviat.

19
00:00:53,850 --> 00:00:56,150
Cada persona està representat per un node a l'arbre.

20
00:00:56,680 --> 00:00:58,370
Els nodes poden tenir nodes secundaris

21
00:00:58,370 --> 00:01:00,350
així com un node pare.

22
00:01:00,350 --> 00:01:02,390
Aquests són els termes tècnics,

23
00:01:02,390 --> 00:01:05,220
fins i tot quan s'utilitzen els arbres per coses més de les famílies.

24
00:01:05,220 --> 00:01:07,940
Node d'Alicia té 2 fills i els pares no,

25
00:01:07,940 --> 00:01:11,500
mentre que el node de Charlie té 3 fills i els pares 1.

26
00:01:11,500 --> 00:01:14,330
>> Un node fulla és un que no té fills

27
00:01:14,330 --> 00:01:16,410
en la vora exterior de l'arbre.

28
00:01:16,410 --> 00:01:18,520
El node superior de l'arbre, el node arrel,

29
00:01:18,520 --> 00:01:20,240
no té pare.

30
00:01:20,240 --> 00:01:23,170
>> Un arbre binari és un tipus específic d'arbre,

31
00:01:23,170 --> 00:01:26,720
en el qual cada node té, com a màxim, 2 nens.

32
00:01:26,720 --> 00:01:30,490
Aquí està l'estructura d'un node d'un arbre binari en C.

33
00:01:31,560 --> 00:01:34,530
Cada node té algunes dades associats amb ell

34
00:01:34,530 --> 00:01:36,520
i 2 punters a altres nodes.

35
00:01:36,520 --> 00:01:38,110
>> En el nostre arbre genealògic,

36
00:01:38,110 --> 00:01:40,900
les dades associades era el nom de cada persona.

37
00:01:40,900 --> 00:01:43,850
Aquí és un int, encara que podria ser qualsevol cosa.

38
00:01:44,510 --> 00:01:46,200
Doncs resulta que,

39
00:01:46,200 --> 00:01:48,990
un arbre binari no seria una bona representació per a una família,

40
00:01:48,990 --> 00:01:51,960
ja que les persones solen tenir més de 2 fills.

41
00:01:51,960 --> 00:01:53,510
>> Un arbre binari de cerca

42
00:01:53,510 --> 00:01:56,380
és un tipus especial d'arbre binari ordenat

43
00:01:56,380 --> 00:01:58,090
que ens permet veure els valors ràpidament.

44
00:01:58,740 --> 00:02:00,050
Vostè pot haver notat

45
00:02:00,050 --> 00:02:02,010
que tots els nodes per sota de l'arrel d'un arbre

46
00:02:02,010 --> 00:02:04,620
és l'arrel d'un altre arbre, anomenat 'subarbre.

47
00:02:04,960 --> 00:02:07,090
Aquí, l'arrel de l'arbre és 6,

48
00:02:07,090 --> 00:02:09,860
i el seu fill, 2, és l'arrel d'un subarbre.

49
00:02:09,860 --> 00:02:11,870
>> En un arbre de recerca binari

50
00:02:11,870 --> 00:02:15,790
tots els valors d'un node és el subarbre dret

51
00:02:15,790 --> 00:02:18,690
són més grans que el valor del node. A continuació: 6.

52
00:02:18,690 --> 00:02:22,640
Doncs bé, els valors de subarbre esquerre d'un node

53
00:02:24,540 --> 00:02:26,890
són menors que el valor del node.

54
00:02:26,890 --> 00:02:28,620
Si hem de manejar valors duplicats,

55
00:02:28,620 --> 00:02:31,760
podem canviar qualsevol d'ells a una desigualtat solt,

56
00:02:31,760 --> 00:02:34,410
el sentit de valors idèntics poden caure ja sigui en el costat esquerre o dret,

57
00:02:34,410 --> 00:02:37,400
sempre que siguin coherents sobre això en tot.

58
00:02:37,400 --> 00:02:39,620
Aquest arbre és un arbre de cerca binària

59
00:02:39,620 --> 00:02:41,540
perquè segueix la regla.

60
00:02:42,320 --> 00:02:46,020
>> Així és com es veuria si convertíssim tots els nodes en estructures de C.

61
00:02:46,880 --> 00:02:48,410
Tingueu en compte que si un nen està desaparegut,

62
00:02:48,410 --> 00:02:50,340
el punter és nul.

63
00:02:50,340 --> 00:02:53,270
Com comprovar si 7 es troba en l'arbre?

64
00:02:53,270 --> 00:02:55,020
Partim des de l'arrel.

65
00:02:55,020 --> 00:02:58,690
El set és més gran que 6, de manera que si està en l'arbre, ha d'estar a la dreta.

66
00:02:59,680 --> 00:03:03,650
Llavors, és menys de 8, de manera que ha de ser l'esquerra.

67
00:03:03,650 --> 00:03:06,210
Aquí, hem trobat 7.

68
00:03:06,210 --> 00:03:08,160
Ara, anem a comprovar per 5.

69
00:03:08,160 --> 00:03:11,500
Cinc és inferior a 6, pel que ha d'estar a l'esquerra.

70
00:03:11,500 --> 00:03:13,460
Cinc és major que 2,

71
00:03:13,460 --> 00:03:15,010
per la qual cosa ha de ser correcte,

72
00:03:15,010 --> 00:03:18,100
i també és major que 4, per la qual cosa ha de ser la dreta de nou.

73
00:03:18,100 --> 00:03:20,300
No obstant això, no hi ha un nen aquí.

74
00:03:20,300 --> 00:03:22,000
El punter és nul.

75
00:03:22,000 --> 00:03:24,270
Això vol dir que 5 no és al nostre arbre.

76
00:03:24,270 --> 00:03:27,250
>> Podem buscar a l'arbre binari amb el codi:

77
00:03:28,430 --> 00:03:31,140
A cada node, es comprova si s'ha trobat

78
00:03:31,140 --> 00:03:33,020
el valor que es busca.

79
00:03:33,020 --> 00:03:35,740
Si no el troba, es determina si ha de ser

80
00:03:35,740 --> 00:03:38,990
i en l'esquerra o la dreta comprovar subarbre.

81
00:03:38,990 --> 00:03:41,160
Aquest cicle continuarà l'arbre

82
00:03:41,160 --> 00:03:44,190
fins que no hi ha cap node fill a l'esquerra o la dreta.

83
00:03:45,190 --> 00:03:48,600
>> Recordi que 5 no estava en l'arbre.

84
00:03:48,600 --> 00:03:50,460
Com s'insereix?

85
00:03:50,460 --> 00:03:52,370
El procés és similar a recerca.

86
00:03:52,370 --> 00:03:54,830
Ens iterar l'arbre a partir de 6,

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

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

89
00:03:59,140 --> 00:04:02,500
ia la dreta de nou, però 4 no té fills en aquest costat.

90
00:04:02,500 --> 00:04:06,090
Aquesta serà la nova posició de 5,

91
00:04:06,090 --> 00:04:08,500
i s'iniciarà sense fills.

92
00:04:09,020 --> 00:04:12,220
>> A quina velocitat són operacions en un arbre de cerca binària?

93
00:04:12,220 --> 00:04:15,410
Recordi que Bigohnotation busca proporcionar un límit superior.

94
00:04:15,410 --> 00:04:17,390
En el pitjor dels casos,

95
00:04:17,390 --> 00:04:19,480
nostre arbre podria ser simplement una llista enllaçada

96
00:04:19,480 --> 00:04:22,220
el que significa que la inserció, deleció, i recerca

97
00:04:22,220 --> 00:04:25,380
podria prendre un temps proporcional al nombre de nodes en l'arbre.

98
00:04:25,380 --> 00:04:27,380
Això és O (n).

99
00:04:27,380 --> 00:04:30,690
>> Per exemple, el següent és un arbre binari de cerca vàlid.

100
00:04:31,850 --> 00:04:34,020
No obstant això, si tractem de trobar 9,

101
00:04:34,020 --> 00:04:36,760
hem de travessar cada node.

102
00:04:36,760 --> 00:04:39,120
No és més que una llista enllaçada.

103
00:04:39,120 --> 00:04:41,410
L'ideal seria que cada node

104
00:04:41,410 --> 00:04:44,120
del nostre arbre de cerca binària per tenir 2 fills.

105
00:04:44,120 --> 00:04:46,370
D'aquesta manera, inserció, eliminació i recerca

106
00:04:46,370 --> 00:04:50,190
prendria, en el pitjor, O (log n) temps.

107
00:04:50,190 --> 00:04:52,470
L'arbre de davant podria ser més equilibrada,

108
00:04:52,470 --> 00:04:54,140
com aquesta.

109
00:04:54,140 --> 00:04:57,980
Ara, mirant cap amunt pren qualsevol valor, com a màxim, 3 passos.

110
00:04:57,980 --> 00:04:59,460
Aquest arbre està equilibrat,

111
00:04:59,460 --> 00:05:01,190
significat que disposi d'un mínim de profunditat

112
00:05:01,190 --> 00:05:03,680
en relació amb el nombre de nodes.

113
00:05:03,680 --> 00:05:06,300
>> Busca un valor en un arbre binari de recerca equilibrat

114
00:05:06,300 --> 00:05:09,540
és similar a la recerca binària en un arranjament ordenat.

115
00:05:09,540 --> 00:05:12,290
De fet, si no és necessari inserir o eliminar elements,

116
00:05:12,290 --> 00:05:15,150
es comporten exactament de la mateixa manera.

117
00:05:15,150 --> 00:05:17,600
No obstant això, una estructura d'arbre és millor

118
00:05:17,600 --> 00:05:19,530
per les insercions i delecions de manipulació

119
00:05:20,360 --> 00:05:22,670
>> El meu nom és Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Això és CS50.