1
00:00:00,000 --> 00:00:02,994
>> [MÜZİK OYUN]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
Doug LLOYD: Yani biz yakın inching oldum
ve daha yakın bu verilerin Holy Grail

4
00:00:08,550 --> 00:00:13,050
biz ekleyebilirsiniz yapıları, tek
içine, silmek ve bakmak

5
00:00:13,050 --> 00:00:15,440
sürekli zaman içinde.

6
00:00:15,440 --> 00:00:16,270
Sağ.

7
00:00:16,270 --> 00:00:17,280
Bu hedefe tür.

8
00:00:17,280 --> 00:00:19,720
Biz yapabilmek istiyorum
işler çok, çok hızlı.

9
00:00:19,720 --> 00:00:22,580
>> Biz burada ne zaman buldunuz
Biz deneme bahsediyoruz?

10
00:00:22,580 --> 00:00:23,670
Peki, bir göz atalım.

11
00:00:23,670 --> 00:00:25,628
Bu yüzden birkaç gördüm
Farklı veri yapıları

12
00:00:25,628 --> 00:00:28,680
Bu haritalama kolu
anahtar-değer çiftleri olarak adlandırılan,

13
00:00:28,680 --> 00:00:32,080
bazı verileri parça haritalama
verilerin başka bir parçasına

14
00:00:32,080 --> 00:00:36,020
bu yüzden nerede bulacağınızı biliyorsunuz
yapıda bilgiler.

15
00:00:36,020 --> 00:00:40,060
>> Bu nedenle bir dizi için, örneğin,
anahtar unsur indeksi veya dizi

16
00:00:40,060 --> 00:00:42,600
Konumu 0 ya da dizi 1 vb.

17
00:00:42,600 --> 00:00:46,140
Ve değer veri
o konumda bulunmaktadır.

18
00:00:46,140 --> 00:00:48,550
Yani dizideki 0 ne saklanır?

19
00:00:48,550 --> 00:00:54,290
Ne sadece karşı dizide 1 depolanır
0, 1, anahtarlar olurdu.

20
00:00:54,290 --> 00:00:56,360
>> Karma tablo ile bu kadar
Aynı fikir tür.

21
00:00:56,360 --> 00:01:00,690
Karma tablo ile, bu karma var
hash kodları üretir işlevi.

22
00:01:00,690 --> 00:01:03,670
Yani anahtar verilerinin karma kodudur.

23
00:01:03,670 --> 00:01:06,530
Ve değer, özellikle de
biz zincirleme hakkında konuştuk

24
00:01:06,530 --> 00:01:10,590
karma tablolar video,
Verilerin bu bağlantılı liste

25
00:01:10,590 --> 00:01:12,550
o hashCode için sağlamalarının.

26
00:01:12,550 --> 00:01:14,050
Sağ.

27
00:01:14,050 --> 00:01:16,050
Başka bir yaklaşım hakkında neler
Bu yöntem olsa?

28
00:01:16,050 --> 00:01:21,000
Bir yöntem hakkında ne nerede
anahtar, benzersiz olması sağlanır

29
00:01:21,000 --> 00:01:25,410
karma tablo, biz olabilir aksine
Verilerin iki parça ile sona

30
00:01:25,410 --> 00:01:27,200
Aynı hashcode sahip.

31
00:01:27,200 --> 00:01:30,020
Ve sonra biz uğraşmak zorunda
bu da sondalama veya daha fazla

32
00:01:30,020 --> 00:01:33,340
tercihen bu sorunu çözmek için zincirleme.

33
00:01:33,340 --> 00:01:37,520
>> Yani şimdi garanti edemez
Bu bizim anahtar benzersiz olacaktır.

34
00:01:37,520 --> 00:01:39,690
Ve değer ne varsa
kolay bir şey

35
00:01:39,690 --> 00:01:44,080
ister bize o kadar doğru ve yanlış
bilgi ya da bu parça

36
00:01:44,080 --> 00:01:45,610
yapısında bulunan?

37
00:01:45,610 --> 00:01:48,180
Bir Boole biraz kadar basit olabilir.

38
00:01:48,180 --> 00:01:52,660
Gerçekçi muhtemelen var bir
biraz daha muhtemeldir bayt.

39
00:01:52,660 --> 00:01:55,410
Ama çok daha küçük olduğunu
50-karakter dizesi belki depolamak,

40
00:01:55,410 --> 00:01:57,360
Örneğin.

41
00:01:57,360 --> 00:02:02,210
>> Denemeden Yani, tablo karma benzer,
hangi birleştirmek diziler ve bağlantılı liste,

42
00:02:02,210 --> 00:02:05,790
çalışır diziler birleştirmek,
yapıları ve işaretçileri

43
00:02:05,790 --> 00:02:08,509
Birlikte veri depolamak için
var ilginç bir yol

44
00:02:08,509 --> 00:02:11,550
oldukça farklı
Şimdiye kadar gördüğüm şey.

45
00:02:11,550 --> 00:02:16,750
Şimdi bir yol haritası olarak verileri kullanmak
Bu veri yapısını gezinmek için.

46
00:02:16,750 --> 00:02:18,710
Ve biz takip edebilirsiniz eğer
yol haritası, eğer biz

47
00:02:18,710 --> 00:02:22,390
veri izleyin
Başından sonuna, yaparız

48
00:02:22,390 --> 00:02:24,945
Bu veriler olup olmadığını bilmek
tray bulunmaktadır.

49
00:02:24,945 --> 00:02:28,310
>> Ve biz haritayı takip edemez eğer
Tüm sona anlam dışında,

50
00:02:28,310 --> 00:02:30,600
veri var olamaz.

51
00:02:30,600 --> 00:02:32,890
Yine, anahtarlar burada
benzersiz olmasını garanti.

52
00:02:32,890 --> 00:02:36,020
Yani karma tablo aksine, biz asla anlayamayacağım
Burada çarpışmalar ile uğraşmak zorunda.

53
00:02:36,020 --> 00:02:39,090
Ve veri yok iki parça
aynı yol haritası var

54
00:02:39,090 --> 00:02:40,530
sürece veri aynıdır.

55
00:02:40,530 --> 00:02:44,580
>> Biz John, daha sonra takarsanız
Biz John arayın.

56
00:02:44,580 --> 00:02:47,430
Bu iki özdeş parçaları var
Veri, sağ, biz aracılığıyla arıyoruz.

57
00:02:47,430 --> 00:02:49,880
Ama aksi takdirde, herhangi bir
veri iki adettir

58
00:02:49,880 --> 00:02:52,750
benzersiz yol haritaları için garanti
Bu veri yapısı ile.

59
00:02:52,750 --> 00:02:56,210
Ve biz bakmak için gidiyoruz
Sadece bir an, bu bir görsel.

60
00:02:56,210 --> 00:02:58,810
>> Biz çalışarak bu yapacağım
Yeni bir veri yapısı oluşturmak,

61
00:02:58,810 --> 00:03:00,564
Aşağıdaki anahtar değer çiftleri haritalama.

62
00:03:00,564 --> 00:03:03,480
Bu durumda, biz kullanmak için gidiyoruz değil
Bir Boolean gibi basit bir şey.

63
00:03:03,480 --> 00:03:06,200
Biz aslında dize depolar.

64
00:03:06,200 --> 00:03:08,690
Ve bu dize gidiyor
Bir üniversitenin adı olabilir.

65
00:03:08,690 --> 00:03:12,140
>> Ve anahtar yılı olacak
Bu üniversitenin kurulduğu zaman.

66
00:03:12,140 --> 00:03:15,380
Üniversiteler için tüm yıl
Dört basamaklı olacak.

67
00:03:15,380 --> 00:03:19,840
Ve böylece biz bu dört basamak kullanacağız
Bu veri yapısının gezinin.

68
00:03:19,840 --> 00:03:22,270
Ve biz yine göreceğiz, nasıl
biz sadece bir saniye içinde bunu.

69
00:03:22,270 --> 00:03:25,110
>> Yolun sonunda,
Biz ismini görürsünüz

70
00:03:25,110 --> 00:03:30,250
karşılık gelen üniversite
Bu anahtara, bu dört basamak.

71
00:03:30,250 --> 00:03:34,390
Bir tray arkasındaki temel fikir
Biz merkezi rota olması.

72
00:03:34,390 --> 00:03:35,640
Yani bir ağaç gibi düşün.

73
00:03:35,640 --> 00:03:39,211
Ve bu yazım benzer
ve bir ağaca kavramı.

74
00:03:39,211 --> 00:03:41,460
Genellikle biz düşünmek zaman
Gerçek dünyada ağaçlar,

75
00:03:41,460 --> 00:03:44,090
Onlar öyle bir kök var
zemin ve yukarı doğru büyür

76
00:03:44,090 --> 00:03:46,830
ve onlar şubeleri var
ve onlar yaprakları vardır.

77
00:03:46,830 --> 00:03:49,450
Ve temelde fikri
bir tray, tam olarak aynı

78
00:03:49,450 --> 00:03:51,755
kök demirlemiş hariç
gökyüzünde bir yerde.

79
00:03:51,755 --> 00:03:53,130
Ve yaprakları alt kısmında bulunmaktadır.

80
00:03:53,130 --> 00:03:55,750
>> Yani bir ağaç alma gibi naziksiniz
ve sadece baş aşağı çevirerek.

81
00:03:55,750 --> 00:03:56,880
Ama yine de şubesi bulunmaktadır.

82
00:03:56,880 --> 00:03:59,463
Ve bu bizim yollar olacaktır
Bu bizim bağlantıları olacak

83
00:03:59,463 --> 00:04:02,220
yapraklara kökünden.

84
00:04:02,220 --> 00:04:04,200
Bu durumda, bu
yolları, bu dalları

85
00:04:04,200 --> 00:04:08,490
bize hane ile etiketlenmiş
hangi yolu Nerede gitmek için.

86
00:04:08,490 --> 00:04:11,800
>> Biz 0 görürseniz, bu şube aşağı gitmek,
Biz 1 görürseniz, bu şube aşağı gitmek,

87
00:04:11,800 --> 00:04:12,900
ve benzeri ve benzerleri.

88
00:04:12,900 --> 00:04:14,060
Peki, bu ne anlama geliyor?

89
00:04:14,060 --> 00:04:16,519
Eh, bu demektir
Her kavşak noktasında

90
00:04:16,519 --> 00:04:19,260
ve her düğüm
orta ve her dal,

91
00:04:19,260 --> 00:04:23,020
olası 10 vardır
biz gidebiliriz yerler.

92
00:04:23,020 --> 00:04:27,690
Yani 10 göstericiler vardır
Her yerden.

93
00:04:27,690 --> 00:04:30,610
>> Çalışır, bir nereden bulabilirim ve bu
biri için korkutucu biraz

94
00:04:30,610 --> 00:04:34,460
kim bir sürü yok
önce bilgisayar bilimlerinde deneyim.

95
00:04:34,460 --> 00:04:35,960
Ama çalışır gerçekten çok harika.

96
00:04:35,960 --> 00:04:37,793
Ve varsa
onlarla çalışmak için bir şans

97
00:04:37,793 --> 00:04:40,420
ve kazmak-in tutardır
ve onlarla birlikte deney,

98
00:04:40,420 --> 00:04:44,234
onlar gerçekten oldukça ilginç konum
veri yapıları ile çalışmak.

99
00:04:44,234 --> 00:04:46,900
Biz bir öğe eklemek istiyorsanız
traya içine bütün yapmamız gereken

100
00:04:46,900 --> 00:04:51,360
Doğru yol inşa edildi
yaprak kökünden.

101
00:04:51,360 --> 00:04:55,390
İşte nasıl her adımda birlikte var
yol gibi görünebilir.

102
00:04:55,390 --> 00:04:59,660
Biz yeni bir veri tanımlamak için gidiyoruz
yeni bir düğüm için yapı tray çağırdı.

103
00:04:59,660 --> 00:05:02,560
>> Ve bu verilerin içinde
yapı iki parça vardır.

104
00:05:02,560 --> 00:05:05,460
Biz saklamak için gidiyoruz
Bir üniversitenin adı.

105
00:05:05,460 --> 00:05:09,410
Ve biz saklamak için gidiyoruz
işaretçiler bir dizi

106
00:05:09,410 --> 00:05:12,190
Aynı türdeki diğer düğümlere.

107
00:05:12,190 --> 00:05:14,780
Yani, yine, bu o tür
Her yerde kavramının

108
00:05:14,780 --> 00:05:18,567
biz 10 mümkünse vardır
biz gidebiliriz yerler.

109
00:05:18,567 --> 00:05:20,150
Biz 0 görürseniz, bu şube aşağı gitmek.

110
00:05:20,150 --> 00:05:22,690
Biz 1 görürseniz, bu şube,
ve benzerleri ve benzeri ve benzerleri.

111
00:05:22,690 --> 00:05:25,160
Biz 9 derseniz, biz bu şube aşağı gitmek.

112
00:05:25,160 --> 00:05:28,220
Her kavşak noktasında Yani
Biz 10 olası yerlere gidebilir.

113
00:05:28,220 --> 00:05:35,740
Yani her düğüm 10 işaretçiler içermelidir
10 diğer düğümlere diğer düğümlere için.

114
00:05:35,740 --> 00:05:39,810
>> Ve biz saklıyoruz veri
üniversitenin sadece isim.

115
00:05:39,810 --> 00:05:41,060
Yani bir tray yapalım.

116
00:05:41,060 --> 00:05:44,860
En bir çift eklemek edelim
Bizim tray içine öğeleri.

117
00:05:44,860 --> 00:05:46,740
Çok üstünde Yani
Bu bizim kök düğümdür.

118
00:05:46,740 --> 00:05:49,740
Bu muhtemelen bir şey olacak
Eğer declare global olarak gidiyoruz.

119
00:05:49,740 --> 00:05:53,450
Ve bakımını global olarak gidiyoruz
her zaman bu düğüme bir işaretçi.

120
00:05:53,450 --> 00:05:55,360
>> Sen demek için gidiyoruz
Kök eşittir, ve sen

121
00:05:55,360 --> 00:05:57,580
Kendinize tray düğümü malloc olacak.

122
00:05:57,580 --> 00:05:59,850
Ve asla gidiyoruz
Yine kök dokunun.

123
00:05:59,850 --> 00:06:02,300
Istediğiniz her zaman
gezinme başlayın,

124
00:06:02,300 --> 00:06:05,802
Başka işaretçi ayarlamak
Böyle trav olarak, kök eşit,

125
00:06:05,802 --> 00:06:07,760
bu örnek, bir
videoları benim birçok kullanmak

126
00:06:07,760 --> 00:06:11,090
Burada yığınlar ve kuyruklar üzerinde
ve bağlantı listeleri vb.

127
00:06:11,090 --> 00:06:13,320
>> Başka bir işaretçi ayarlamak
kastetmek için trav denir.

128
00:06:13,320 --> 00:06:15,890
Ve gezinmek için trav kullanın
Veri yapısı ile.

129
00:06:15,890 --> 00:06:17,500
Yani bu nasıl görünebileceğini görelim.

130
00:06:17,500 --> 00:06:19,880
Yani şimdi, ne
Bir düğüm benziyor?

131
00:06:19,880 --> 00:06:22,920
Peki, sadece bizim veri olarak
yapı beyanı, belirtilen

132
00:06:22,920 --> 00:06:26,906
Biz bir dize sahip olan
Bu durumda boştur.

133
00:06:26,906 --> 00:06:27,780
Burada bir şey yok.

134
00:06:27,780 --> 00:06:29,550
>> Ve 10 işaretçiler bir dizi.

135
00:06:29,550 --> 00:06:31,790
Ve şimdi, biz sadece
Bu tray 1 düğümü vardır.

136
00:06:31,790 --> 00:06:33,110
İçinde başka bir şey yok.

137
00:06:33,110 --> 00:06:36,020
Yani bunların hepsi 10
nokta işaretçileri null.

138
00:06:36,020 --> 00:06:38,090
O kırmızı işaret buydu.

139
00:06:38,090 --> 00:06:39,500
>> En dize Harvard eklemek edelim.

140
00:06:39,500 --> 00:06:41,999
En University eklemek edelim
Bu tray içine Harvard, burada

141
00:06:41,999 --> 00:06:43,940
Yıl 1636 yılında kuruldu.

142
00:06:43,940 --> 00:06:48,220
Biz anahtarı kullanmak istiyorum,
1636, biz olduğun yerde bize

143
00:06:48,220 --> 00:06:50,140
tray de Harvard'a saklamak için gidiyoruz.

144
00:06:50,140 --> 00:06:51,470
Şimdi, bunu nasıl yapabilirim?

145
00:06:51,470 --> 00:06:52,886
>> Böyle bir şey olabilir.

146
00:06:52,886 --> 00:06:54,160
Biz kökünde başlar.

147
00:06:54,160 --> 00:06:56,920
Ve biz gidebiliriz bu 10 yerler var.

148
00:06:56,920 --> 00:06:59,900
Kök herhangi gibi
tray diğer düğüm.

149
00:06:59,900 --> 00:07:02,850
Buradan gidebilirsiniz 10 yer vardır.

150
00:07:02,850 --> 00:07:07,215
>> Nerede muhtemelen istiyoruz
Anahtar 1636 ise gitmek için?

151
00:07:07,215 --> 00:07:08,340
Gerçekten iki seçenek var.

152
00:07:08,340 --> 00:07:08,450
Sağ.

153
00:07:08,450 --> 00:07:10,825
Biz anahtarı oluşturabilirsiniz
sağdan sola ve 6 ile başlamak.

154
00:07:10,825 --> 00:07:14,000
Ya anahtarı inşa edebileceğini
soldan sağa ve 1 ile başlar.

155
00:07:14,000 --> 00:07:16,140
>> Muhtemelen daha var
bir insan olarak sezgisel

156
00:07:16,140 --> 00:07:18,110
bir sorunumuz olacak anlamak için
Sadece sağa sola gidin.

157
00:07:18,110 --> 00:07:21,140
Ve bu yüzden eklemek istiyorsanız
Bu tray içine Harvard

158
00:07:21,140 --> 00:07:23,560
Herhalde başlamak istiyorum
kökünden başlayarak,

159
00:07:23,560 --> 00:07:25,720
Benim 10 seçenekleri bakarak
Önümde, söyleyerek

160
00:07:25,720 --> 00:07:28,700
Ben 1 yolda gitmek istiyorum.

161
00:07:28,700 --> 00:07:29,700
TAMAM.

162
00:07:29,700 --> 00:07:31,810
>> Şimdi, 1 yol şu anda boş olduğunu.

163
00:07:31,810 --> 00:07:35,920
Yani bu yolda devam etmek istiyorsanız
traya içine bu öğe eklemek için,

164
00:07:35,920 --> 00:07:42,040
Ben 1 var, yeni bir düğüm malloc zorunda
Orada gelin ve sonra gitmek iyi değilim.

165
00:07:42,040 --> 00:07:46,460
>> Yani temelde bir de ben
nokta nerede duruyorum

166
00:07:46,460 --> 00:07:50,270
ağaç veya kökündeki
tray ve 10 şubesi vardır.

167
00:07:50,270 --> 00:07:52,260
Ama her dal olan
Bunun önündeki kapısı.

168
00:07:52,260 --> 00:07:53,060
Sağ.

169
00:07:53,060 --> 00:07:54,850
Bir şey yok, çünkü başka var.

170
00:07:54,850 --> 00:07:56,522
Hayır güvenli geçiş.

171
00:07:56,522 --> 00:07:58,980
O hiçbir şey demektir
Bu dalların herhangi aşağı.

172
00:07:58,980 --> 00:08:02,532
Binayı başlatmak istiyorsanız
bir şey, ben kapıyı kaldırmak istiyor.

173
00:08:02,532 --> 00:08:04,490
Ben kapıyı kaldırmak istiyorum
1 numaralı ön.

174
00:08:04,490 --> 00:08:05,698
Ve ben aşağı yürümek istiyorum.

175
00:08:05,698 --> 00:08:08,060
Ve ben kurmak istiyorum
Benim için başka bir yere gitmek için.

176
00:08:08,060 --> 00:08:09,470
>> Ve ben burada yaptığım buydu.

177
00:08:09,470 --> 00:08:11,430
Yani 1 artık null işaret ediyor.

178
00:08:11,430 --> 00:08:13,830
Ben şimdi burada aşağı gitmek güvenli söyledim.

179
00:08:13,830 --> 00:08:15,789
Ben başka bir düğüm inşa.

180
00:08:15,789 --> 00:08:18,330
Ve ben bu düğüme olsun, ben
yapmak için başka bir karar var.

181
00:08:18,330 --> 00:08:20,890
Nereye buradan gitmek için gidiyorum?

182
00:08:20,890 --> 00:08:22,700
>> Eh, zaten 1 aşağı gittin.

183
00:08:22,700 --> 00:08:24,470
Yani şimdi ben muhtemelen 6 aşağı gitmek istiyorum.

184
00:08:24,470 --> 00:08:24,970
Sağ.

185
00:08:24,970 --> 00:08:27,100
Yine, ben seçebilirsiniz 10 yerler var.

186
00:08:27,100 --> 00:08:30,060
Öyleyse şimdi numarayı 6 aşağı gidelim.

187
00:08:30,060 --> 00:08:32,280
Yani kapıyı açık
6 numaralı önüne.

188
00:08:32,280 --> 00:08:33,250
Ve ben oraya yürüyorum.

189
00:08:33,250 --> 00:08:34,580
Ve ben başka bir düğüm oluşturmak.

190
00:08:34,580 --> 00:08:37,630
Ve ben başka birleşim noktası ulaştınız.

191
00:08:37,630 --> 00:08:40,289
>> Yine, ben 10 seçeneğiniz var
Ben nereye için.

192
00:08:40,289 --> 00:08:42,799
I, 1 ile 6 arasında hareket ettik.

193
00:08:42,799 --> 00:08:44,215
Yani şimdi ben muhtemelen 3 gitmek istiyorum.

194
00:08:44,215 --> 00:08:45,381
3, hiçbir yerde gidebilirsiniz var.

195
00:08:45,381 --> 00:08:48,980
Yani yolu temizlemek zorunda
ve kendime yeni bir alan oluşturmak.

196
00:08:48,980 --> 00:08:50,870
Ve sonra ben gitmek istersiniz 3, gelen?

197
00:08:50,870 --> 00:08:52,450
Ben aşağı 6 gitmek istiyorum.

198
00:08:52,450 --> 00:08:54,770
>> Ve yine, ben vardı
Bunu yapmanın yolu temizleyin.

199
00:08:54,770 --> 00:08:59,179
Yani şimdi ben oluşturmak eklemek için benim anahtar kullandım
düğümler bu trie inşa etmeye başlar ve.

200
00:08:59,179 --> 00:09:00,220
Ben kökünde başladım.

201
00:09:00,220 --> 00:09:03,666
Ben 1636 aşağı gittim.

202
00:09:03,666 --> 00:09:05,540
Ve şimdi dibinde değilim
Orada bu düğüm üzerindeki.

203
00:09:05,540 --> 00:09:06,610
Ve mümkün olabilir
Ekranda görmek.

204
00:09:06,610 --> 00:09:07,735
>> Sarý oluyor.

205
00:09:07,735 --> 00:09:10,020
Şu anda nerede budur.

206
00:09:10,020 --> 00:09:11,300
Benim anahtar yapılır.

207
00:09:11,300 --> 00:09:13,030
Benim anahtarında her pozisyonda tükettim.

208
00:09:13,030 --> 00:09:15,040
Yani daha hiç gidemem.

209
00:09:15,040 --> 00:09:17,720
Bu noktada, tüm I So
gerçekten Tamam, demek yapmanız gerekiyor.

210
00:09:17,720 --> 00:09:18,990
Bu tür bakıyor gibi oluyor
yere aşağı,

211
00:09:18,990 --> 00:09:21,115
Eğer öngören eğer
Kendinizi yolun bu tür olarak

212
00:09:21,115 --> 00:09:22,350
Farklı bağlantıları ile.

213
00:09:22,350 --> 00:09:25,800
Sıralama aşağı ve çeşit arıyor
Yerde Harvard'a boyama sprey.

214
00:09:25,800 --> 00:09:26,800
Yani, bu adı.

215
00:09:26,800 --> 00:09:28,300
Bu konumda ne olduğunu biliyorum.

216
00:09:28,300 --> 00:09:31,870
Biz kök başlar ve aşağı giderseniz
1 ve 6 ve daha sonra 3 ve 6,

217
00:09:31,870 --> 00:09:32,780
neredeyiz?

218
00:09:32,780 --> 00:09:35,640
Peki biz aşağı bakmak durumunda
ve biz o zaman, Harvard bkz

219
00:09:35,640 --> 00:09:38,960
Biz Harvard olduğunu biliyoruz
Yolda dayalı 1636 yılında kurulan

220
00:09:38,960 --> 00:09:41,400
Bu veri yapısı uygulamak ediyoruz.

221
00:09:41,400 --> 00:09:43,177
Yani umarım açıktı.

222
00:09:43,177 --> 00:09:44,760
Biz iki eklemeleri yapmak için gidiyoruz.

223
00:09:44,760 --> 00:09:50,060
Ve umarım yardımcı olacak
bkz bu kez daha yapmış.

224
00:09:50,060 --> 00:09:52,210
>> Şimdi, başka bir üniversite eklemek edelim.

225
00:09:52,210 --> 00:09:54,630
Şimdi bu tray içine Yale eklemek edelim.

226
00:09:54,630 --> 00:09:57,037
Yale 1701 yılında kurulmuştur.

227
00:09:57,037 --> 00:09:58,870
Yani biz başlayacağız
Kök, biz her zaman yaptığımız gibi.

228
00:09:58,870 --> 00:09:59,890
Ve biz kastetmek işaretçi ayarlayın.

229
00:09:59,890 --> 00:10:01,624
Biz gezinmek için kullanan gidiyoruz.

230
00:10:01,624 --> 00:10:03,790
Biz istediğiniz ilk şey
do 1 yolda gidin.

231
00:10:03,790 --> 00:10:05,830
Bu bizim anahtarın ilk basamak var.

232
00:10:05,830 --> 00:10:08,420
Neyse ki, olsa da, biz değil
Herhangi bir esere bu sefer yapmak zorunda.

233
00:10:08,420 --> 00:10:09,919
1 yol zaten temizlenmiş oldu.

234
00:10:09,919 --> 00:10:13,520
Daha önce ben onu temizlenir
1636 de Harvard'a takmadan oldu.

235
00:10:13,520 --> 00:10:18,090
Yani güvenle taşıyabilirsiniz
1 aşağı ve sadece oraya gitmek.

236
00:10:18,090 --> 00:10:20,150
1 aşağı hareket edebilirsiniz.

237
00:10:20,150 --> 00:10:22,930
>> Şimdi olsa, ben 7 gitmek istiyorum.

238
00:10:22,930 --> 00:10:24,280
Ben 6'da yolu temizledi.

239
00:10:24,280 --> 00:10:27,050
Ben güvenle yapabilirsiniz biliyorum
6 yolda devam edin.

240
00:10:27,050 --> 00:10:29,220
Ama 7 yolda devam etmek gerekir.

241
00:10:29,220 --> 00:10:30,580
Peki ne yapmam gerekiyor?

242
00:10:30,580 --> 00:10:35,070
Peki, daha önce olduğu gibi, sadece ihtiyaç
Kapıyı temizlemek için, yoldan çekil,

243
00:10:35,070 --> 00:10:38,740
ve 7 yolundan yeni bir düğüm oluşturmak.

244
00:10:38,740 --> 00:10:40,250
Aynen böyle.

245
00:10:40,250 --> 00:10:42,930
>> Yani şimdi ben 1 ve sonra 7 taşındım.

246
00:10:42,930 --> 00:10:45,550
Ve şimdi fark ben sayılırım
bu yeni subbranch üzerinde.

247
00:10:45,550 --> 00:10:46,050
Sağ.

248
00:10:46,050 --> 00:10:49,260
16 ila Her şey
, ben umurumda değil.

249
00:10:49,260 --> 00:10:50,720
Ben 16 şey yapmıyorum.

250
00:10:50,720 --> 00:10:51,750
Ben 17 şeyler yapıyorum.

251
00:10:51,750 --> 00:10:58,380
>> Şimdi 17'den, ben var
çeşit burada yeni yollar yangını.

252
00:10:58,380 --> 00:11:00,462
Bir sonraki basamak benim anahtar 0'dır.

253
00:11:00,462 --> 00:11:01,670
Ben açıkça her yerde alamıyorum.

254
00:11:01,670 --> 00:11:02,628
Ben sadece bu düğüm inşa etti.

255
00:11:02,628 --> 00:11:04,550
Yani orada hiçbir biliyorum
İleri buradan yolları.

256
00:11:04,550 --> 00:11:06,370
Bu yüzden bir kendimi yapmak zorunda.

257
00:11:06,370 --> 00:11:09,360
>> Yani yeni bir düğüm malloc
ve orada 0 nokta var.

258
00:11:09,360 --> 00:11:12,770
Ve sonra bir kez daha, ben malloc bir
Yeni düğüm ve orada bir nokta var.

259
00:11:12,770 --> 00:11:15,870
Yine, benim anahtar, 1701 tükettik.

260
00:11:15,870 --> 00:11:18,472
Yani aşağı bakmak ve ben Yale boya sprey.

261
00:11:18,472 --> 00:11:19,680
İşte bu düğümün adı.

262
00:11:19,680 --> 00:11:24,660
>> Ve şimdi ben hiç Yale görmek için gerekirse
Bu tray de, ben kökünde başlayacak olan,

263
00:11:24,660 --> 00:11:27,060
Ben 1701 inmek ve aşağı bakmak.

264
00:11:27,060 --> 00:11:30,030
Ve ben Yale sprey görürsem
Daha sonra, zemin üzerine boyalı

265
00:11:30,030 --> 00:11:32,200
Ben Yale Bu tray var biliyorum.

266
00:11:32,200 --> 00:11:32,950
Bir kere daha yapalım.

267
00:11:32,950 --> 00:11:36,430
Şimdi bu içine Dartmouth eklemek edelim
1769 yılında kurulan tray.

268
00:11:36,430 --> 00:11:37,750
>> Yine kökünden başlayın.

269
00:11:37,750 --> 00:11:39,445
Benim anahtar Benim ilk basamak 1'dir.

270
00:11:39,445 --> 00:11:40,820
Ben güvenle bu yolda hareket edebilirsiniz.

271
00:11:40,820 --> 00:11:42,400
Bu zaten var.

272
00:11:42,400 --> 00:11:44,040
Benim anahtar sonraki basamak 7'dir.

273
00:11:44,040 --> 00:11:45,890
Ben güvenle bu yolda hareket edebilirsiniz.

274
00:11:45,890 --> 00:11:47,540
O da var.

275
00:11:47,540 --> 00:11:49,000
>> Benim sonraki 6.

276
00:11:49,000 --> 00:11:52,860
Buradan, Şu anda benim yerden
O orta düğüm orada sarı,

277
00:11:52,860 --> 00:11:56,060
6 Şu anda kapalı kilitli.

278
00:11:56,060 --> 00:11:58,830
Ben o yolda gitmek isterseniz,
Kendim oluşturmamız gerekiyor.

279
00:11:58,830 --> 00:12:02,250
Yani yeni bir düğüm malloc edeceğiz
ve orada 6 nokta var.

280
00:12:02,250 --> 00:12:04,250
Ve sonra, yine, ben
burada yeni yollar yanan.

281
00:12:04,250 --> 00:12:10,750
>> Yani yeni bir düğüm malloc böylece
Şimdi o node-- yol numarası 9-- ve

282
00:12:10,750 --> 00:12:13,584
Ben 1769 seyahat ve ben aşağı bakarsanız.

283
00:12:13,584 --> 00:12:15,500
Hiçbir şey şu anda yok
Orada boyalı sprey.

284
00:12:15,500 --> 00:12:16,930
Ben Dartmouth yazabilirsiniz.

285
00:12:16,930 --> 00:12:20,710
Ve ben ekledikten
Traya içine Dartmouth.

286
00:12:20,710 --> 00:12:23,450
>> Yani takmadan var
traya içine işler.

287
00:12:23,450 --> 00:12:25,384
Şimdi şeylere aramak istiyorum.

288
00:12:25,384 --> 00:12:27,050
Nasıl tray şeyler arayabilirim?

289
00:12:27,050 --> 00:12:29,170
Peki, bu hemen hemen aynı fikir.

290
00:12:29,170 --> 00:12:33,620
Şimdi biz sadece anahtar rakamlarını kullanın
Biz kök gezinebilirsiniz görmek için

291
00:12:33,620 --> 00:12:37,170
Biz tray gitmek istediğiniz yere.

292
00:12:37,170 --> 00:12:41,620
>> Biz o zaman, herhangi bir noktada çıkmaz vurursanız
biz bu eleman var olamayacağını biliyorum

293
00:12:41,620 --> 00:12:44,500
ya da başka bu yolu olur
Zaten temizlendi.

294
00:12:44,500 --> 00:12:45,930
Biz tüm yol yaparsanız
sonunda, tüm yapmamız gereken

295
00:12:45,930 --> 00:12:48,471
aşağı bakmak ve bu olmadığını görmek olduğunu
Aradığımız elemanı.

296
00:12:48,471 --> 00:12:49,335
Bu başarı ise.

297
00:12:49,335 --> 00:12:52,610
O değilse, başarısız.

298
00:12:52,610 --> 00:12:54,940
>> Yani aramak için izin
Bu tray Harvard.

299
00:12:54,940 --> 00:12:56,020
Biz kökünde başlar.

300
00:12:56,020 --> 00:12:58,228
Ve yine, biz gidiyoruz
Bir kastetmek işaretçi oluşturmak

301
00:12:58,228 --> 00:12:59,390
bizim için hamle yapmak.

302
00:12:59,390 --> 00:13:02,080
Root itibaren biz biliyoruz
gitmemiz gereken ilk yer, 1

303
00:13:02,080 --> 00:13:03,390
biz yapabiliriz?

304
00:13:03,390 --> 00:13:03,982
Evet yapabiliriz.

305
00:13:03,982 --> 00:13:04,690
Eğer güvenli var.

306
00:13:04,690 --> 00:13:06,660
Biz oraya gidebiliriz.

307
00:13:06,660 --> 00:13:08,440
>> Şimdi, biz gitmek gerekir bir sonraki yer 6'dır.

308
00:13:08,440 --> 00:13:10,557
6 yolu buradan var mıdır?

309
00:13:10,557 --> 00:13:11,140
Evet, öyle.

310
00:13:11,140 --> 00:13:12,690
Biz 6 yolda gidebilirsiniz.

311
00:13:12,690 --> 00:13:13,905
Ve biz burada bitirmek.

312
00:13:13,905 --> 00:13:16,130
>> Buradan 3 yolda gidebilir miyim?

313
00:13:16,130 --> 00:13:18,450
Peki, bu çıkıyor gibi,
evet, o da var.

314
00:13:18,450 --> 00:13:20,790
Ve biz burada 6 yolda alabilirim?

315
00:13:20,790 --> 00:13:21,982
Evet yapabiliriz.

316
00:13:21,982 --> 00:13:24,002
>> Biz oldukça cevap değil
Henüz bir soru.

317
00:13:24,002 --> 00:13:25,710
Bir tane daha var hala
şimdi adım,

318
00:13:25,710 --> 00:13:28,520
Biz aşağı bakmak gerekir ve
Bu actually-- olmadığını görmek

319
00:13:28,520 --> 00:13:32,660
Harvard arıyorsanız, yani
biz anahtar egzoz sonra ne buldun?

320
00:13:32,660 --> 00:13:35,430
Örneğin biz burada kullanıyorsanız,
yıllar hep dört basamak vardır.

321
00:13:35,430 --> 00:13:40,280
Ama örnek nerede kullanıyor olabilirsiniz
Eğer kelimelerin sözlük depoluyor.

322
00:13:40,280 --> 00:13:44,060
>> Ve böylece yerine 10 işaretçiler sahip
Benim konum, sen 26 olabilir.

323
00:13:44,060 --> 00:13:46,040
Alfabenin her harfi için bir.

324
00:13:46,040 --> 00:13:50,350
Ve yarasa gibi bazı kelimeler vardır,
bu, örneğin toplu bir alt kümesidir.

325
00:13:50,350 --> 00:13:53,511
Ve sen olsun bile
anahtarın ucunu ve aşağı bakmak,

326
00:13:53,511 --> 00:13:55,260
ne görüyorsun olmayabilir
Aradığınız.

327
00:13:55,260 --> 00:13:58,500
>> Yani her zaman hareket ettirmek zorunda
Tüm yol ve daha sonra

328
00:13:58,500 --> 00:14:01,540
başarıyla mümkün olsaydı
tüm yolu travers,

329
00:14:01,540 --> 00:14:03,440
aşağı bakmak ve bir final onay yapmak.

330
00:14:03,440 --> 00:14:05,120
Ben arıyorum şey mi?

331
00:14:05,120 --> 00:14:07,740
Eh, ben başladıktan sonra aşağı bakmak
üstünde ve 1636 gidiş.

332
00:14:07,740 --> 00:14:08,240
Ben aşağı bakmak.

333
00:14:08,240 --> 00:14:09,400
Ben Harvard görüyorum.

334
00:14:09,400 --> 00:14:11,689
Yani, evet, ben başardı.

335
00:14:11,689 --> 00:14:13,980
Ne olursa ne arıyorum
olsa da, tray değildir.

336
00:14:13,980 --> 00:14:17,200
Ben Princeton arıyorum ne olur,
hangi 1746 yılında kurulmuştur.

337
00:14:17,200 --> 00:14:20,875
Ve böylece 1746 benim anahtar olur
traya gezinmek için.

338
00:14:20,875 --> 00:14:22,040
Eh, ben kökünde başlar.

339
00:14:22,040 --> 00:14:24,760
Ve ben istiyorum ilk yer
1 yolda gider.

340
00:14:24,760 --> 00:14:25,590
Bunu yapabilir miyim?

341
00:14:25,590 --> 00:14:26,490
Evet yapabilirim.

342
00:14:26,490 --> 00:14:28,730
>> Orada 7 yolda gidebilir miyim?

343
00:14:28,730 --> 00:14:29,230
Evet yapabilirim.

344
00:14:29,230 --> 00:14:30,750
O da var.

345
00:14:30,750 --> 00:14:32,460
Ama burada 4 yolda gidebilir?

346
00:14:32,460 --> 00:14:35,550
Bu can, soruyu soran gibi
Ben küçük kare aşağı devam

347
00:14:35,550 --> 00:14:37,114
ben sarı renkte vurgulanır ettik?

348
00:14:37,114 --> 00:14:38,030
Orada hiçbir şey yok.

349
00:14:38,030 --> 00:14:38,610
Sağ.

350
00:14:38,610 --> 00:14:41,310
>> Hiçbir şekilde ileri 4 yolda var.

351
00:14:41,310 --> 00:14:46,480
Princeton, bu tray olduğu 4 bu takdirde
zaten bizim için temizlenmiş olurdu.

352
00:14:46,480 --> 00:14:49,130
Ve böylece bu noktada
Biz ölü sonuna ulaştınız.

353
00:14:49,130 --> 00:14:50,250
Biz daha gidemem.

354
00:14:50,250 --> 00:14:53,440
Ve böylece biz, kesin söyleyebiliriz.

355
00:14:53,440 --> 00:14:56,760
Princeton Bu tray mevcut değil.

356
00:14:56,760 --> 00:14:58,860
>> Peki bu ne anlama geliyor?

357
00:14:58,860 --> 00:14:59,360
Sağ.

358
00:14:59,360 --> 00:15:01,000
Burada devam eden bir sürü var.

359
00:15:01,000 --> 00:15:02,500
Her yerde işaretçiler var.

360
00:15:02,500 --> 00:15:04,249
Ve, gibi görebilirsiniz
Sadece, diyagramından

361
00:15:04,249 --> 00:15:07,010
düğümler bir sürü olduğunu
tür etrafında uçuyor.

362
00:15:07,010 --> 00:15:13,480
Ama biz istedik her zaman fark
bir şey tray içinde olup olmadığını kontrol edin

363
00:15:13,480 --> 00:15:15,000
biz sadece 4 hamle yapmak zorunda kaldı.

364
00:15:15,000 --> 00:15:17,208
>> Biz istedik her zaman
tray şey eklemek

365
00:15:17,208 --> 00:15:20,440
biz muhtemelen, 4 hamle yapmak zorunda
Yol boyunca bazı şeyler mallocing.

366
00:15:20,440 --> 00:15:23,482
Biz takıldığında Ama biz gördüğümüz gibi
Traya içine Dartmouth,

367
00:15:23,482 --> 00:15:25,940
Bazen yolun bazı
zaten bizim için temizlenmiş olabilir.

368
00:15:25,940 --> 00:15:30,520
Ve böylece bizim trie alır gibi büyük ve
Daha büyük, daha az çalışmalarının her zaman yapmak zorunda

369
00:15:30,520 --> 00:15:32,270
yeni şeyler eklemek için
biz zaten ettik çünkü

370
00:15:32,270 --> 00:15:35,746
ara bir sürü inşa
Yol boyunca dalları.

371
00:15:35,746 --> 00:15:38,370
Biz sadece şimdiye bakmak varsa
4 şey 4 sadece bir sabittir.

372
00:15:38,370 --> 00:15:41,750
Biz gerçekten bir tür yaklaşıyor
zaman sabiti ekleme

373
00:15:41,750 --> 00:15:44,501
ve sabit zaman arama.

374
00:15:44,501 --> 00:15:47,500
Tradeoff, tabii ki, varlık
Bu tray olarak muhtemelen söyleyebilirim

375
00:15:47,500 --> 00:15:49,030
çok büyük.

376
00:15:49,030 --> 00:15:51,040
Bu düğümlerin her biri
çok yer kaplıyor.

377
00:15:51,040 --> 00:15:52,090
>> Ama bu değiş tokuş.

378
00:15:52,090 --> 00:15:55,260
Biz gerçekten çabuk istiyorsanız
ekleme, gerçekten hızlı silme,

379
00:15:55,260 --> 00:15:59,630
ve gerçekten hızlı arama, biz var
Verilerin bir sürü etrafında uçan var.

380
00:15:59,630 --> 00:16:03,590
Biz çok yer ayırmak zorunda
ve veri yapısı için bellek

381
00:16:03,590 --> 00:16:04,290
var olmak.

382
00:16:04,290 --> 00:16:05,415
>> Ve böylece değiş tokuş.

383
00:16:05,415 --> 00:16:07,310
Ama biz benziyor
Onu bulmuş olabilir.

384
00:16:07,310 --> 00:16:09,560
Biz bulduk olabilir
veri yapılarının Holy Grail

385
00:16:09,560 --> 00:16:12,264
Hızlı ekleme ile,
silme ve arama.

386
00:16:12,264 --> 00:16:14,430
Ve belki bu bir olacak
Uygun bir veri yapısı

387
00:16:14,430 --> 00:16:18,890
ne olursa olsun bilgi için kullanmak
Biz mağazaya çalışıyoruz.

388
00:16:18,890 --> 00:16:21,860
Ben Doug Lloyd değilim, bu CS50 olduğunu.

389
00:16:21,860 --> 00:16:23,433