1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kuidas te esindada kõiki oma pereliikmetele arvuti?

2
00:00:10,790 --> 00:00:12,390
Me võiksime lihtsalt kasutada nimekirja,

3
00:00:12,390 --> 00:00:14,400
kuid seal on selge hierarhia siin.

4
00:00:14,400 --> 00:00:17,110
>> Oletame, et me hakkame oma vanavanaema, Alice.

5
00:00:17,110 --> 00:00:19,030
Tal on 2 poega, Bob

6
00:00:19,030 --> 00:00:21,310
ja oma vanaisa, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie on 3 last,

8
00:00:23,190 --> 00:00:26,730
oma onu, Dave, oma tädi, Eve, ja oma isa, Fred.

9
00:00:26,730 --> 00:00:28,750
Olete Fredi ainus laps.

10
00:00:28,750 --> 00:00:30,950
>> Miks peaks korraldama oma pereliikmetele sel viisil

11
00:00:30,950 --> 00:00:34,010
parem kui lihtne nimekiri esindus?

12
00:00:34,010 --> 00:00:36,630
Üks põhjus on see, et hierarhiline struktuur,

13
00:00:36,630 --> 00:00:39,660
nimega "puu" sisaldab rohkem infot kui lihtsalt loetelu.

14
00:00:40,540 --> 00:00:43,520
Me teame põlvnemissuhete vahel kõigile

15
00:00:43,520 --> 00:00:45,440
lihtsalt uurides puu.

16
00:00:45,440 --> 00:00:47,250
Samuti võib kiirendada

17
00:00:47,250 --> 00:00:50,010
look-up aega tohutult, kui puu andmeid sorteerida.

18
00:00:50,010 --> 00:00:53,850
>> Me ei saa ära, et siin, kuid eks me näeme näide sellest varsti.

19
00:00:53,850 --> 00:00:56,150
Iga inimene on esindatud sõlme puul.

20
00:00:56,680 --> 00:00:58,370
Sõlmed võivad tütartippu

21
00:00:58,370 --> 00:01:00,350
samuti vanem sõlme.

22
00:01:00,350 --> 00:01:02,390
Need on tehnilised terminid,

23
00:01:02,390 --> 00:01:05,220
isegi kui kasutate puud asju peale peredele.

24
00:01:05,220 --> 00:01:07,940
Alice'i sõlm on 2 last ja vanemaid,

25
00:01:07,940 --> 00:01:11,500
samas Charlie sõlm on 3 last ja 1 vanem.

26
00:01:11,500 --> 00:01:14,330
>> Lehed on üks, mis ei ole ka lapsi

27
00:01:14,330 --> 00:01:16,410
väljastpoolt serva puu.

28
00:01:16,410 --> 00:01:18,520
Tähtsaim sõlm puu, juur sõlme,

29
00:01:18,520 --> 00:01:20,240
puudub tema vanem.

30
00:01:20,240 --> 00:01:23,170
>> Kahendpuu on teatud tüüpi puu,

31
00:01:23,170 --> 00:01:26,720
kus iga tipp on kõige rohkem 2 last.

32
00:01:26,720 --> 00:01:30,490
Siin on struct kohta sõlme kahendpuu in C.

33
00:01:31,560 --> 00:01:34,530
Iga sõlm on mõned andmed sellega seotud

34
00:01:34,530 --> 00:01:36,520
ja 2 viiteid teistele tippe.

35
00:01:36,520 --> 00:01:38,110
>> Meie sugupuu,

36
00:01:38,110 --> 00:01:40,900
seotud andmed oli iga isiku nimi.

37
00:01:40,900 --> 00:01:43,850
Siin see on keskmine, kuigi see võiks olla midagi.

38
00:01:44,510 --> 00:01:46,200
Nagu selgub,

39
00:01:46,200 --> 00:01:48,990
kahendpuu ei oleks hea esitus perele,

40
00:01:48,990 --> 00:01:51,960
kuna inimesed on sageli rohkem kui 2 last.

41
00:01:51,960 --> 00:01:53,510
>> Kahendotsingupuu

42
00:01:53,510 --> 00:01:56,380
on eriline, tellitud tüüpi kahendpuu

43
00:01:56,380 --> 00:01:58,090
mis võimaldab meil vaadata väärtused kiiresti.

44
00:01:58,740 --> 00:02:00,050
Olete ehk märganud

45
00:02:00,050 --> 00:02:02,010
et iga sõlme allpool puu juurt

46
00:02:02,010 --> 00:02:04,620
on root teise puu, mida nimetatakse "alampuu."

47
00:02:04,960 --> 00:02:07,090
Siin just puu on 6,

48
00:02:07,090 --> 00:02:09,860
ja oma lapse, 2, on just alampuu.

49
00:02:09,860 --> 00:02:11,870
>> Aastal Kahendotsingupuu

50
00:02:11,870 --> 00:02:15,790
kõik väärtused sõlm on parempoolne alampuu

51
00:02:15,790 --> 00:02:18,690
on suurem kui sõlme väärtusest. Siin: 6.

52
00:02:18,690 --> 00:02:22,640
Noh, väärtused sõlme vasaku alampuu

53
00:02:24,540 --> 00:02:26,890
on väiksem kui sõlme väärtusest.

54
00:02:26,890 --> 00:02:28,620
Kui me peame hakkama duplikaatväärtusi,

55
00:02:28,620 --> 00:02:31,760
saame muuta kumbki neist on lahtine ebavõrdsus,

56
00:02:31,760 --> 00:02:34,410
mis tähendab identsed väärtused võivad langeda kas vasakule või paremale,

57
00:02:34,410 --> 00:02:37,400
nii kaua kui meil on kooskõlas selle peale kogu.

58
00:02:37,400 --> 00:02:39,620
See puu on Kahendotsingupuu

59
00:02:39,620 --> 00:02:41,540
sest see järgib neid eeskirju.

60
00:02:42,320 --> 00:02:46,020
>> See on kuidas see näeks välja kui me pöördusime kõik sõlmed arvesse C structs.

61
00:02:46,880 --> 00:02:48,410
Pange tähele, et kui laps on kadunud,

62
00:02:48,410 --> 00:02:50,340
pointer on null.

63
00:02:50,340 --> 00:02:53,270
Kuidas vaadata, kui 7 on puus?

64
00:02:53,270 --> 00:02:55,020
Alustame keskmes.

65
00:02:55,020 --> 00:02:58,690
Seitse on suurem kui 6, nii et kui see on puu, see peab olema õige.

66
00:02:59,680 --> 00:03:03,650
Siis on vähem kui 8, seega tuleb jätta.

67
00:03:03,650 --> 00:03:06,210
Siin me oleme leidnud 7.

68
00:03:06,210 --> 00:03:08,160
Nüüd vaatan 5.

69
00:03:08,160 --> 00:03:11,500
Viis on väiksem kui 6, seega tuleb vasakule.

70
00:03:11,500 --> 00:03:13,460
Viis on suurem kui 2,

71
00:03:13,460 --> 00:03:15,010
seepärast peab olema õigus,

72
00:03:15,010 --> 00:03:18,100
ja see on ka suurem kui 4, seega tuleb uuesti paremale.

73
00:03:18,100 --> 00:03:20,300
Samas ei ole lapse siin.

74
00:03:20,300 --> 00:03:22,000
Pointer on null.

75
00:03:22,000 --> 00:03:24,270
See tähendab, et 5 ei ole meie puu.

76
00:03:24,270 --> 00:03:27,250
>> Me ei otsi kahendpuu koos järgmise koodi abil:

77
00:03:28,430 --> 00:03:31,140
Igas tipus, me vaadata, kui oleme leidnud

78
00:03:31,140 --> 00:03:33,020
väärtus otsime.

79
00:03:33,020 --> 00:03:35,740
Kui me ei leia seda, me kindlaks teha, kas see peaks olema

80
00:03:35,740 --> 00:03:38,990
vasakule või paremale ja kontrollige, et alampuu.

81
00:03:38,990 --> 00:03:41,160
See silmus jätkab puu otsast alla

82
00:03:41,160 --> 00:03:44,190
kuni ei ole laps sõlme kas vasakule või paremale.

83
00:03:45,190 --> 00:03:48,600
>> Pea meeles, et 5 ei olnud puu.

84
00:03:48,600 --> 00:03:50,460
Kuidas lisada see?

85
00:03:50,460 --> 00:03:52,370
Protsess sarnaneb otsida.

86
00:03:52,370 --> 00:03:54,830
Me itereerima puu otsast alla alates 6

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

88
00:03:57,040 --> 00:03:59,140
õigus 4,

89
00:03:59,140 --> 00:04:02,500
ja uuesti paremale, kuid 4 ei ole lapse siinpool.

90
00:04:02,500 --> 00:04:06,090
See on uus positsioon 5,

91
00:04:06,090 --> 00:04:08,500
ja siis hakkab kellel ei ole lapsi.

92
00:04:09,020 --> 00:04:12,220
>> Kui kiiresti on operatsioonid Kahendotsingupuu?

93
00:04:12,220 --> 00:04:15,410
Pea meeles, et Bigohnotation püütakse anda ülemise.

94
00:04:15,410 --> 00:04:17,390
Halvimal juhul,

95
00:04:17,390 --> 00:04:19,480
meie puu võiks lihtsalt seotud nimekirja

96
00:04:19,480 --> 00:04:22,220
mis tähendab, et sisestamise, kustutamise ja otsing

97
00:04:22,220 --> 00:04:25,380
võib võtta aega proportsionaalne arv tippe puu.

98
00:04:25,380 --> 00:04:27,380
See on O (n).

99
00:04:27,380 --> 00:04:30,690
>> Näiteks järgmised on kehtiv Kahendotsingupuu.

100
00:04:31,850 --> 00:04:34,020
Siiski, kui me püüame leida 9,

101
00:04:34,020 --> 00:04:36,760
meil läbida iga sõlme.

102
00:04:36,760 --> 00:04:39,120
See ei ole parem kui seotud nimekirja.

103
00:04:39,120 --> 00:04:41,410
Ideaalis tahaksime iga sõlme

104
00:04:41,410 --> 00:04:44,120
meie Kahendotsingupuu on 2 last.

105
00:04:44,120 --> 00:04:46,370
Nii, sisestamise, kustutamise ja otsing

106
00:04:46,370 --> 00:04:50,190
võtaks, halvimal juhul O (log n) ajaga.

107
00:04:50,190 --> 00:04:52,470
Puud enne võiks olla rohkem tasakaalustatud,

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

109
00:04:54,140 --> 00:04:57,980
Nüüd, vaadates üles mingit väärtust võtab kõige rohkem 3 astet.

110
00:04:57,980 --> 00:04:59,460
See puu on tasakaalustatud,

111
00:04:59,460 --> 00:05:01,190
mis tähendab, et tal on minimaalne sügavus

112
00:05:01,190 --> 00:05:03,680
võrreldes sõlmede arvul.

113
00:05:03,680 --> 00:05:06,300
>> Otsid väärtus tasakaalustatud Kahendotsingupuu

114
00:05:06,300 --> 00:05:09,540
on sarnane binaarne otsing sorteeritud massiiv.

115
00:05:09,540 --> 00:05:12,290
Tegelikult, kui me ei vaja lisada või eemaldada,

116
00:05:12,290 --> 00:05:15,150
nad käituvad täpselt samamoodi.

117
00:05:15,150 --> 00:05:17,600
Kuid puu struktuuri on parem

118
00:05:17,600 --> 00:05:19,530
käitlemise lisamised ja kustutamised

119
00:05:20,360 --> 00:05:22,670
>> Minu nimi on Bannus Van der kloot.

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