1
00:00:00,000 --> 00:00:02,994
>> [Bermain muzik]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Oleh itu, kita telah inching dekat
dan lebih dekat bahawa kaedah berpotensi suci data

4
00:00:08,550 --> 00:00:13,050
struktur, satu yang kita boleh memasukkan
ke dalam, memotong daripada, dan melihat ke atas

5
00:00:13,050 --> 00:00:15,440
dalam masa yang berterusan.

6
00:00:15,440 --> 00:00:16,270
Betul.

7
00:00:16,270 --> 00:00:17,280
Itulah jenis matlamat.

8
00:00:17,280 --> 00:00:19,720
Kami mahu menjadi mampu untuk melakukan
perkara yang sangat, sangat cepat.

9
00:00:19,720 --> 00:00:22,580
>> Kami dapati ia di sini apabila
kita berbicara tentang try?

10
00:00:22,580 --> 00:00:23,670
Nah, mari kita lihat.

11
00:00:23,670 --> 00:00:25,628
Oleh itu, kita telah melihat beberapa
struktur data yang berbeza

12
00:00:25,628 --> 00:00:28,680
yang mengendalikan pemetaan
apa yang dikenali sebagai pasangan kunci-nilai,

13
00:00:28,680 --> 00:00:32,080
pemetaan sedikit data
kepada beberapa bahagian lain dari data

14
00:00:32,080 --> 00:00:36,020
supaya kita tahu di mana untuk mencari
maklumat dalam struktur.

15
00:00:36,020 --> 00:00:40,060
>> Jadi untuk pelbagai, sebagai contoh,
utama ialah indeks unsur atau pelbagai

16
00:00:40,060 --> 00:00:42,600
lokasi 0 atau pelbagai 1 dan sebagainya.

17
00:00:42,600 --> 00:00:46,140
Dan nilai adalah data
yang wujud di lokasi tersebut.

18
00:00:46,140 --> 00:00:48,550
Jadi apa yang disimpan dalam array 0?

19
00:00:48,550 --> 00:00:54,290
Apa yang disimpan dalam tatasusunan 1 berbanding hanya
0 dan 1, yang akan menjadi kunci.

20
00:00:54,290 --> 00:00:56,360
>> Dengan jadual hash ia
jenis idea yang sama.

21
00:00:56,360 --> 00:01:00,690
Dengan jadual hash, kami mempunyai hash ini
fungsi yang menjana kod hash.

22
00:01:00,690 --> 00:01:03,670
Jadi, kunci adalah kod hash data.

23
00:01:03,670 --> 00:01:06,530
Dan nilai, terutamanya
kita bercakap tentang chaining

24
00:01:06,530 --> 00:01:10,590
dalam video itu di atas meja hash,
ialah senarai dikaitkan data

25
00:01:10,590 --> 00:01:12,550
bahawa hash untuk Kodcincang itu.

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

27
00:01:14,050 --> 00:01:16,050
Bagaimana pula dengan pendekatan lain
kaedah ini, walaupun?

28
00:01:16,050 --> 00:01:21,000
Bagaimana pula dengan kaedah yang mana
utama dijamin unik,

29
00:01:21,000 --> 00:01:25,410
tidak seperti jadual hash, di mana kita boleh
berakhir dengan dua bahagian data

30
00:01:25,410 --> 00:01:27,200
mempunyai Kodcincang yang sama.

31
00:01:27,200 --> 00:01:30,020
Dan kemudian kita perlu berurusan dengan
dengan memuat menyelesaikan sesuatu atau lebih

32
00:01:30,020 --> 00:01:33,340
sebaik-baiknya chaining untuk menyelesaikan masalah itu.

33
00:01:33,340 --> 00:01:37,520
>> Oleh sebab itu kami boleh menjamin
yang utama kita akan menjadi unik.

34
00:01:37,520 --> 00:01:39,690
Dan apa jika nilai kita adalah
hanya sesuatu semudah

35
00:01:39,690 --> 00:01:44,080
sebagai benar dan palsu yang memberitahu kita sama ada
atau tidak bahawa sekeping maklumat

36
00:01:44,080 --> 00:01:45,610
wujud dalam struktur?

37
00:01:45,610 --> 00:01:48,180
A Boolean boleh menjadi semudah sedikit.

38
00:01:48,180 --> 00:01:52,660
Realistik ia mungkin
bait lebih mungkin daripada sedikit.

39
00:01:52,660 --> 00:01:55,410
Tetapi itu lebih kecil daripada
menyimpan mungkin rentetan 50 aksara,

40
00:01:55,410 --> 00:01:57,360
contohnya.

41
00:01:57,360 --> 00:02:02,210
>> Jadi cuba, sama dengan hash jadual,
yang menggabungkan tatasusunan dan senarai bersambung,

42
00:02:02,210 --> 00:02:05,790
cuba menggabungkan tatasusunan,
struktur, dan petunjuk

43
00:02:05,790 --> 00:02:08,509
bersama-sama untuk menyimpan data dalam
cara yang menarik itu

44
00:02:08,509 --> 00:02:11,550
cukup berbeza daripada
apa-apa yang kita lihat setakat ini.

45
00:02:11,550 --> 00:02:16,750
Sekarang kita menggunakan data sebagai hala tuju yang
untuk mengemudi struktur data ini.

46
00:02:16,750 --> 00:02:18,710
Dan jika kita boleh mengikuti
pelan tindakan itu, jika kita boleh

47
00:02:18,710 --> 00:02:22,390
mengikut data dari
awal hingga akhir, kita akan

48
00:02:22,390 --> 00:02:24,945
tahu sama ada data yang
wujud di indone itu.

49
00:02:24,945 --> 00:02:28,310
>> Dan jika kita tidak boleh ikut peta
dari bermaksud untuk menamatkan sama sekali,

50
00:02:28,310 --> 00:02:30,600
data tidak boleh wujud.

51
00:02:30,600 --> 00:02:32,890
Sekali lagi, kunci di sini adalah
dijamin unik.

52
00:02:32,890 --> 00:02:36,020
Dan sebagainya tidak seperti jadual hash, kita akan tidak pernah
perlu berurusan dengan perlanggaran di sini.

53
00:02:36,020 --> 00:02:39,090
Dan tidak ada dua bahagian data
telah betul-betul pelan hala tuju yang sama

54
00:02:39,090 --> 00:02:40,530
kecuali data yang serupa.

55
00:02:40,530 --> 00:02:44,580
>> Jika kita memasukkan John, kemudian
kita mencari John.

56
00:02:44,580 --> 00:02:47,430
Itu dua keping serupa
data, betul, kita sedang melalui.

57
00:02:47,430 --> 00:02:49,880
Tetapi jika tidak, mana-mana
dua keping data adalah

58
00:02:49,880 --> 00:02:52,750
dijamin untuk mempunyai peta jalan yang unik
melalui struktur data ini.

59
00:02:52,750 --> 00:02:56,210
Dan kita akan lihat pada
visual ini dalam hanya seketika.

60
00:02:56,210 --> 00:02:58,810
>> Kami akan melakukan ini dengan cuba untuk
mewujudkan satu struktur data baru,

61
00:02:58,810 --> 00:03:00,564
pemetaan pasangan nilai utama berikut.

62
00:03:00,564 --> 00:03:03,480
Dalam kes ini, kita tidak akan menggunakan
sesuatu yang mudah seperti yang Boolean.

63
00:03:03,480 --> 00:03:06,200
Kami benar-benar akan menyimpan tali.

64
00:03:06,200 --> 00:03:08,690
Dan tali yang akan
menjadi nama sebuah universiti.

65
00:03:08,690 --> 00:03:12,140
>> Dan kunci akan menjadi tahun
apabila universiti yang diasaskan.

66
00:03:12,140 --> 00:03:15,380
Semua tahun bagi universiti
akan menjadi empat digit.

67
00:03:15,380 --> 00:03:19,840
Dan dengan itu kita akan menggunakan orang-orang empat digit untuk
menavigasi melalui struktur data ini.

68
00:03:19,840 --> 00:03:22,270
Dan kita akan melihat, sekali lagi, bagaimana
kita berbuat demikian dalam masa satu saat.

69
00:03:22,270 --> 00:03:25,110
>> Pada akhir jalan,
kita akan melihat nama

70
00:03:25,110 --> 00:03:30,250
universiti yang sepadan
kepada kekunci itu, mereka empat digit.

71
00:03:30,250 --> 00:03:34,390
Idea asas di sebalik indone a
adalah kita mempunyai laluan pusat.

72
00:03:34,390 --> 00:03:35,640
Jadi berfikir mengenainya seperti pokok.

73
00:03:35,640 --> 00:03:39,211
Dan ini adalah sama dalam ejaan
dan konsepnya dengan pokok.

74
00:03:39,211 --> 00:03:41,460
Secara umumnya apabila kita berfikir tentang
pokok di dunia sebenar,

75
00:03:41,460 --> 00:03:44,090
mereka mempunyai akar yang dalam yang
tanah dan mereka membesar menaik

76
00:03:44,090 --> 00:03:46,830
dan mereka mempunyai cawangan
dan mereka mempunyai daun.

77
00:03:46,830 --> 00:03:49,450
Dan pada dasarnya idea
indone adalah sama,

78
00:03:49,450 --> 00:03:51,755
kecuali akar yang berlabuh
di suatu tempat di langit.

79
00:03:51,755 --> 00:03:53,130
Dan daun di bahagian bawah.

80
00:03:53,130 --> 00:03:55,750
>> Jadi ia adalah jenis seperti mengambil pokok
dan hanya membalik terbalik.

81
00:03:55,750 --> 00:03:56,880
Tetapi masih terdapat cawangan.

82
00:03:56,880 --> 00:03:59,463
Dan orang-orang akan menjadi laluan kami,
mereka akan menjadi hubungan kami

83
00:03:59,463 --> 00:04:02,220
dari akar ke daun.

84
00:04:02,220 --> 00:04:04,200
Dalam kes ini, orang-orang
laluan, orang-orang cawangan

85
00:04:04,200 --> 00:04:08,490
dilabel dengan digit yang memberitahu kita
yang cara untuk pergi dari mana kita berada.

86
00:04:08,490 --> 00:04:11,800
>> Jika kita lihat 0, kita pergi ke cawangan ini,
jika kita melihat 1, kita turun cawangan ini,

87
00:04:11,800 --> 00:04:12,900
dan sebagainya dan sebagainya.

88
00:04:12,900 --> 00:04:14,060
Nah, apa maknanya?

89
00:04:14,060 --> 00:04:16,519
Nah, itu bermakna
pada setiap titik persimpangan

90
00:04:16,519 --> 00:04:19,260
dan setiap nod dalam
pertengahan dan setiap cawangan,

91
00:04:19,260 --> 00:04:23,020
terdapat 10 mungkin
tempat-tempat yang kita boleh pergi.

92
00:04:23,020 --> 00:04:27,690
Jadi terdapat 10 petunjuk
dari setiap lokasi.

93
00:04:27,690 --> 00:04:30,610
>> Dan di sinilah try boleh mendapatkan
sedikit menakutkan bagi seseorang

94
00:04:30,610 --> 00:04:34,460
siapa yang tidak mempunyai banyak
pengalaman dalam bidang sains komputer sebelum ini.

95
00:04:34,460 --> 00:04:35,960
Tetapi cuba benar-benar cukup menggerunkan.

96
00:04:35,960 --> 00:04:37,793
Dan jika anda mempunyai
peluang untuk bekerja dengan mereka

97
00:04:37,793 --> 00:04:40,420
dan anda bersedia untuk menggali masuk
dan bereksperimen dengan mereka,

98
00:04:40,420 --> 00:04:44,234
mereka benar-benar agak menarik
struktur data untuk bekerja dengan.

99
00:04:44,234 --> 00:04:46,900
Jika kita mahu memasukkan unsur
ke dalam indone, semua perlu kita lakukan

100
00:04:46,900 --> 00:04:51,360
adalah membina jalan yang betul
dari akar ke daun.

101
00:04:51,360 --> 00:04:55,390
Berikut adalah apa yang setiap langkah
cara mungkin kelihatan seperti.

102
00:04:55,390 --> 00:04:59,660
Kami akan menentukan data baru
struktur bagi nod baru dipanggil indone a.

103
00:04:59,660 --> 00:05:02,560
>> Dan di dalam data yang
struktur terdapat dua keping.

104
00:05:02,560 --> 00:05:05,460
Kami akan menyimpan
menamakan sebuah universiti.

105
00:05:05,460 --> 00:05:09,410
Dan kita akan menyimpan
pelbagai petunjuk

106
00:05:09,410 --> 00:05:12,190
untuk nod lain dari jenis yang sama.

107
00:05:12,190 --> 00:05:14,780
Jadi, sekali lagi, ini adalah seperti itu
daripada konsep di mana-mana

108
00:05:14,780 --> 00:05:18,567
kami, kami di 10 mungkin
tempat kita boleh pergi.

109
00:05:18,567 --> 00:05:20,150
Jika kita lihat 0, kita pergi ke cawangan ini.

110
00:05:20,150 --> 00:05:22,690
Jika kita melihat 1, cawangan ini,
dan sebagainya dan sebagainya dan sebagainya.

111
00:05:22,690 --> 00:05:25,160
Jika kita mengatakan 9, kita turun cawangan ini.

112
00:05:25,160 --> 00:05:28,220
Jadi pada setiap titik persimpangan,
kita boleh pergi 10 tempat mungkin.

113
00:05:28,220 --> 00:05:35,740
Jadi setiap nod mempunyai mengandungi 10 petunjuk
kepada nod yang lain, untuk 10 nod lain.

114
00:05:35,740 --> 00:05:39,810
>> Dan data yang kita menyimpan adalah
hanya nama universiti.

115
00:05:39,810 --> 00:05:41,060
Jadi mari kita membina indone a.

116
00:05:41,060 --> 00:05:44,860
Mari kita memasukkan pasangan
item ke dalam indone kami.

117
00:05:44,860 --> 00:05:46,740
Jadi pada bahagian paling atas,
ini adalah nod akar kami.

118
00:05:46,740 --> 00:05:49,740
Ini mungkin akan menjadi sesuatu
anda akan mengisytiharkan secara global.

119
00:05:49,740 --> 00:05:53,450
Dan anda akan secara global mengekalkan
penunjuk kepada nod ini sentiasa.

120
00:05:53,450 --> 00:05:55,360
>> Anda akan berkata,
akar sama, dan anda

121
00:05:55,360 --> 00:05:57,580
akan malloc diri nod indone.

122
00:05:57,580 --> 00:05:59,850
Dan anda tidak akan
menyentuh akar lagi.

123
00:05:59,850 --> 00:06:02,300
Setiap kali anda mahu
mula menavigasi melalui,

124
00:06:02,300 --> 00:06:05,802
anda menetapkan penunjuk lain
sama dengan punca, seperti trav,

125
00:06:05,802 --> 00:06:07,760
yang merupakan contoh yang saya
menggunakan dalam banyak video saya

126
00:06:07,760 --> 00:06:11,090
di sini pada susunan dan beratur
dan senarai link dan sebagainya.

127
00:06:11,090 --> 00:06:13,320
>> Anda menetapkan penunjuk lain
dipanggil trav untuk penyusuran.

128
00:06:13,320 --> 00:06:15,890
Dan anda menggunakan trav untuk mengemudi
melalui struktur data.

129
00:06:15,890 --> 00:06:17,500
Jadi mari kita lihat bagaimana ini mungkin kelihatan.

130
00:06:17,500 --> 00:06:19,880
Jadi sekarang, apa
tidak nod kelihatan seperti?

131
00:06:19,880 --> 00:06:22,920
Nah, hanya sebagai data kami
pengisytiharan struktur dinyatakan,

132
00:06:22,920 --> 00:06:26,906
kita mempunyai tali, yang
dalam kes ini adalah kosong.

133
00:06:26,906 --> 00:06:27,780
Tiada apa-apa di sini.

134
00:06:27,780 --> 00:06:29,550
>> Dan pelbagai 10 petunjuk.

135
00:06:29,550 --> 00:06:31,790
Dan sekarang, kita hanya
1 nod dalam indone ini.

136
00:06:31,790 --> 00:06:33,110
Ada apa-apa lagi di dalamnya.

137
00:06:33,110 --> 00:06:36,020
Jadi semua 10 orang
petunjuk titik ke nol.

138
00:06:36,020 --> 00:06:38,090
Itulah yang merah menunjukkan.

139
00:06:38,090 --> 00:06:39,500
>> Mari kita memasukkan tali Harvard.

140
00:06:39,500 --> 00:06:41,999
Mari kita memasukkan Universiti
Harvard ke indone ini, yang

141
00:06:41,999 --> 00:06:43,940
telah ditubuhkan pada tahun 1636.

142
00:06:43,940 --> 00:06:48,220
Kami mahu menggunakan kekunci,
1636, untuk memberitahu kami di mana kita berada

143
00:06:48,220 --> 00:06:50,140
akan menyimpan Harvard di indone itu.

144
00:06:50,140 --> 00:06:51,470
Sekarang, bagaimana kita boleh berbuat demikian?

145
00:06:51,470 --> 00:06:52,886
>> Ia mungkin kelihatan seperti ini.

146
00:06:52,886 --> 00:06:54,160
Kami bermula dari akar.

147
00:06:54,160 --> 00:06:56,920
Dan kita mempunyai 10 tempat kita boleh pergi.

148
00:06:56,920 --> 00:06:59,900
Akar adalah seperti mana-mana
nod lain indone itu.

149
00:06:59,900 --> 00:07:02,850
Terdapat 10 tempat kita boleh pergi dari sini.

150
00:07:02,850 --> 00:07:07,215
>> Di manakah kita mungkin mahu
untuk pergi jika yang penting adalah 1636?

151
00:07:07,215 --> 00:07:08,340
Ada benar-benar dua pilihan.

152
00:07:08,340 --> 00:07:08,450
Betul.

153
00:07:08,450 --> 00:07:10,825
Kita boleh membina kunci dari
kanan ke kiri dan bermula dengan 6.

154
00:07:10,825 --> 00:07:14,000
Atau kita boleh membina kunci dari
kiri ke kanan dan mulakan dengan 1.

155
00:07:14,000 --> 00:07:16,140
>> Ia mungkin lebih
intuitif sebagai manusia

156
00:07:16,140 --> 00:07:18,110
untuk memahami kita akan
hanya pergi kiri ke kanan.

157
00:07:18,110 --> 00:07:21,140
Dan jadi jika saya mahu memasukkan
Harvard ke indone ini,

158
00:07:21,140 --> 00:07:23,560
Saya mungkin ingin memulakan
dengan memulakan pada akar,

159
00:07:23,560 --> 00:07:25,720
melihat 10 pilihan saya
di depan saya, dan berkata

160
00:07:25,720 --> 00:07:28,700
Saya mahu pergi ke jalan yang 1.

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

162
00:07:29,700 --> 00:07:31,810
>> Sekarang, 1 jalan kini null.

163
00:07:31,810 --> 00:07:35,920
Jadi, jika saya mahu meneruskan ke jalan yang
untuk memasukkan elemen ini ke dalam indone itu,

164
00:07:35,920 --> 00:07:42,040
Saya mempunyai malloc nod baru, mempunyai 1
menunjukkan di sana, dan kemudian saya baik untuk pergi.

165
00:07:42,040 --> 00:07:46,460
>> Jadi saya pada dasarnya adalah di
titik di mana saya berdiri

166
00:07:46,460 --> 00:07:50,270
pada akar pokok atau
indone dan terdapat 10 cawangan.

167
00:07:50,270 --> 00:07:52,260
Tetapi setiap cawangan mempunyai
pintu di hadapannya.

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

169
00:07:53,060 --> 00:07:54,850
Oleh kerana tiada apa-apa lagi yang ada.

170
00:07:54,850 --> 00:07:56,522
Tiada laluan selamat.

171
00:07:56,522 --> 00:07:58,980
Ini bermakna bahawa tiada apa-apa
bawah mana-mana cawangan.

172
00:07:58,980 --> 00:08:02,532
Jika saya ingin memulakan bangunan
sesuatu, saya mahu mengeluarkan pintu pagar.

173
00:08:02,532 --> 00:08:04,490
Saya mahu mengeluarkan pintu gerbang
di hadapan nombor 1.

174
00:08:04,490 --> 00:08:05,698
Dan saya mahu berjalan itu.

175
00:08:05,698 --> 00:08:08,060
Dan saya mahu membina
tempat lain untuk saya pergi.

176
00:08:08,060 --> 00:08:09,470
>> Dan itulah yang saya lakukan di sini.

177
00:08:09,470 --> 00:08:11,430
Jadi 1 tidak lagi menunjuk kepada nol.

178
00:08:11,430 --> 00:08:13,830
Saya telah berkata ia adalah selamat untuk turun di sini sekarang.

179
00:08:13,830 --> 00:08:15,789
Saya membina nod yang lain.

180
00:08:15,789 --> 00:08:18,330
Dan apabila saya ke nod itu, saya
mempunyai satu lagi keputusan untuk membuat.

181
00:08:18,330 --> 00:08:20,890
Di mana saya akan pergi dari sini?

182
00:08:20,890 --> 00:08:22,700
>> Well, saya telah pergi ke bawah 1.

183
00:08:22,700 --> 00:08:24,470
Jadi sekarang saya mungkin mahu turun ke bawah 6.

184
00:08:24,470 --> 00:08:24,970
Betul.

185
00:08:24,970 --> 00:08:27,100
Sekali lagi, saya mempunyai 10 lokasi saya boleh pilih.

186
00:08:27,100 --> 00:08:30,060
Jadi mari kita kini turun nombor 6.

187
00:08:30,060 --> 00:08:32,280
Jadi saya membersihkan pintu gerbang
di hadapan nombor 6.

188
00:08:32,280 --> 00:08:33,250
Dan saya berjalan di bawah sana.

189
00:08:33,250 --> 00:08:34,580
Dan saya membina nod yang lain.

190
00:08:34,580 --> 00:08:37,630
Dan saya telah mencapai titik persimpangan lain.

191
00:08:37,630 --> 00:08:40,289
>> Sekali lagi, saya mempunyai 10 pilihan
untuk di mana saya boleh pergi.

192
00:08:40,289 --> 00:08:42,799
Saya telah berpindah 1-6.

193
00:08:42,799 --> 00:08:44,215
Jadi sekarang saya mungkin mahu pergi ke 3.

194
00:08:44,215 --> 00:08:45,381
3, tidak ada tempat yang saya boleh pergi.

195
00:08:45,381 --> 00:08:48,980
Jadi saya perlu untuk membersihkan jalan
dan membina diri saya ruang baru.

196
00:08:48,980 --> 00:08:50,870
Dan kemudian dari 3, di mana saya mahu pergi?

197
00:08:50,870 --> 00:08:52,450
Saya mahu turun ke bawah 6.

198
00:08:52,450 --> 00:08:54,770
>> Dan, sekali lagi, saya terpaksa
membersihkan jalan untuk melakukannya.

199
00:08:54,770 --> 00:08:59,179
Jadi sekarang saya telah menggunakan kekunci saya untuk memasukkan mewujudkan
nod dan mula membina indone ini.

200
00:08:59,179 --> 00:09:00,220
Saya telah memulakan pada akar.

201
00:09:00,220 --> 00:09:03,666
Saya telah pergi ke bawah 1636.

202
00:09:03,666 --> 00:09:05,540
Dan sekarang saya di bahagian bawah
terdapat pada nod itu.

203
00:09:05,540 --> 00:09:06,610
Dan anda mungkin boleh
melihatnya di skrin anda.

204
00:09:06,610 --> 00:09:07,735
>> Ia berwarna kuning.

205
00:09:07,735 --> 00:09:10,020
Itulah di mana saya kini am.

206
00:09:10,020 --> 00:09:11,300
Kekunci saya dilakukan.

207
00:09:11,300 --> 00:09:13,030
Saya telah habis setiap kedudukan dalam kunci saya.

208
00:09:13,030 --> 00:09:15,040
Jadi saya tidak boleh pergi mana-mana lagi.

209
00:09:15,040 --> 00:09:17,720
Jadi pada ketika ini, apa yang saya
benar-benar perlu lakukan adalah berkata, OK.

210
00:09:17,720 --> 00:09:18,990
Ia adalah jenis suka mencari
ke bawah di bawah,

211
00:09:18,990 --> 00:09:21,115
jika anda membayangkan
diri anda sebagai seperti ini jalan

212
00:09:21,115 --> 00:09:22,350
dengan sambungan yang berbeza.

213
00:09:22,350 --> 00:09:25,800
Semacam melihat ke bawah dan jenis
spray lukisan Harvard di atas tanah.

214
00:09:25,800 --> 00:09:26,800
Itulah nama ini.

215
00:09:26,800 --> 00:09:28,300
Tahu bahawa apa yang di lokasi ini.

216
00:09:28,300 --> 00:09:31,870
Jika kita bermula dari akar dan kita turun
1 dan kemudian 6 dan kemudian 3 dan kemudian 6,

217
00:09:31,870 --> 00:09:32,780
di mana kita?

218
00:09:32,780 --> 00:09:35,640
Baik jika kita melihat ke bawah
dan kita lihat Harvard, kemudian

219
00:09:35,640 --> 00:09:38,960
kita tahu bahawa Harvard adalah
ditubuhkan pada 1636 berdasarkan cara

220
00:09:38,960 --> 00:09:41,400
kita melaksanakan struktur data ini.

221
00:09:41,400 --> 00:09:43,177
Jadi yang diharapkan mudah.

222
00:09:43,177 --> 00:09:44,760
Kami akan melakukan dua lagi sisipan.

223
00:09:44,760 --> 00:09:50,060
Dan mudah-mudahan ia akan membantu untuk
melihat ini dilakukan dua kali lagi.

224
00:09:50,060 --> 00:09:52,210
>> Sekarang, mari kita memasukkan universiti lain.

225
00:09:52,210 --> 00:09:54,630
Mari kita memasukkan Yale ke indone ini.

226
00:09:54,630 --> 00:09:57,037
Yale ditubuhkan pada 1701.

227
00:09:57,037 --> 00:09:58,870
Oleh itu, kita akan bermula pada
akar, seperti yang kita selalu lakukan.

228
00:09:58,870 --> 00:09:59,890
Dan kami menetapkan penunjuk penyusuran.

229
00:09:59,890 --> 00:10:01,624
Kita akan menggunakannya untuk bergerak melalui.

230
00:10:01,624 --> 00:10:03,790
Perkara pertama yang kita mahu
lakukan adalah pergi ke jalan yang 1.

231
00:10:03,790 --> 00:10:05,830
Itulah angka pertama utama kami.

232
00:10:05,830 --> 00:10:08,420
Nasib baik, walaupun, kita tidak
perlu melakukan apa-apa kerja masa ini.

233
00:10:08,420 --> 00:10:09,919
1 jalan telah dibersihkan.

234
00:10:09,919 --> 00:10:13,520
Saya dibersihkan ia sebelum ini apabila saya
telah memasukkan Harvard pada 1636.

235
00:10:13,520 --> 00:10:18,090
Jadi saya selamat boleh bergerak
turun 1 dan hanya pergi ke sana.

236
00:10:18,090 --> 00:10:20,150
Jika boleh bergerak ke bawah 1.

237
00:10:20,150 --> 00:10:22,930
>> Sekarang, walaupun, saya mahu pergi ke 7.

238
00:10:22,930 --> 00:10:24,280
Saya membuka jalan pada 6.

239
00:10:24,280 --> 00:10:27,050
Saya tahu saya boleh selamat
meneruskan ke jalan yang 6.

240
00:10:27,050 --> 00:10:29,220
Tetapi saya perlu meneruskan di jalan yang 7.

241
00:10:29,220 --> 00:10:30,580
Jadi, apa yang perlu saya lakukan?

242
00:10:30,580 --> 00:10:35,070
Well, seperti sebelum ini, saya hanya perlu
untuk membersihkan pintu, keluar dari jalan,

243
00:10:35,070 --> 00:10:38,740
dan membina nod baru dari jalan yang 7.

244
00:10:38,740 --> 00:10:40,250
Hanya seperti ini.

245
00:10:40,250 --> 00:10:42,930
>> Jadi sekarang saya telah berpindah 1 dan kemudian 7.

246
00:10:42,930 --> 00:10:45,550
Dan kini melihat, Saya jenis
dari pada subbranch baru ini.

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

248
00:10:46,050 --> 00:10:49,260
Segala-galanya daripada 16
, saya tidak mengambil berat tentang.

249
00:10:49,260 --> 00:10:50,720
Saya tidak melakukan 16 apa-apa.

250
00:10:50,720 --> 00:10:51,750
Saya melakukan 17 barangan.

251
00:10:51,750 --> 00:10:58,380
>> Jadi sekarang dari 17 pada, saya perlu
semacam pergi mengikut laluan baru di sini.

252
00:10:58,380 --> 00:11:00,462
Digit berikut utama saya ialah 0.

253
00:11:00,462 --> 00:11:01,670
Saya dengan jelas tidak boleh mendapatkan mana-mana sahaja.

254
00:11:01,670 --> 00:11:02,628
Saya hanya dibina nod ini.

255
00:11:02,628 --> 00:11:04,550
Jadi saya tahu tidak ada
laluan ke hadapan dari sini.

256
00:11:04,550 --> 00:11:06,370
Jadi saya perlu membuat satu diri saya sendiri.

257
00:11:06,370 --> 00:11:09,360
>> Jadi saya malloc nod baru
dan mempunyai 0 mata di sana.

258
00:11:09,360 --> 00:11:12,770
Dan kemudian sekali lagi, saya malloc yang
nod baru dan mempunyai satu mata di sana.

259
00:11:12,770 --> 00:11:15,870
Sekali lagi, saya telah habis utama saya, 1701.

260
00:11:15,870 --> 00:11:18,472
Jadi saya melihat ke bawah dan saya menyembur cat Yale.

261
00:11:18,472 --> 00:11:19,680
Itulah nama nod ini.

262
00:11:19,680 --> 00:11:24,660
>> Dan sekarang jika saya merasa perlu untuk melihat jika Yale
adalah di indone ini, saya bermula dari akar,

263
00:11:24,660 --> 00:11:27,060
Saya turun 1701, dan memandang rendah.

264
00:11:27,060 --> 00:11:30,030
Dan jika saya melihat semburan Yale
dicat ke tanah, kemudian

265
00:11:30,030 --> 00:11:32,200
Saya tahu Yale wujud di indone ini.

266
00:11:32,200 --> 00:11:32,950
Mari kita buat satu lagi.

267
00:11:32,950 --> 00:11:36,430
Mari kita memasukkan Dartmouth ke dalam ini
indone, yang ditubuhkan pada 1769.

268
00:11:36,430 --> 00:11:37,750
>> Bermula dari akar lagi.

269
00:11:37,750 --> 00:11:39,445
Digit pertama saya kunci saya ialah 1.

270
00:11:39,445 --> 00:11:40,820
Saya boleh bergerak ke bawah jalan itu.

271
00:11:40,820 --> 00:11:42,400
Yang telah wujud.

272
00:11:42,400 --> 00:11:44,040
Digit seterusnya utama saya ialah 7.

273
00:11:44,040 --> 00:11:45,890
Saya boleh bergerak ke bawah jalan itu.

274
00:11:45,890 --> 00:11:47,540
Ia wujud juga.

275
00:11:47,540 --> 00:11:49,000
>> Berikut saya ialah 6.

276
00:11:49,000 --> 00:11:52,860
Dari sini, dari mana saya kini sedang
kuning di sana pada nod pertengahan,

277
00:11:52,860 --> 00:11:56,060
6 sedang dikunci off.

278
00:11:56,060 --> 00:11:58,830
Jika saya mahu pergi ke jalan itu,
Saya perlu membina sendiri.

279
00:11:58,830 --> 00:12:02,250
Jadi saya akan malloc nod baru
dan mempunyai 6 titik di sana.

280
00:12:02,250 --> 00:12:04,250
Dan kemudian, sekali lagi, saya
menjulang-julang laluan baru di sini.

281
00:12:04,250 --> 00:12:10,750
>> Jadi saya malloc nod baru supaya dari
bahawa bilangan jalan node-- 9-- dan kemudian sekarang

282
00:12:10,750 --> 00:12:13,584
jika saya melakukan perjalanan 1769, dan saya melihat ke bawah.

283
00:12:13,584 --> 00:12:15,500
Tiada apa-apa pada masa ini
semburan dicat di sana.

284
00:12:15,500 --> 00:12:16,930
Saya boleh menulis Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Dan saya telah dimasukkan
Dartmouth ke indone itu.

286
00:12:20,710 --> 00:12:23,450
>> Jadi itulah memasukkan
sesuatu ke dalam indone itu.

287
00:12:23,450 --> 00:12:25,384
Sekarang kita mahu untuk mencari sesuatu.

288
00:12:25,384 --> 00:12:27,050
Bagaimana kita mencari perkara-perkara di indone itu?

289
00:12:27,050 --> 00:12:29,170
Nah, ia cukup banyak idea yang sama.

290
00:12:29,170 --> 00:12:33,620
Sekarang kita hanya menggunakan digit kunci
untuk melihat jika kita boleh menavigasi dari akar

291
00:12:33,620 --> 00:12:37,170
di mana kita mahu pergi di indone itu.

292
00:12:37,170 --> 00:12:41,620
>> Jika kita menemui jalan buntu pada bila-bila, maka
kita tahu bahawa elemen yang tidak boleh wujud

293
00:12:41,620 --> 00:12:44,500
atau lain jalan yang akan
telah pun dibersihkan.

294
00:12:44,500 --> 00:12:45,930
Jika kita membuat semuanya jalan ke
akhirnya, semua perlu kita lakukan

295
00:12:45,930 --> 00:12:48,471
adalah melihat ke bawah dan melihat jika itu
unsur yang kami cari.

296
00:12:48,471 --> 00:12:49,335
Jika ia, kejayaan.

297
00:12:49,335 --> 00:12:52,610
Jika tidak, gagal.

298
00:12:52,610 --> 00:12:54,940
>> Jadi mari kita mencari
Harvard di indone ini.

299
00:12:54,940 --> 00:12:56,020
Kami bermula dari akar.

300
00:12:56,020 --> 00:12:58,228
Dan, sekali lagi, kita akan
mewujudkan penunjuk penyusuran

301
00:12:58,228 --> 00:12:59,390
untuk melakukan tindakan kami untuk kita.

302
00:12:59,390 --> 00:13:02,080
Dari akar kita tahu bahawa
Tempat pertama kita perlu pergi adalah 1,

303
00:13:02,080 --> 00:13:03,390
kita boleh berbuat demikian?

304
00:13:03,390 --> 00:13:03,982
Ya kami boleh.

305
00:13:03,982 --> 00:13:04,690
Jika selamat wujud.

306
00:13:04,690 --> 00:13:06,660
Kita boleh pergi ke sana.

307
00:13:06,660 --> 00:13:08,440
>> Sekarang, tempat yang akan datang kita perlu pergi adalah 6.

308
00:13:08,440 --> 00:13:10,557
Adakah jalan yang 6 wujud dari sini?

309
00:13:10,557 --> 00:13:11,140
Ya, ia tidak.

310
00:13:11,140 --> 00:13:12,690
Kita boleh pergi ke jalan yang 6.

311
00:13:12,690 --> 00:13:13,905
Dan kita berakhir di sini.

312
00:13:13,905 --> 00:13:16,130
>> Bolehkah kita pergi ke jalan yang 3 dari sini?

313
00:13:16,130 --> 00:13:18,450
Nah, kerana ia ternyata,
ya, yang wujud juga.

314
00:13:18,450 --> 00:13:20,790
Dan kita boleh mendapatkan di jalan yang 6 dari sini?

315
00:13:20,790 --> 00:13:21,982
Ya kami boleh.

316
00:13:21,982 --> 00:13:24,002
>> Kami tidak cukup menjawab
soalan lagi.

317
00:13:24,002 --> 00:13:25,710
Masih ada satu lagi
langkah, yang kini

318
00:13:25,710 --> 00:13:28,520
kita perlu melihat ke bawah dan
melihat jika itu actually--

319
00:13:28,520 --> 00:13:32,660
jika kita mencari Harvard, adalah bahawa
apa yang kita dapati selepas kita menghabiskan kunci?

320
00:13:32,660 --> 00:13:35,430
Dalam contoh yang kami gunakan di sini,
tahun-tahun sentiasa empat digit.

321
00:13:35,430 --> 00:13:40,280
Tetapi anda mungkin menggunakan contoh di mana
anda menyimpan sebuah kamus kata-kata.

322
00:13:40,280 --> 00:13:44,060
>> Dan sebagainya daripada harus 10 petunjuk
lokasi saya, anda mungkin mempunyai 26.

323
00:13:44,060 --> 00:13:46,040
Satu untuk setiap huruf abjad.

324
00:13:46,040 --> 00:13:50,350
Dan terdapat beberapa perkataan seperti kelawar,
yang merupakan subset kelompok, sebagai contoh.

325
00:13:50,350 --> 00:13:53,511
Dan sebagainya walaupun anda sampai ke
akhir utama dan anda melihat ke bawah,

326
00:13:53,511 --> 00:13:55,260
anda mungkin tidak melihat apa yang
anda cari.

327
00:13:55,260 --> 00:13:58,500
>> Jadi, anda sentiasa perlu merentasi
keseluruhan jalan dan kemudian

328
00:13:58,500 --> 00:14:01,540
jika anda berjaya dapat
untuk merentasi keseluruhan jalan,

329
00:14:01,540 --> 00:14:03,440
melihat ke bawah dan lakukan salah satu pengesahan akhir.

330
00:14:03,440 --> 00:14:05,120
Adakah itu apa yang saya cari?

331
00:14:05,120 --> 00:14:07,740
Well, saya melihat ke bawah selepas memulakan
di bahagian atas dan akan 1636.

332
00:14:07,740 --> 00:14:08,240
Saya melihat ke bawah.

333
00:14:08,240 --> 00:14:09,400
Saya melihat Harvard.

334
00:14:09,400 --> 00:14:11,689
Jadi, ya, saya berjaya.

335
00:14:11,689 --> 00:14:13,980
Bagaimana jika apa yang saya cari
tidak di indone, walaupun.

336
00:14:13,980 --> 00:14:17,200
Bagaimana jika saya mencari Princeton,
yang ditubuhkan pada 1746.

337
00:14:17,200 --> 00:14:20,875
Dan sebagainya 1746 menjadi kunci saya
untuk menavigasi melalui indone itu.

338
00:14:20,875 --> 00:14:22,040
Well, saya bermula dari akar.

339
00:14:22,040 --> 00:14:24,760
Dan tempat pertama yang saya mahu
untuk pergi ke jalan yang 1.

340
00:14:24,760 --> 00:14:25,590
Bolehkah saya melakukannya?

341
00:14:25,590 --> 00:14:26,490
Ya saya boleh.

342
00:14:26,490 --> 00:14:28,730
>> Bolehkah saya pergi ke jalan yang 7 dari sana?

343
00:14:28,730 --> 00:14:29,230
Ya, saya boleh.

344
00:14:29,230 --> 00:14:30,750
Yang wujud juga.

345
00:14:30,750 --> 00:14:32,460
Tetapi saya boleh turun 4 jalan dari sini?

346
00:14:32,460 --> 00:14:35,550
Itu seperti bertanya soalan, boleh
Saya teruskan turun yang sedikit persegi

347
00:14:35,550 --> 00:14:37,114
bahawa saya telah ditonjolkan dalam kuning?

348
00:14:37,114 --> 00:14:38,030
Tiada apa-apa di sana.

349
00:14:38,030 --> 00:14:38,610
Betul.

350
00:14:38,610 --> 00:14:41,310
>> Tidak ada cara ke hadapan ke jalan yang 4.

351
00:14:41,310 --> 00:14:46,480
Jika Princeton berada di indone ini, bahawa 4
akan telah dibersihkan untuk kita sudah.

352
00:14:46,480 --> 00:14:49,130
Dan sebagainya pada ketika ini
kita telah mencapai jalan buntu.

353
00:14:49,130 --> 00:14:50,250
Kita tidak boleh pergi mana-mana lagi.

354
00:14:50,250 --> 00:14:53,440
Dan dengan itu kita boleh berkata, secara muktamad, tidak.

355
00:14:53,440 --> 00:14:56,760
Princeton tidak wujud dalam indone ini.

356
00:14:56,760 --> 00:14:58,860
>> Jadi apakah ini semua bermakna?

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

358
00:14:59,360 --> 00:15:01,000
Ada banyak berlaku di sini.

359
00:15:01,000 --> 00:15:02,500
Ada petunjuk di seluruh tempat.

360
00:15:02,500 --> 00:15:04,249
Dan, seperti yang anda lihat
hanya dari rajah,

361
00:15:04,249 --> 00:15:07,010
ada banyak nod yang
adalah sejenis terbang di sekitar.

362
00:15:07,010 --> 00:15:13,480
Tetapi perhatikan setiap kali kita mahu
memeriksa sama ada sesuatu yang tidak di indone itu,

363
00:15:13,480 --> 00:15:15,000
kita hanya perlu membuat 4 bergerak.

364
00:15:15,000 --> 00:15:17,208
>> Setiap kali kita mahu
memasukkan sesuatu di indone itu,

365
00:15:17,208 --> 00:15:20,440
kita perlu membuat 4 bergerak, mungkin
mallocing beberapa barangan di sepanjang jalan.

366
00:15:20,440 --> 00:15:23,482
Tetapi seperti yang kita lihat apabila kita dimasukkan
Dartmouth ke indone itu,

367
00:15:23,482 --> 00:15:25,940
kadang-kadang beberapa jalan
mungkin sudah dibersihkan untuk kita.

368
00:15:25,940 --> 00:15:30,520
Dan supaya indone kita mendapat lebih besar dan
lebih besar, kita perlu melakukan kerja yang kurang setiap kali

369
00:15:30,520 --> 00:15:32,270
untuk memasukkan perkara-perkara baru
kerana kami telah pun

370
00:15:32,270 --> 00:15:35,746
membina banyak perantaraan
cawangan di sepanjang jalan.

371
00:15:35,746 --> 00:15:38,370
Jika kita hanya pernah perlu melihat
4 perkara, 4 hanya pemalar.

372
00:15:38,370 --> 00:15:41,750
Kami benar-benar adalah sejenis menghampiri
masa kemasukan berterusan

373
00:15:41,750 --> 00:15:44,501
dan masa pencarian yang berterusan.

374
00:15:44,501 --> 00:15:47,500
Tradeoff, sudah tentu, adalah bahawa
indone ini, seperti yang anda mungkin boleh memberitahu,

375
00:15:47,500 --> 00:15:49,030
adalah besar.

376
00:15:49,030 --> 00:15:51,040
Setiap nod ini
mengambil banyak ruang.

377
00:15:51,040 --> 00:15:52,090
>> Tetapi itu pengimbangan.

378
00:15:52,090 --> 00:15:55,260
Jika kita mahu benar-benar cepat
kemasukan, penghapusan benar-benar cepat,

379
00:15:55,260 --> 00:15:59,630
dan lookup benar-benar cepat, kita perlu
mempunyai banyak data terbang di sekitar.

380
00:15:59,630 --> 00:16:03,590
Kita perlu mengetepikan banyak ruang
dan memori untuk struktur data

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

382
00:16:04,290 --> 00:16:05,415
>> Dan supaya pengimbangan.

383
00:16:05,415 --> 00:16:07,310
Tetapi ia kelihatan seperti kita
mungkin telah menjumpainya.

384
00:16:07,310 --> 00:16:09,560
Kita mungkin telah mendapati bahawa
kaedah berpotensi suci struktur data

385
00:16:09,560 --> 00:16:12,264
dengan kemasukan cepat,
penghapusan, dan carian.

386
00:16:12,264 --> 00:16:14,430
Dan mungkin ini akan menjadi satu
struktur data yang sesuai

387
00:16:14,430 --> 00:16:18,890
untuk digunakan untuk apa-apa maklumat
kami cuba untuk menyimpan.

388
00:16:18,890 --> 00:16:21,860
Saya Doug Lloyd, ini adalah cs50.

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