1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kā Jūs pārstāvēt visus savus ģimenes locekļus ar datoru?

2
00:00:10,790 --> 00:00:12,390
Mēs varētu vienkārši izmanto sarakstu,

3
00:00:12,390 --> 00:00:14,400
bet tur skaidrs hierarhija šeit.

4
00:00:14,400 --> 00:00:17,110
>> Pieņemsim, ka mēs esam sākuši ar savu vecvecmāmiņa, Alice.

5
00:00:17,110 --> 00:00:19,030
Viņai ir 2 dēli, Bob

6
00:00:19,030 --> 00:00:21,310
un jūsu vectēvs, Čārlijs.

7
00:00:21,310 --> 00:00:23,190
Čārlijs ir 3 bērni,

8
00:00:23,190 --> 00:00:26,730
jūsu tēvocis, Deivs, jūsu tante, Ieva, un tavs tēvs, Fred.

9
00:00:26,730 --> 00:00:28,750
Jums ir Freda vienīgais bērns.

10
00:00:28,750 --> 00:00:30,950
>> Kāpēc būtu organizēt savu ģimenes locekļiem šādā veidā

11
00:00:30,950 --> 00:00:34,010
labāk nekā vienkārši saraksts pārstāvniecības?

12
00:00:34,010 --> 00:00:36,630
Viens iemesls ir tas, ka šis hierarhiska struktūra,

13
00:00:36,630 --> 00:00:39,660
sauc par "koku," satur vairāk informācijas nekā vienkāršu sarakstu.

14
00:00:40,540 --> 00:00:43,520
Mēs zinām radnieciskas attiecības starp visiem

15
00:00:43,520 --> 00:00:45,440
vienkārši pārbaudot koku.

16
00:00:45,440 --> 00:00:47,250
Arī tas var paātrināt

17
00:00:47,250 --> 00:00:50,010
meklēt-up laiks vareni, ja koku dati tiek sakārtoti.

18
00:00:50,010 --> 00:00:53,850
>> Mēs nevaram izmantot, ka šeit, bet mēs redzēsim piemēru tas drīz.

19
00:00:53,850 --> 00:00:56,150
Katrs cilvēks ir pārstāvēta ar mezglu uz koku.

20
00:00:56,680 --> 00:00:58,370
Mezgli var būt bērnu mezgliem

21
00:00:58,370 --> 00:01:00,350
kā arī mātes mezglā.

22
00:01:00,350 --> 00:01:02,390
Tie ir tehniski termini,

23
00:01:02,390 --> 00:01:05,220
pat izmantojot koku, lai lietas, bez ģimenēm.

24
00:01:05,220 --> 00:01:07,940
Alises mezgls ir 2 bērni un nav vecāku,

25
00:01:07,940 --> 00:01:11,500
bet Charlie mezgls ir 3 bērni un 1 no vecākiem.

26
00:01:11,500 --> 00:01:14,330
>> Lapu mezgls ir viens, ka nav bērnu

27
00:01:14,330 --> 00:01:16,410
uz ārējās malas no koka.

28
00:01:16,410 --> 00:01:18,520
Augšējais mezgla koka, saknes mezglu,

29
00:01:18,520 --> 00:01:20,240
nav vecāks.

30
00:01:20,240 --> 00:01:23,170
>> Binārs koks ir īpaša veida koku,

31
00:01:23,170 --> 00:01:26,720
kurā katrs mezgls ir, augstākais, 2 bērni.

32
00:01:26,720 --> 00:01:30,490
Šeit ir no mezgla bināro koku C. struct

33
00:01:31,560 --> 00:01:34,530
Katram mezglam ir daži ar to saistītie dati

34
00:01:34,530 --> 00:01:36,520
un 2 norādes uz citiem mezgliem.

35
00:01:36,520 --> 00:01:38,110
>> Mūsu ģimenes koku,

36
00:01:38,110 --> 00:01:40,900
saistītās dati bija katra cilvēka vārdu.

37
00:01:40,900 --> 00:01:43,850
Šeit tas ir int, lai gan tas varētu būt kaut kas.

38
00:01:44,510 --> 00:01:46,200
Kā izrādās,

39
00:01:46,200 --> 00:01:48,990
binārs koks nebūtu labu pārstāvību par ģimeni,

40
00:01:48,990 --> 00:01:51,960
jo cilvēki bieži ir vairāk nekā 2 bērnus.

41
00:01:51,960 --> 00:01:53,510
>> Binārs meklēšanas koks

42
00:01:53,510 --> 00:01:56,380
ir īpašs, piesprieda binārās koku

43
00:01:56,380 --> 00:01:58,090
kas ļauj mums paskatīties uz vērtībām ātri.

44
00:01:58,740 --> 00:02:00,050
Jums var būt ievērojuši

45
00:02:00,050 --> 00:02:02,010
ka katrs mezgls zem saknes koku

46
00:02:02,010 --> 00:02:04,620
ir arī citas koku saknes, ko sauc "apakškoka."

47
00:02:04,960 --> 00:02:07,090
Lūk, no koka sakne ir 6,

48
00:02:07,090 --> 00:02:09,860
un tā bērns, 2, ir sakne apakškoka.

49
00:02:09,860 --> 00:02:11,870
>> Jo bināro meklēšanas koku

50
00:02:11,870 --> 00:02:15,790
visi mezglu vērtības ir labi apakškoka

51
00:02:15,790 --> 00:02:18,690
ir lielāka nekā mezglu vērtības. Šeit: 6.

52
00:02:18,690 --> 00:02:22,640
Nu, vērtībām mezgla kreisā apakškoka

53
00:02:24,540 --> 00:02:26,890
ir mazāk nekā mezglu vērtības.

54
00:02:26,890 --> 00:02:28,620
Ja mums ir nepieciešams, lai apstrādātu dublikātus,

55
00:02:28,620 --> 00:02:31,760
mēs varam mainīt nu no tiem ar vaļēju nevienlīdzību,

56
00:02:31,760 --> 00:02:34,410
nozīmē identiskas vērtības var krist nu pa kreisi vai pa labi,

57
00:02:34,410 --> 00:02:37,400
kamēr mēs esam konsekventi par to visā.

58
00:02:37,400 --> 00:02:39,620
Šis koks ir binārs meklēšanas koks

59
00:02:39,620 --> 00:02:41,540
jo no tā izriet, šos noteikumus.

60
00:02:42,320 --> 00:02:46,020
>> Tas ir, kā tas izskatītos, ja mēs vērsāmies visus mezglus uz C structs.

61
00:02:46,880 --> 00:02:48,410
Ievērojiet, ka, ja bērns ir pazudis,

62
00:02:48,410 --> 00:02:50,340
rādītājs ir nulle.

63
00:02:50,340 --> 00:02:53,270
Kā mēs pārbaudām, vai 7 ir kokā?

64
00:02:53,270 --> 00:02:55,020
Mēs sākam pie saknes.

65
00:02:55,020 --> 00:02:58,690
Septiņi ir lielāks par 6, tāpēc, ja tas ir no koka, tai jābūt tiesībām.

66
00:02:59,680 --> 00:03:03,650
Tad tas ir mazāk nekā 8, tāpēc jāatstāj.

67
00:03:03,650 --> 00:03:06,210
Lūk, mēs esam atraduši 7.

68
00:03:06,210 --> 00:03:08,160
Tagad, mēs pārbaudīsim uz 5.

69
00:03:08,160 --> 00:03:11,500
Pieci ir mazāks par 6, tāpēc tai jābūt pa kreisi.

70
00:03:11,500 --> 00:03:13,460
Pieci ir lielāks par 2,

71
00:03:13,460 --> 00:03:15,010
tāpēc tai jābūt labi,

72
00:03:15,010 --> 00:03:18,100
un tas ir arī lielāka par 4, tāpēc tai jābūt labi atkal.

73
00:03:18,100 --> 00:03:20,300
Tomēr nav bērnu šeit.

74
00:03:20,300 --> 00:03:22,000
Rādītājs ir nulle.

75
00:03:22,000 --> 00:03:24,270
Tas nozīmē, ka 5 nav mūsu koku.

76
00:03:24,270 --> 00:03:27,250
>> Mēs varam meklēt bināro koku ar šādu kodu:

77
00:03:28,430 --> 00:03:31,140
Katrā mezglā, mēs pārbaudām, vai mums ir atrasts

78
00:03:31,140 --> 00:03:33,020
vērtība, mēs meklējam.

79
00:03:33,020 --> 00:03:35,740
Ja mēs nevaram atrast to, mēs noteikt, ja tas būtu

80
00:03:35,740 --> 00:03:38,990
pa kreisi vai pa labi un pārbaudiet apakškoka.

81
00:03:38,990 --> 00:03:41,160
Šī cilpa turpinās pa koku

82
00:03:41,160 --> 00:03:44,190
kamēr nav bērnu mezglu vai nu pa kreisi vai pa labi.

83
00:03:45,190 --> 00:03:48,600
>> Atcerieties, ka 5 bija ne kokā.

84
00:03:48,600 --> 00:03:50,460
Kā mēs ievietot to?

85
00:03:50,460 --> 00:03:52,370
Šis process izskatās līdzīgs meklēt.

86
00:03:52,370 --> 00:03:54,830
Mēs atkārtot pa koku sākot no 6,

87
00:03:54,830 --> 00:03:57,040
kreisi līdz 2,

88
00:03:57,040 --> 00:03:59,140
Tiesības uz 4,

89
00:03:59,140 --> 00:04:02,500
un tiesības vēlreiz, 4 bet nav bērnu uz šo pusi.

90
00:04:02,500 --> 00:04:06,090
Tas būs jauns amats par 5,

91
00:04:06,090 --> 00:04:08,500
un tas sāks bez bērniem.

92
00:04:09,020 --> 00:04:12,220
>> Cik ātri ir operācijas bināro meklēšanas koku?

93
00:04:12,220 --> 00:04:15,410
Atcerieties, ka Bigohnotation cenšas nodrošināt augšējo robežu.

94
00:04:15,410 --> 00:04:17,390
Sliktākajā gadījumā,

95
00:04:17,390 --> 00:04:19,480
Mūsu koks varētu būt vienkārši saistīts saraksts

96
00:04:19,480 --> 00:04:22,220
kas nozīmē, ka ievietošanu, dzēšanu, un meklēt

97
00:04:22,220 --> 00:04:25,380
varētu prasīt laiku proporcionāls skaits mezglu kokā.

98
00:04:25,380 --> 00:04:27,380
Tas ir O (n).

99
00:04:27,380 --> 00:04:30,690
>> Piemēram, šādu derīgs bināro meklēšanas koku.

100
00:04:31,850 --> 00:04:34,020
Taču, ja mēs cenšamies atrast 9,

101
00:04:34,020 --> 00:04:36,760
mums ir traversa katru mezglu.

102
00:04:36,760 --> 00:04:39,120
Tas nav labāka nekā saistīts saraksts.

103
00:04:39,120 --> 00:04:41,410
Ideāli, ja mēs vēlamies katru mezglu

104
00:04:41,410 --> 00:04:44,120
Mūsu binārā meklēšanas koks ir 2 bērni.

105
00:04:44,120 --> 00:04:46,370
Tādā veidā, ievietošanas, dzēšanu un meklēt

106
00:04:46,370 --> 00:04:50,190
varētu veikt, bet sliktākajā, O (log n) laiks.

107
00:04:50,190 --> 00:04:52,470
No pirms koks varētu būt sabalansēts,

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

109
00:04:54,140 --> 00:04:57,980
Tagad, skatoties uz augšu nekādas vērtības ņem, augstākais, 3 soļi.

110
00:04:57,980 --> 00:04:59,460
Šis koks ir līdzsvarots,

111
00:04:59,460 --> 00:05:01,190
nozīmē, ka ir ir minimāla dziļums

112
00:05:01,190 --> 00:05:03,680
salīdzinot ar mezglu skaita.

113
00:05:03,680 --> 00:05:06,300
>> Meklē vērtību līdzsvarotas bināro meklēšanas koku

114
00:05:06,300 --> 00:05:09,540
ir līdzīgs bināro meklēšanu uz šķiroto masīvs.

115
00:05:09,540 --> 00:05:12,290
Patiesībā, ja mums nav nepieciešams, lai ievietotu vai dzēstu objektus,

116
00:05:12,290 --> 00:05:15,150
viņi uzvedas tieši tāpat.

117
00:05:15,150 --> 00:05:17,600
Tomēr koks struktūra ir labāka

118
00:05:17,600 --> 00:05:19,530
par apstrādes iespraudumi un svītrojumiem

119
00:05:20,360 --> 00:05:22,670
>> Mans vārds ir Bannus van der Kloot.

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