1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kako bi vam predstavlja sve svoje članove obitelji u računalu?

2
00:00:10,790 --> 00:00:12,390
Mi jednostavno mogli koristiti popis,

3
00:00:12,390 --> 00:00:14,400
ali postoji jasna hijerarhija ovdje.

4
00:00:14,400 --> 00:00:17,110
>> Recimo počinjemo s prabaka, Alice.

5
00:00:17,110 --> 00:00:19,030
Ona ima dva sina, Bob

6
00:00:19,030 --> 00:00:21,310
i tvoj djed, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ima 3 djece,

8
00:00:23,190 --> 00:00:26,730
Vaš ujak, Dave, vaša tetka, Eva, i tvoj otac, Fred.

9
00:00:26,730 --> 00:00:28,750
Vi ste Fredov jedino dijete.

10
00:00:28,750 --> 00:00:30,950
>> Zašto bi organizira svoje članove obitelji na ovaj način

11
00:00:30,950 --> 00:00:34,010
biti bolja od jednostavnog popisa reprezentacije?

12
00:00:34,010 --> 00:00:36,630
Jedan od razloga je da je to hijerarhijska struktura,

13
00:00:36,630 --> 00:00:39,660
naziva "stablo", sadrži više informacija nego jednostavan popis.

14
00:00:40,540 --> 00:00:43,520
Znamo obiteljske odnose između svakoga

15
00:00:43,520 --> 00:00:45,440
samo uvidom u stablo.

16
00:00:45,440 --> 00:00:47,250
Također, to može ubrzati

17
00:00:47,250 --> 00:00:50,010
izgled-up vrijeme strahovito, ako stablo podaci razvrstani.

18
00:00:50,010 --> 00:00:53,850
>> Ne možemo iskoristiti da ovdje, ali vidjet ćemo primjer za to uskoro.

19
00:00:53,850 --> 00:00:56,150
Svaka osoba predstavlja čvor na stablu.

20
00:00:56,680 --> 00:00:58,370
Čvorovi mogu imati djecu čvorova

21
00:00:58,370 --> 00:01:00,350
kao i roditelj čvor.

22
00:01:00,350 --> 00:01:02,390
To su tehnički uvjeti,

23
00:01:02,390 --> 00:01:05,220
Čak i ako koristite stabala za stvari osim obitelji.

24
00:01:05,220 --> 00:01:07,940
Alice čvor ima dva djecu i nema roditelje,

25
00:01:07,940 --> 00:01:11,500
dok je Charliejev čvor ima 3 djece i jedan roditelj.

26
00:01:11,500 --> 00:01:14,330
>> Čvor nultog stupnja je onaj koji nema nikakve djecu

27
00:01:14,330 --> 00:01:16,410
na vanjskom rubu stabla.

28
00:01:16,410 --> 00:01:18,520
Najviši čvor stabla, korijen čvor,

29
00:01:18,520 --> 00:01:20,240
nema roditelja.

30
00:01:20,240 --> 00:01:23,170
>> Binarno stablo je specifična vrsta drveta,

31
00:01:23,170 --> 00:01:26,720
u kojem je svaki čvor ima, u najboljem slučaju, 2 djece.

32
00:01:26,720 --> 00:01:30,490
Ovdje je struct od čvora binarnog stabla u C.

33
00:01:31,560 --> 00:01:34,530
Svaki čvor ima neke podatke povezane s njim

34
00:01:34,530 --> 00:01:36,520
i dva upućuje na druge čvorove.

35
00:01:36,520 --> 00:01:38,110
>> U našem obiteljskom stablu,

36
00:01:38,110 --> 00:01:40,900
pridružene podataka je svaka osoba je ime.

37
00:01:40,900 --> 00:01:43,850
Ovdje je int, iako bi to moglo biti ništa.

38
00:01:44,510 --> 00:01:46,200
Kao što se ispostavilo,

39
00:01:46,200 --> 00:01:48,990
stablo binarno neće biti dobra reprezentacija za obitelj,

40
00:01:48,990 --> 00:01:51,960
jer ljudi često imaju više od dva djece.

41
00:01:51,960 --> 00:01:53,510
>> Stablo binarno pretraživanje

42
00:01:53,510 --> 00:01:56,380
je posebna, uređenu vrsta binarnog stabla

43
00:01:56,380 --> 00:01:58,090
koji nam omogućuje da pogledamo vrijednosti brzo.

44
00:01:58,740 --> 00:02:00,050
Možda ste primijetili

45
00:02:00,050 --> 00:02:02,010
da je svaki čvor ispod korijena stabla

46
00:02:02,010 --> 00:02:04,620
je korijen drugog stabla, zove 'podstablo.'

47
00:02:04,960 --> 00:02:07,090
Evo, korijen stabla je 6,

48
00:02:07,090 --> 00:02:09,860
i njegova dijete, 2, je korijen podstablo.

49
00:02:09,860 --> 00:02:11,870
>> U binarnom stablu pretraživanja

50
00:02:11,870 --> 00:02:15,790
sve vrijednosti čvor je pravo podstablo

51
00:02:15,790 --> 00:02:18,690
su veći od čvora vrijednosti. Ovdje: 6.

52
00:02:18,690 --> 00:02:22,640
Pa, vrijednosti u čvor je lijevo podstablo

53
00:02:24,540 --> 00:02:26,890
manje od čvora vrijednosti.

54
00:02:26,890 --> 00:02:28,620
Ako trebamo nositi dvostruke vrijednosti,

55
00:02:28,620 --> 00:02:31,760
možemo promijeniti bilo koji od onih na slobodnom nejednakosti,

56
00:02:31,760 --> 00:02:34,410
znači identične vrijednosti može pasti bilo na lijevo ili desno,

57
00:02:34,410 --> 00:02:37,400
dok smo dosljedni o tome tijekom.

58
00:02:37,400 --> 00:02:39,620
Ovo stablo je binarno pretraživanje stablo

59
00:02:39,620 --> 00:02:41,540
jer slijedi ta pravila.

60
00:02:42,320 --> 00:02:46,020
>> To je, kako bi to izgledalo da smo okrenuli sve čvorove u C tvorevina.

61
00:02:46,880 --> 00:02:48,410
Primjetite da ako je dijete nestalo,

62
00:02:48,410 --> 00:02:50,340
Pokazivač je null.

63
00:02:50,340 --> 00:02:53,270
Kako smo provjerili da li je 7 u stablu?

64
00:02:53,270 --> 00:02:55,020
Krećemo u korijenu.

65
00:02:55,020 --> 00:02:58,690
Sedam je veći od 6, pa ako je to u stablo, to mora biti na desnoj strani.

66
00:02:59,680 --> 00:03:03,650
Zatim, to je manje od 8, tako da mora biti lijevo.

67
00:03:03,650 --> 00:03:06,210
Evo, našli smo sedam.

68
00:03:06,210 --> 00:03:08,160
Sada ćemo provjeriti za pet.

69
00:03:08,160 --> 00:03:11,500
Pet je manje od 6, pa to mora biti na lijevoj strani.

70
00:03:11,500 --> 00:03:13,460
Pet je veći od 2,

71
00:03:13,460 --> 00:03:15,010
tako da mora biti u pravu,

72
00:03:15,010 --> 00:03:18,100
i to je također veći od četiri, tako da mora biti ponovno desno.

73
00:03:18,100 --> 00:03:20,300
Međutim, ne postoji dijete ovdje.

74
00:03:20,300 --> 00:03:22,000
Pokazivač je null.

75
00:03:22,000 --> 00:03:24,270
To znači da 5 nije u našem stablu.

76
00:03:24,270 --> 00:03:27,250
>> Možemo pretraživati ​​binarnog stabla sa sljedeći kod:

77
00:03:28,430 --> 00:03:31,140
Na svakom čvoru, mi provjeriti da li smo našli

78
00:03:31,140 --> 00:03:33,020
vrijednost tražimo.

79
00:03:33,020 --> 00:03:35,740
Ako ga ne pronađete, mi se utvrdilo da li je to trebao biti

80
00:03:35,740 --> 00:03:38,990
lijevo ili desno i provjerite da podstablo.

81
00:03:38,990 --> 00:03:41,160
Ova petlja će se nastaviti niz stablo

82
00:03:41,160 --> 00:03:44,190
dok ne postoji čvor dijete na bilo lijevo ili desno.

83
00:03:45,190 --> 00:03:48,600
>> Sjetite se da je 5 nije bio u stablo.

84
00:03:48,600 --> 00:03:50,460
Kako ćemo ga ubaciti?

85
00:03:50,460 --> 00:03:52,370
Proces sličan pretraživanje.

86
00:03:52,370 --> 00:03:54,830
Mi ponoviti dolje stablo počevši od 6,

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

88
00:03:57,040 --> 00:03:59,140
pravo na 4,

89
00:03:59,140 --> 00:04:02,500
i opet desno, ali 4 nema dijete na ovoj strani.

90
00:04:02,500 --> 00:04:06,090
To će biti novi položaj za 5,

91
00:04:06,090 --> 00:04:08,500
i počet će bez djece.

92
00:04:09,020 --> 00:04:12,220
>> Koliko brzo su operacije na binarnog stabla pretraživanja?

93
00:04:12,220 --> 00:04:15,410
Zapamtite da Bigohnotation nastoji pružiti gornja granica.

94
00:04:15,410 --> 00:04:17,390
U najgorem slučaju,

95
00:04:17,390 --> 00:04:19,480
naša stablo jednostavno mogla biti povezana popis

96
00:04:19,480 --> 00:04:22,220
što znači da umetanje, brisanje i pretraživanje

97
00:04:22,220 --> 00:04:25,380
moglo potrajati proporcionalan broju čvorova u stablu.

98
00:04:25,380 --> 00:04:27,380
Ovo je O (n).

99
00:04:27,380 --> 00:04:30,690
>> Na primjer, sljedeće je važeća binarno stablo pretraživanja.

100
00:04:31,850 --> 00:04:34,020
Međutim, ako ćemo pokušati pronaći 9,

101
00:04:34,020 --> 00:04:36,760
moramo proći svaki čvor.

102
00:04:36,760 --> 00:04:39,120
To nije ništa bolji od povezane liste.

103
00:04:39,120 --> 00:04:41,410
U idealnom slučaju, mi bi htjeli svaki čvor

104
00:04:41,410 --> 00:04:44,120
našeg stabla binarno pretraživanje imati dva djece.

105
00:04:44,120 --> 00:04:46,370
Na taj način, umetanje, brisanje i pretraživanje

106
00:04:46,370 --> 00:04:50,190
bi, u najgorem slučaju, O (log n) vremena.

107
00:04:50,190 --> 00:04:52,470
Stablo od prije mogao biti uravnotežena,

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

109
00:04:54,140 --> 00:04:57,980
Sada, gledajući bilo koju vrijednost ima, najviše, tri koraka.

110
00:04:57,980 --> 00:04:59,460
Ovo stablo je uravnotežen,

111
00:04:59,460 --> 00:05:01,190
što znači da je ima minimalnu dubinu

112
00:05:01,190 --> 00:05:03,680
u odnosu na broj čvorova.

113
00:05:03,680 --> 00:05:06,300
>> U potrazi za vrijednosti u uravnoteženom binarnog stabla pretraživanja

114
00:05:06,300 --> 00:05:09,540
je sličan binarnom pretraživanje na sortirati niz.

115
00:05:09,540 --> 00:05:12,290
U stvari, ako mi ne treba umetnuti ili izbrisati stavke,

116
00:05:12,290 --> 00:05:15,150
oni se ponašaju na isti način.

117
00:05:15,150 --> 00:05:17,600
Međutim, struktura stabla je bolje

118
00:05:17,600 --> 00:05:19,530
za rukovanje umetanja i brisanja

119
00:05:20,360 --> 00:05:22,670
>> Moje ime je Bannus Van der Kloot.

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