1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kaip jūs atstovauti visus savo šeimos narius į kompiuterį?

2
00:00:10,790 --> 00:00:12,390
Mes galime tiesiog naudoti sąrašą,

3
00:00:12,390 --> 00:00:14,400
bet čia yra aiški hierarchija.

4
00:00:14,400 --> 00:00:17,110
>> Tarkime, mes pradėjome su savo puikiai močiutė, Alice.

5
00:00:17,110 --> 00:00:19,030
Ji turi 2 sūnus, BOB

6
00:00:19,030 --> 00:00:21,310
ir tavo senelis, Čarlis.

7
00:00:21,310 --> 00:00:23,190
Čarlis turi 3 vaikus,

8
00:00:23,190 --> 00:00:26,730
tavo dėdė, Dave, jūsų teta, Ieva, ir tavo tėvas, Fredas.

9
00:00:26,730 --> 00:00:28,750
Esate Fredo vienintelis vaikas.

10
00:00:28,750 --> 00:00:30,950
>> Kodėl gi organizuoti savo šeimos narius tokiu būdu

11
00:00:30,950 --> 00:00:34,010
būti geriau nei paprastas sąrašas atstovavimo?

12
00:00:34,010 --> 00:00:36,630
Viena iš priežasčių yra tai, kad hierarchinė struktūra,

13
00:00:36,630 --> 00:00:39,660
vadinamas "medis", pateikiama daugiau informacijos nei paprastą sąrašą.

14
00:00:40,540 --> 00:00:43,520
Mes žinome, kad šeimos santykius tarp visiems

15
00:00:43,520 --> 00:00:45,440
tik nagrinėjant medį.

16
00:00:45,440 --> 00:00:47,250
Be to, ji gali pagreitinti

17
00:00:47,250 --> 00:00:50,010
peržiūroje laikas labai, jei medžių duomenys rūšiuojami.

18
00:00:50,010 --> 00:00:53,850
>> Mes negalime pasinaudoti, kad čia, bet mes pamatyti šio pavyzdžiu netrukus.

19
00:00:53,850 --> 00:00:56,150
Kiekvienas žmogus yra atstovaujamos ant medžio mazgas.

20
00:00:56,680 --> 00:00:58,370
Mazgai gali turėti vaikų mazgų

21
00:00:58,370 --> 00:01:00,350
taip pat patronuojančios mazgas.

22
00:01:00,350 --> 00:01:02,390
Tai yra techniniai terminai,

23
00:01:02,390 --> 00:01:05,220
net naudojant medžių dalykų, be šeimų.

24
00:01:05,220 --> 00:01:07,940
Alisos mazgas turi 2 vaikus ir neturi tėvų,

25
00:01:07,940 --> 00:01:11,500
o Čarlio mazgas turi 3 vaikus ir 1 iš tėvų.

26
00:01:11,500 --> 00:01:14,330
>> Lapų mazgas yra vienas, kad neturi vaikų

27
00:01:14,330 --> 00:01:16,410
išorinio krašto medžio.

28
00:01:16,410 --> 00:01:18,520
Viršutinis medžio mazgas, šakninis mazgas,

29
00:01:18,520 --> 00:01:20,240
neturi tėvų.

30
00:01:20,240 --> 00:01:23,170
>> Dvejetainis medis yra tam tikros rūšies medžio,

31
00:01:23,170 --> 00:01:26,720
, kurioje kiekvienas mazgas turi ne daugiau kaip 2 vaikus.

32
00:01:26,720 --> 00:01:30,490
Čia yra dvejetainis medis, C mazgas struct

33
00:01:31,560 --> 00:01:34,530
Kiekvienas mazgas turi tam tikrus duomenis, susijusius su juo

34
00:01:34,530 --> 00:01:36,520
ir 2 rodykles į kitus mazgus.

35
00:01:36,520 --> 00:01:38,110
>> Mūsų šeimos medį,

36
00:01:38,110 --> 00:01:40,900
susiję duomenys buvo kiekvieno žmogaus vardas.

37
00:01:40,900 --> 00:01:43,850
Čia jis yra int, nors ji gali būti bet kas.

38
00:01:44,510 --> 00:01:46,200
As it turns out,

39
00:01:46,200 --> 00:01:48,990
dvejetainis medis nebūtų geras atstovavimas šeimai,

40
00:01:48,990 --> 00:01:51,960
nes žmonės dažnai turi daugiau nei 2 vaikus.

41
00:01:51,960 --> 00:01:53,510
>> Dvejetainis paieškos medis

42
00:01:53,510 --> 00:01:56,380
yra išskirtinis, sutvarkyta dvejetainis medis tipas

43
00:01:56,380 --> 00:01:58,090
, kuri leidžia mums greitai pažvelgti į vertybes.

44
00:01:58,740 --> 00:02:00,050
Galbūt jūs pastebėjote,

45
00:02:00,050 --> 00:02:02,010
kad kiekvienas žemiau medžio šaknų mazgas

46
00:02:02,010 --> 00:02:04,620
yra kito medžio šaknis, vadinama "šaka".

47
00:02:04,960 --> 00:02:07,090
Čia iš medžio šaknis yra 6,

48
00:02:07,090 --> 00:02:09,860
ir jo vaikas, 2, šaka šaknis.

49
00:02:09,860 --> 00:02:11,870
>> Dvejetainis paieškos medis

50
00:02:11,870 --> 00:02:15,790
visi mazgas vertės teisė šaka

51
00:02:15,790 --> 00:02:18,690
yra didesnė nei mazgas vertės. Čia: 6.

52
00:02:18,690 --> 00:02:22,640
Na, mazgo kairėje šaka vertės

53
00:02:24,540 --> 00:02:26,890
yra mažiau nei mazgas vertės.

54
00:02:26,890 --> 00:02:28,620
Jei mums reikės tvarkyti pasikartojančius vertybes,

55
00:02:28,620 --> 00:02:31,760
mes galime pakeisti arba tų, kurios prarasti nelygybės,

56
00:02:31,760 --> 00:02:34,410
identiški dydžiai gali nukristi arba į kairę arba į dešinę,

57
00:02:34,410 --> 00:02:37,400
tol, kol mes nuosekliai visoje.

58
00:02:37,400 --> 00:02:39,620
Šis medis yra dvejetainis paieškos medis

59
00:02:39,620 --> 00:02:41,540
, nes jis šias taisykles.

60
00:02:42,320 --> 00:02:46,020
>> Tai, kaip jis atrodys, jei mes kreipėmės į visus mazgus C structs.

61
00:02:46,880 --> 00:02:48,410
Atkreipkite dėmesį, kad, jei vaikas nėra,

62
00:02:48,410 --> 00:02:50,340
rodyklė yra tuščias.

63
00:02:50,340 --> 00:02:53,270
Kaip mes patikrinti, norėdami pamatyti, jei 7 į medį?

64
00:02:53,270 --> 00:02:55,020
Mes pradedame ne šaknis.

65
00:02:55,020 --> 00:02:58,690
Septyni yra didesnis kaip 6, todėl, jei jis yra medžio, ji turi būti į dešinę.

66
00:02:59,680 --> 00:03:03,650
Tada, tai yra mažiau nei 8, todėl jis turi būti paliktas.

67
00:03:03,650 --> 00:03:06,210
Čia, mes nustatėme, 7.

68
00:03:06,210 --> 00:03:08,160
Dabar mes patikrinti 5.

69
00:03:08,160 --> 00:03:11,500
Penki yra mažiau nei 6, todėl ji turi būti į kairę.

70
00:03:11,500 --> 00:03:13,460
Penkių yra didesnis kaip 2,

71
00:03:13,460 --> 00:03:15,010
todėl ji turi būti teisinga,

72
00:03:15,010 --> 00:03:18,100
ir ji taip pat yra didesnės nei 4, todėl ji turi būti vėl dešinėn.

73
00:03:18,100 --> 00:03:20,300
Tačiau yra ne vaikas čia.

74
00:03:20,300 --> 00:03:22,000
Rodyklė yra tuščias.

75
00:03:22,000 --> 00:03:24,270
Tai reiškia, kad 5 yra ne mūsų medžio.

76
00:03:24,270 --> 00:03:27,250
>> Mes galime ieškoti dvejetainį medį su šį kodą:

77
00:03:28,430 --> 00:03:31,140
Kiekviename mazge, mes patikrinti, norėdami pamatyti, jei mes turime rasti

78
00:03:31,140 --> 00:03:33,020
vertė, mes ieškome.

79
00:03:33,020 --> 00:03:35,740
Jei mes negalime rasti tai, mes nustatyti, ar ji turėtų būti

80
00:03:35,740 --> 00:03:38,990
kairę arba į dešinę ir patikrinti, kad šaka.

81
00:03:38,990 --> 00:03:41,160
Šis ciklas bus toliau medį

82
00:03:41,160 --> 00:03:44,190
kol nėra vaikas mazgas arba į kairę arba į dešinę.

83
00:03:45,190 --> 00:03:48,600
>> Atminkite, kad 5 buvo ne į medį.

84
00:03:48,600 --> 00:03:50,460
Kaip mes jį įterpti?

85
00:03:50,460 --> 00:03:52,370
Procesas yra panašus ieškoti.

86
00:03:52,370 --> 00:03:54,830
Mes pakartoti medį nuo 6,

87
00:03:54,830 --> 00:03:57,040
kairės į 2,

88
00:03:57,040 --> 00:03:59,140
teisę į 4,

89
00:03:59,140 --> 00:04:02,500
ir vėl dešinėn, bet 4 turi vaikų neturi šioje pusėje.

90
00:04:02,500 --> 00:04:06,090
Tai bus nauja pozicija 5,

91
00:04:06,090 --> 00:04:08,500
ir jis pradės be vaikų.

92
00:04:09,020 --> 00:04:12,220
>> Kaip greitai yra dvejetainis paieškos medis operacijos?

93
00:04:12,220 --> 00:04:15,410
Atminkite, kad Bigohnotation siekia teikti viršutinė riba.

94
00:04:15,410 --> 00:04:17,390
Blogiausiu atveju,

95
00:04:17,390 --> 00:04:19,480
mūsų medis gali tiesiog būti susieta sąrašas

96
00:04:19,480 --> 00:04:22,220
tai reiškia, kad papildymui, ištrynimui ir ieškoti

97
00:04:22,220 --> 00:04:25,380
gali užtrukti, proporcingą medžio mazgų skaičių.

98
00:04:25,380 --> 00:04:27,380
Tai yra O (n).

99
00:04:27,380 --> 00:04:30,690
>> Pavyzdžiui, taip yra galiojantis dvejetainis paieškos medis.

100
00:04:31,850 --> 00:04:34,020
Tačiau, jei mes stengiamės rasti 9

101
00:04:34,020 --> 00:04:36,760
turime išanalizuoti kiekvieną mazgą.

102
00:04:36,760 --> 00:04:39,120
Tai ne geriau nei susietą sąrašą.

103
00:04:39,120 --> 00:04:41,410
Idealiu atveju, mes norime, kad kiekvienas mazgas

104
00:04:41,410 --> 00:04:44,120
mūsų dvejetainis paieškos medis turi 2 vaikus.

105
00:04:44,120 --> 00:04:46,370
Tokiu būdu, įterpimas, ištrynimo ir paieškos

106
00:04:46,370 --> 00:04:50,190
imsis, blogiausiu atveju, O (log n) laiko.

107
00:04:50,190 --> 00:04:52,470
Nuo iki medis gali būti labiau subalansuota,

108
00:04:52,470 --> 00:04:54,140
kaip šis.

109
00:04:54,140 --> 00:04:57,980
Dabar, žiūrint kokią nors vertę užima ne daugiau kaip 3 žingsniai.

110
00:04:57,980 --> 00:04:59,460
Šis medis yra subalansuotas,

111
00:04:59,460 --> 00:05:01,190
tai reiškia, kad turi minimalų gylį

112
00:05:01,190 --> 00:05:03,680
, palyginti su mazgų skaičius.

113
00:05:03,680 --> 00:05:06,300
>> Domina subalansuotą dvejetainis paieškos medis vertės

114
00:05:06,300 --> 00:05:09,540
yra panaši į dvejetainį paieškos rūšiuotų masyvo.

115
00:05:09,540 --> 00:05:12,290
Iš tiesų, jei mes neturime reikia įterpti ar ištrinti elementus,

116
00:05:12,290 --> 00:05:15,150
jie elgiasi lygiai taip pat.

117
00:05:15,150 --> 00:05:17,600
Tačiau, medžio struktūra yra geriau

118
00:05:17,600 --> 00:05:19,530
tvarkymo įterpimus ir panaikinti

119
00:05:20,360 --> 00:05:22,670
>> Mano vardas yra Bannus Van der Kloot.

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