1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Cum ti-ar reprezenta toți membrii familiei dumneavoastră într-un calculator?

2
00:00:10,790 --> 00:00:12,390
Am putea folosi pur și simplu o listă,

3
00:00:12,390 --> 00:00:14,400
dar există o ierarhie clară aici.

4
00:00:14,400 --> 00:00:17,110
>> Să spunem că te începând cu stră-bunica, Alice.

5
00:00:17,110 --> 00:00:19,030
Ea are 2 fii, Bob

6
00:00:19,030 --> 00:00:21,310
și bunicul tău, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie are 3 copii,

8
00:00:23,190 --> 00:00:26,730
unchiul tău, Dave, mătușa ta, Eva, și tatăl tău, Fred.

9
00:00:26,730 --> 00:00:28,750
Sunteți singurul copil lui Fred.

10
00:00:28,750 --> 00:00:30,950
>> De ce ar fi organizarea de membrii familiei dumneavoastră în acest mod

11
00:00:30,950 --> 00:00:34,010
fi mai bine decât reprezentarea simplă listă?

12
00:00:34,010 --> 00:00:36,630
Unul dintre motive este faptul că această structură ierarhică,

13
00:00:36,630 --> 00:00:39,660
numit "copac," conține mai multe informații decât o simplă listă.

14
00:00:40,540 --> 00:00:43,520
Știm că relațiile familiale dintre toți

15
00:00:43,520 --> 00:00:45,440
doar prin examinarea copac.

16
00:00:45,440 --> 00:00:47,250
De asemenea, se poate accelera

17
00:00:47,250 --> 00:00:50,010
Look-up timp foarte mult, în cazul în care datele de arbori este sortat.

18
00:00:50,010 --> 00:00:53,850
>> Noi nu putem profita de asta aici, dar vom vedea un exemplu în acest sens în curând.

19
00:00:53,850 --> 00:00:56,150
Fiecare persoană este reprezentată de un nod în arbore.

20
00:00:56,680 --> 00:00:58,370
Nodurile pot avea noduri copilului

21
00:00:58,370 --> 00:01:00,350
precum și un nod parinte.

22
00:01:00,350 --> 00:01:02,390
Acestea sunt condițiile tehnice,

23
00:01:02,390 --> 00:01:05,220
chiar și atunci când se utilizează arbori de lucruri în afară de familii.

24
00:01:05,220 --> 00:01:07,940
Nod lui Alice are 2 copii si nici parintii,

25
00:01:07,940 --> 00:01:11,500
în timp ce nodul lui Charlie are 3 copii și 1-mamă.

26
00:01:11,500 --> 00:01:14,330
>> Un nod frunză este una care nu are nici un copil

27
00:01:14,330 --> 00:01:16,410
pe marginea exterioară a arborelui.

28
00:01:16,410 --> 00:01:18,520
Nodul cel mai important al arborelui, nodul rădăcină,

29
00:01:18,520 --> 00:01:20,240
nu are nici un părinte.

30
00:01:20,240 --> 00:01:23,170
>> Un arbore binar este un tip specific de copac,

31
00:01:23,170 --> 00:01:26,720
în care fiecare nod are, cel mult, 2 copii.

32
00:01:26,720 --> 00:01:30,490
Aici este struct de un nod al unui arbore binar în C.

33
00:01:31,560 --> 00:01:34,530
Fiecare nod are unele date asociate cu acesta

34
00:01:34,530 --> 00:01:36,520
și 2 pointeri la alte noduri.

35
00:01:36,520 --> 00:01:38,110
>> În arborele familiei noastre,

36
00:01:38,110 --> 00:01:40,900
datele asociate era numele fiecărei persoane.

37
00:01:40,900 --> 00:01:43,850
Aici este un int, deși ar putea fi orice.

38
00:01:44,510 --> 00:01:46,200
După cum se dovedește,

39
00:01:46,200 --> 00:01:48,990
un arbore binar nu ar fi o reprezentare buna pentru o familie,

40
00:01:48,990 --> 00:01:51,960
din moment ce oamenii au în mod frecvent mai mult de 2 copii.

41
00:01:51,960 --> 00:01:53,510
>> Un copac binar de căutare

42
00:01:53,510 --> 00:01:56,380
este un tip special, ordonată de arbore binar

43
00:01:56,380 --> 00:01:58,090
care ne permite sa se uite la valori mai repede.

44
00:01:58,740 --> 00:02:00,050
Este posibil să fi observat

45
00:02:00,050 --> 00:02:02,010
că fiecare nod sub rădăcina unui copac

46
00:02:02,010 --> 00:02:04,620
este rădăcina alt copac, numit "subarbore."

47
00:02:04,960 --> 00:02:07,090
Aici, rădăcina arborelui este de 6,

48
00:02:07,090 --> 00:02:09,860
și copilul său, 2, este rădăcina unui subarbore.

49
00:02:09,860 --> 00:02:11,870
>> Într-un arbore binar de căutare

50
00:02:11,870 --> 00:02:15,790
toate valorile unui nod e drept subarborele

51
00:02:15,790 --> 00:02:18,690
sunt mai mari decât valoarea nodului. Aici: 6.

52
00:02:18,690 --> 00:02:22,640
Ei bine, valorile din subarborele un nod de stânga

53
00:02:24,540 --> 00:02:26,890
sunt mai mici decât valoarea nodului.

54
00:02:26,890 --> 00:02:28,620
Dacă avem nevoie să se ocupe de valori dublură,

55
00:02:28,620 --> 00:02:31,760
putem schimba oricare dintre cele la o inegalitate în vrac,

56
00:02:31,760 --> 00:02:34,410
ceea ce înseamnă valori identice poate cădea fie pe stânga sau dreapta,

57
00:02:34,410 --> 00:02:37,400
atâta timp cât suntem consecvenți cu privire la aceasta de-a lungul.

58
00:02:37,400 --> 00:02:39,620
Acest arbore este un arbore binar de căutare

59
00:02:39,620 --> 00:02:41,540
deoarece urmează aceste reguli.

60
00:02:42,320 --> 00:02:46,020
>> Acesta este modul în care ar arăta dacă ne-am întors toate nodurile în struct C.

61
00:02:46,880 --> 00:02:48,410
Observați că, dacă un copil este dispărut,

62
00:02:48,410 --> 00:02:50,340
indicatorul este nul.

63
00:02:50,340 --> 00:02:53,270
Cum vom verifica pentru a vedea dacă 7 este în copac?

64
00:02:53,270 --> 00:02:55,020
Vom începe de la rădăcină.

65
00:02:55,020 --> 00:02:58,690
Șapte este mai mare de 6, așa că dacă e în copac, acesta trebuie să fie dreaptă.

66
00:02:59,680 --> 00:03:03,650
Apoi, aceasta este mai mică de 8, așa că trebuie să fie lăsat.

67
00:03:03,650 --> 00:03:06,210
Aici, am gasit 7.

68
00:03:06,210 --> 00:03:08,160
Acum, vom verifica pentru 5.

69
00:03:08,160 --> 00:03:11,500
Cinci este mai mică de 6, așa că trebuie să fie la stânga.

70
00:03:11,500 --> 00:03:13,460
Cinci este mai mare de 2,

71
00:03:13,460 --> 00:03:15,010
așa că trebuie să fie corect,

72
00:03:15,010 --> 00:03:18,100
și este, de asemenea, mai mare de 4, deci trebuie să fie corect din nou.

73
00:03:18,100 --> 00:03:20,300
Cu toate acestea, nu există nici un copil aici.

74
00:03:20,300 --> 00:03:22,000
Cursorul este nul.

75
00:03:22,000 --> 00:03:24,270
Acest lucru înseamnă că 5 nu este în copacul nostru.

76
00:03:24,270 --> 00:03:27,250
>> Noi putem căuta arbore binar cu codul de mai jos:

77
00:03:28,430 --> 00:03:31,140
La fiecare nod, vom verifica pentru a vedea dacă ne-am gasit

78
00:03:31,140 --> 00:03:33,020
valoarea pe care o cautati.

79
00:03:33,020 --> 00:03:35,740
Dacă nu vom găsi, vom determina dacă acesta ar trebui să fie

80
00:03:35,740 --> 00:03:38,990
pe stânga sau dreapta și verificați dacă subarborele.

81
00:03:38,990 --> 00:03:41,160
Această buclă va continua în jos copac

82
00:03:41,160 --> 00:03:44,190
până când nu există nici un nod copil fie pe stânga sau la dreapta.

83
00:03:45,190 --> 00:03:48,600
>> Amintiți-vă că 5 nu a fost în copac.

84
00:03:48,600 --> 00:03:50,460
Cum l-am introduce?

85
00:03:50,460 --> 00:03:52,370
Procesul este asemănător pentru a căuta.

86
00:03:52,370 --> 00:03:54,830
Noi repeta în jos arborele începând de la 6,

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

88
00:03:57,040 --> 00:03:59,140
dreptul la 4,

89
00:03:59,140 --> 00:04:02,500
și din nou la dreapta, dar nu are nici un copil 4 pe partea asta.

90
00:04:02,500 --> 00:04:06,090
Acest lucru va fi noua poziție timp de 5,

91
00:04:06,090 --> 00:04:08,500
și va începe fără copii.

92
00:04:09,020 --> 00:04:12,220
>> Cât de repede sunt operații pe un arbore binar de căutare?

93
00:04:12,220 --> 00:04:15,410
Amintiți-vă că Bigohnotation încearcă să ofere o legat de sus.

94
00:04:15,410 --> 00:04:17,390
În cel mai rău caz,

95
00:04:17,390 --> 00:04:19,480
copacul nostru ar putea fi pur și simplu o listă legat

96
00:04:19,480 --> 00:04:22,220
sensul că inserare, ștergere, căutare și

97
00:04:22,220 --> 00:04:25,380
ar putea avea nevoie de timp proporțional cu numărul de noduri din arbore.

98
00:04:25,380 --> 00:04:27,380
Acest lucru este O (n).

99
00:04:27,380 --> 00:04:30,690
>> De exemplu, următorul este un arbore binar de căutare validă.

100
00:04:31,850 --> 00:04:34,020
Cu toate acestea, în cazul în care vom încerca să găsim 9,

101
00:04:34,020 --> 00:04:36,760
avem de a traversa fiecare nod.

102
00:04:36,760 --> 00:04:39,120
Nu este nici mai bună decât o listă legată.

103
00:04:39,120 --> 00:04:41,410
În mod ideal, ne-ar dori fiecare nod

104
00:04:41,410 --> 00:04:44,120
nostru binar arbore de căutare pentru a avea 2 copii.

105
00:04:44,120 --> 00:04:46,370
În acest fel, inserare, ștergere și căutare

106
00:04:46,370 --> 00:04:50,190
ar lua, în cel mai rău, O (log n) timp.

107
00:04:50,190 --> 00:04:52,470
Arbore de dinainte ar putea fi mai echilibrată,

108
00:04:52,470 --> 00:04:54,140
ca asta.

109
00:04:54,140 --> 00:04:57,980
Acum, uita în sus orice valoare are, cel mult, 3 trepte.

110
00:04:57,980 --> 00:04:59,460
Acest copac este echilibrat,

111
00:04:59,460 --> 00:05:01,190
sensul că are o adâncime minimă

112
00:05:01,190 --> 00:05:03,680
în raport cu numărul de noduri.

113
00:05:03,680 --> 00:05:06,300
>> Cauti o valoare într-un copac echilibrată binar de căutare

114
00:05:06,300 --> 00:05:09,540
este similar cu cautarea binara pe o matrice sortate.

115
00:05:09,540 --> 00:05:12,290
De fapt, în cazul în care nu avem nevoie pentru a insera sau șterge elemente,

116
00:05:12,290 --> 00:05:15,150
acestea se comportă exact același mod.

117
00:05:15,150 --> 00:05:17,600
Cu toate acestea, o structură de arbore este mai bine

118
00:05:17,600 --> 00:05:19,530
pentru insertii de manipulare și ștergeri

119
00:05:20,360 --> 00:05:22,670
>> Numele meu este Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Acest lucru este CS50.