1
00:00:00,000 --> 00:00:02,994
>> [MUSIC PLAYING]

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

3
00:00:05,426 --> 00:00:08,550
Doug LLOYD: Jadi kita sudah beringsut lebih dekat
dan lebih dekat yang grail suci data

4
00:00:08,550 --> 00:00:13,050
struktur, salah satu yang kita dapat menyisipkan
dalam, menghapus dari, dan mencari

5
00:00:13,050 --> 00:00:15,440
dalam waktu yang konstan.

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

7
00:00:16,270 --> 00:00:17,280
Itu semacam tujuan.

8
00:00:17,280 --> 00:00:19,720
Kami ingin dapat melakukan
hal yang sangat, sangat cepat.

9
00:00:19,720 --> 00:00:22,580
>> Memiliki kami menemukan itu di sini ketika
kita berbicara tentang mencoba?

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

11
00:00:23,670 --> 00:00:25,628
Jadi kita telah melihat beberapa
struktur data yang berbeda

12
00:00:25,628 --> 00:00:28,680
yang menangani pemetaan
disebut pasangan kunci-nilai,

13
00:00:28,680 --> 00:00:32,080
pemetaan beberapa bagian dari data
untuk beberapa bagian lain dari data yang

14
00:00:32,080 --> 00:00:36,020
jadi kami tahu di mana untuk menemukan
informasi dalam struktur.

15
00:00:36,020 --> 00:00:40,060
>> Jadi untuk array, misalnya,
kunci adalah indeks elemen atau array

16
00:00:40,060 --> 00:00:42,600
Lokasi 0 atau array 1 dan seterusnya.

17
00:00:42,600 --> 00:00:46,140
Dan nilai data
yang ada 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 array 1 versus hanya
0 dan 1, yang akan menjadi kunci.

20
00:00:54,290 --> 00:00:56,360
>> Dengan tabel hash itu
semacam gagasan yang sama.

21
00:00:56,360 --> 00:01:00,690
Dengan tabel hash, kita memiliki hash ini
fungsi yang menghasilkan kode hash.

22
00:01:00,690 --> 00:01:03,670
Jadi kuncinya adalah kode hash dari data.

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

24
00:01:06,530 --> 00:01:10,590
dalam video pada tabel hash,
adalah bahwa linked list data

25
00:01:10,590 --> 00:01:12,550
yang hash untuk kode hash itu.

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

27
00:01:14,050 --> 00:01:16,050
Bagaimana pendekatan lain
metode ini, meskipun?

28
00:01:16,050 --> 00:01:21,000
Bagaimana metode mana
kunci dijamin untuk menjadi unik,

29
00:01:21,000 --> 00:01:25,410
tidak seperti tabel hash, di mana kita bisa
berakhir dengan dua buah data

30
00:01:25,410 --> 00:01:27,200
memiliki kode hash yang sama.

31
00:01:27,200 --> 00:01:30,020
Dan kemudian kita harus berurusan dengan
bahwa dengan baik probing atau lebih

32
00:01:30,020 --> 00:01:33,340
sebaiknya chaining untuk memperbaiki masalah itu.

33
00:01:33,340 --> 00:01:37,520
>> Jadi sekarang kita bisa menjamin
bahwa kunci kami akan menjadi unik.

34
00:01:37,520 --> 00:01:39,690
Dan bagaimana jika nilai kami
hanya sesuatu yang mudah

35
00:01:39,690 --> 00:01:44,080
sebagai benar dan salah yang memberitahu kita apakah
atau tidak sepotong informasi

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

37
00:01:45,610 --> 00:01:48,180
Sebuah Boolean bisa sesederhana sedikit.

38
00:01:48,180 --> 00:01:52,660
Realistis itu mungkin
byte lebih mungkin dibandingkan sedikit.

39
00:01:52,660 --> 00:01:55,410
Tapi itu jauh lebih kecil daripada
menyimpan mungkin string 50-karakter,

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

41
00:01:57,360 --> 00:02:02,210
>> Jadi mencoba, mirip dengan hash tabel,
yang menggabungkan array dan linked list,

42
00:02:02,210 --> 00:02:05,790
mencoba menggabungkan array,
struktur, dan pointer

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

44
00:02:08,509 --> 00:02:11,550
cukup berbeda dari
apa yang telah kita lihat sejauh ini.

45
00:02:11,550 --> 00:02:16,750
Sekarang kita menggunakan data sebagai peta jalan
untuk menavigasi struktur data.

46
00:02:16,750 --> 00:02:18,710
Dan jika kita dapat mengikuti
roadmap, jika kita bisa

47
00:02:18,710 --> 00:02:22,390
ikuti data dari
awal sampai akhir, kami akan

48
00:02:22,390 --> 00:02:24,945
mengetahui apakah data yang
ada di trie.

49
00:02:24,945 --> 00:02:28,310
>> Dan jika kita tidak bisa mengikuti peta
dari yang berarti untuk mengakhiri sama sekali,

50
00:02:28,310 --> 00:02:30,600
data tidak bisa eksis.

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

52
00:02:32,890 --> 00:02:36,020
Dan tidak seperti tabel hash, kita tidak akan pernah
harus berurusan dengan tabrakan di sini.

53
00:02:36,020 --> 00:02:39,090
Dan tidak ada dua buah data
memiliki persis roadmap yang sama

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

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

56
00:02:44,580 --> 00:02:47,430
Itu dua potong identik
data, kanan, kita melihat melalui.

57
00:02:47,430 --> 00:02:49,880
Tapi sebaliknya, setiap
dua potong data

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

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

60
00:02:56,210 --> 00:02:58,810
>> Kami akan melakukan ini dengan mencoba
membuat struktur data baru,

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

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

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

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

65
00:03:08,690 --> 00:03:12,140
>> Dan kunci akan menjadi tahun
ketika universitas yang didirikan.

66
00:03:12,140 --> 00:03:15,380
Semua tahun untuk universitas
akan menjadi empat angka.

67
00:03:15,380 --> 00:03:19,840
Dan jadi kita akan menggunakan empat angka
menavigasi melalui struktur data.

68
00:03:19,840 --> 00:03:22,270
Dan kita akan melihat, lagi, bagaimana
kami melakukan itu hanya satu detik.

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

70
00:03:25,110 --> 00:03:30,250
dari universitas yang sesuai
untuk kunci itu, empat digit.

71
00:03:30,250 --> 00:03:34,390
Ide dasar di balik trie
adalah kita memiliki rute sentral.

72
00:03:34,390 --> 00:03:35,640
Jadi pikirkan tentang hal itu seperti pohon.

73
00:03:35,640 --> 00:03:39,211
Dan ini mirip dalam ejaan
dan dalam konsep pohon.

74
00:03:39,211 --> 00:03:41,460
Umumnya ketika kita berpikir tentang
pohon di dunia nyata,

75
00:03:41,460 --> 00:03:44,090
mereka memiliki akar yang dalam
tanah dan mereka tumbuh ke atas

76
00:03:44,090 --> 00:03:46,830
dan mereka memiliki cabang
dan mereka memiliki daun.

77
00:03:46,830 --> 00:03:49,450
Dan pada dasarnya ide
trie adalah persis sama,

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

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

80
00:03:53,130 --> 00:03:55,750
>> Jadi itu semacam seperti mengambil pohon
dan hanya membalik terbalik.

81
00:03:55,750 --> 00:03:56,880
Namun masih ada cabang.

82
00:03:56,880 --> 00:03:59,463
Dan mereka akan menjadi jalur kami,
mereka akan koneksi kami

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

84
00:04:02,220 --> 00:04:04,200
Dalam hal ini, orang-orang
jalan, cabang-cabang

85
00:04:04,200 --> 00:04:08,490
diberi label dengan angka yang kami kirim
cara untuk pergi dari tempat kami berada.

86
00:04:08,490 --> 00:04:11,800
>> Jika kita melihat 0, kita turun cabang ini,
jika kita melihat 1, kita turun cabang 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 artinya ini?

89
00:04:14,060 --> 00:04:16,519
Nah, itu berarti bahwa
di setiap titik persimpangan

90
00:04:16,519 --> 00:04:19,260
dan setiap node dalam
tengah dan setiap cabang,

91
00:04:19,260 --> 00:04:23,020
ada 10 kemungkinan
tempat-tempat yang kita bisa pergi.

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

93
00:04:27,690 --> 00:04:30,610
>> Dan ini adalah di mana mencoba bisa mendapatkan
sedikit menakutkan bagi seseorang

94
00:04:30,610 --> 00:04:34,460
siapa yang tidak memiliki banyak
Pengalaman dalam ilmu komputer sebelumnya.

95
00:04:34,460 --> 00:04:35,960
Tapi mencoba benar-benar cukup mengagumkan.

96
00:04:35,960 --> 00:04:37,793
Dan jika Anda memiliki
kesempatan untuk bekerja dengan mereka

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

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

99
00:04:44,234 --> 00:04:46,900
Jika kita ingin memasukkan unsur
dalam trie, semua yang perlu kita lakukan

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

101
00:04:51,360 --> 00:04:55,390
Inilah yang setiap langkah bersama
jalan mungkin terlihat seperti.

102
00:04:55,390 --> 00:04:59,660
Kita akan mendefinisikan data baru
struktur untuk node baru yang disebut trie.

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

104
00:05:02,560 --> 00:05:05,460
Kita akan menyimpan
nama universitas.

105
00:05:05,460 --> 00:05:09,410
Dan kita akan menyimpan
array pointer

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

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

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

109
00:05:18,567 --> 00:05:20,150
Jika kita melihat 0, kita turun cabang ini.

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

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

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

113
00:05:28,220 --> 00:05:35,740
Jadi setiap node memiliki mengandung 10 pointer
ke node lain, untuk 10 node lain.

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

115
00:05:39,810 --> 00:05:41,060
Jadi mari kita membangun trie.

116
00:05:41,060 --> 00:05:44,860
Mari kita masukkan beberapa
item dalam trie kami.

117
00:05:44,860 --> 00:05:46,740
Jadi di bagian paling atas,
ini adalah simpul akar kami.

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

119
00:05:49,740 --> 00:05:53,450
Dan Anda akan secara global mempertahankan
pointer ke node ini selalu.

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

121
00:05:55,360 --> 00:05:57,580
akan malloc sendiri trie simpul.

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

123
00:05:59,850 --> 00:06:02,300
Setiap kali Anda ingin
mulai menavigasi melalui,

124
00:06:02,300 --> 00:06:05,802
Anda mengatur pointer lain
sama dengan akar, seperti trav,

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

126
00:06:07,760 --> 00:06:11,090
di sini di tumpukan dan antrian
dan daftar link and sebagainya.

127
00:06:11,090 --> 00:06:13,320
>> Anda mengatur pointer lain
disebut trav untuk traversal.

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

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

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

131
00:06:19,880 --> 00:06:22,920
Nah, seperti data kami
Struktur deklarasi ditunjukkan,

132
00:06:22,920 --> 00:06:26,906
kita memiliki string, yang
dalam hal ini adalah kosong.

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

134
00:06:27,780 --> 00:06:29,550
>> Dan sebuah array dari 10 pointer.

135
00:06:29,550 --> 00:06:31,790
Dan sekarang, kita hanya
memiliki 1 node dalam trie ini.

136
00:06:31,790 --> 00:06:33,110
Tidak ada yang lain di dalamnya.

137
00:06:33,110 --> 00:06:36,020
Jadi semua 10 dari mereka
pointer titik untuk null.

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

139
00:06:38,090 --> 00:06:39,500
>> Mari kita masukkan string Harvard.

140
00:06:39,500 --> 00:06:41,999
Mari kita masukkan Universitas
Harvard ke trie ini, yang

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

142
00:06:43,940 --> 00:06:48,220
Kami ingin menggunakan kunci,
1636, untuk memberitahu kami di mana kami

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

144
00:06:50,140 --> 00:06:51,470
Sekarang, bagaimana kita bisa melakukan itu?

145
00:06:51,470 --> 00:06:52,886
>> Ini mungkin terlihat seperti ini.

146
00:06:52,886 --> 00:06:54,160
Kita mulai pada akar.

147
00:06:54,160 --> 00:06:56,920
Dan kami memiliki 10 tempat ini kita bisa pergi.

148
00:06:56,920 --> 00:06:59,900
Akar adalah sama seperti
simpul lain dari trie.

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

150
00:07:02,850 --> 00:07:07,215
>> Di mana kita mungkin ingin
untuk pergi jika kuncinya 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
Benar.

153
00:07:08,450 --> 00:07:10,825
Kita dapat membangun kunci dari
kanan ke kiri dan mulai dengan 6.

154
00:07:10,825 --> 00:07:14,000
Atau kita bisa membangun kunci dari
kiri ke kanan dan mulai dengan 1.

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

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

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

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

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

160
00:07:25,720 --> 00:07:28,700
Saya ingin pergi ke 1 jalur.

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

162
00:07:29,700 --> 00:07:31,810
>> Sekarang, 1 jalan saat ini nol.

163
00:07:31,810 --> 00:07:35,920
Jadi jika saya ingin melanjutkan ke jalan yang
untuk memasukkan unsur ini ke trie,

164
00:07:35,920 --> 00:07:42,040
Saya harus malloc node baru, memiliki 1
titik di sana, dan kemudian aku baik untuk pergi.

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

166
00:07:46,460 --> 00:07:50,270
pada akar pohon atau
trie dan ada 10 cabang.

167
00:07:50,270 --> 00:07:52,260
Tapi setiap cabang memiliki
gerbang di depannya.

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

169
00:07:53,060 --> 00:07:54,850
Karena tidak ada yang lain ada.

170
00:07:54,850 --> 00:07:56,522
Tidak ada perjalanan yang aman.

171
00:07:56,522 --> 00:07:58,980
Itu berarti bahwa tidak ada
bawah salah satu dari mereka cabang.

172
00:07:58,980 --> 00:08:02,532
Jika saya ingin mulai membangun
sesuatu, saya ingin menghapus gerbang.

173
00:08:02,532 --> 00:08:04,490
Saya ingin menghapus gerbang
di depan nomor 1.

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

175
00:08:05,698 --> 00:08:08,060
Dan saya ingin membangun
tempat lain bagi saya untuk 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 ke null.

178
00:08:11,430 --> 00:08:13,830
Aku sudah mengatakan itu aman untuk turun di sini sekarang.

179
00:08:13,830 --> 00:08:15,789
Saya membangun node lain.

180
00:08:15,789 --> 00:08:18,330
Dan ketika saya sampai ke simpul itu, saya
memiliki keputusan lain untuk membuat.

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

182
00:08:20,890 --> 00:08:22,700
>> Yah, aku sudah turun 1.

183
00:08:22,700 --> 00:08:24,470
Jadi sekarang saya mungkin ingin pergi ke 6.

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

185
00:08:24,970 --> 00:08:27,100
Sekali lagi, saya memiliki 10 lokasi saya dapat memilih.

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

187
00:08:30,060 --> 00:08:32,280
Jadi saya menghapus gerbang
di depan nomor 6.

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

189
00:08:33,250 --> 00:08:34,580
Dan saya membangun node lain.

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

191
00:08:37,630 --> 00:08:40,289
>> Sekali lagi, saya memiliki 10 pilihan
untuk mana aku bisa pergi.

192
00:08:40,289 --> 00:08:42,799
Aku pindah 1-6.

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

194
00:08:44,215 --> 00:08:45,381
3, yang mana aku bisa pergi ke sana.

195
00:08:45,381 --> 00:08:48,980
Jadi saya harus membersihkan jalan
dan membangun sendiri ruang baru.

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

197
00:08:50,870 --> 00:08:52,450
Saya ingin pergi ke 6.

198
00:08:52,450 --> 00:08:54,770
>> Dan, sekali lagi, saya harus
menghapus cara untuk melakukannya.

199
00:08:54,770 --> 00:08:59,179
Jadi sekarang aku telah menggunakan kunci untuk menyisipkan membuat
node dan mulai membangun trie ini.

200
00:08:59,179 --> 00:09:00,220
Saya sudah mulai pada akar.

201
00:09:00,220 --> 00:09:03,666
Aku sudah turun 1.636.

202
00:09:03,666 --> 00:09:05,540
Dan sekarang aku di bagian bawah
ada pada simpul tersebut.

203
00:09:05,540 --> 00:09:06,610
Dan Anda mungkin bisa
melihatnya di layar Anda.

204
00:09:06,610 --> 00:09:07,735
>> Ini ditandai dengan warna kuning.

205
00:09:07,735 --> 00:09:10,020
Di situlah saya saat saya.

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

207
00:09:11,300 --> 00:09:13,030
Saya telah kehabisan setiap posisi di kunci.

208
00:09:13,030 --> 00:09:15,040
Jadi saya tidak bisa pergi lebih jauh.

209
00:09:15,040 --> 00:09:17,720
Jadi pada titik ini, semua saya
benar-benar perlu lakukan adalah mengatakan, OK.

210
00:09:17,720 --> 00:09:18,990
Ini semacam seperti mencari
turun di tanah,

211
00:09:18,990 --> 00:09:21,115
jika Anda membayangkan
diri semacam ini jalan

212
00:09:21,115 --> 00:09:22,350
dengan koneksi yang berbeda.

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

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

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

216
00:09:28,300 --> 00:09:31,870
Jika kita mulai dari akar dan kami 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
Nah jika kita melihat ke bawah
dan kita melihat Harvard, kemudian

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

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

221
00:09:41,400 --> 00:09:43,177
Jadi itu mudah-mudahan langsung.

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

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

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

225
00:09:52,210 --> 00:09:54,630
Mari kita masukkan ke dalam Yale trie ini.

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

227
00:09:57,037 --> 00:09:58,870
Jadi kita akan mulai di
akar, seperti yang kita selalu lakukan.

228
00:09:58,870 --> 00:09:59,890
Dan kami menetapkan pointer traversal.

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

230
00:10:01,624 --> 00:10:03,790
Hal pertama yang ingin kita
lakukan adalah pergi ke 1 jalur.

231
00:10:03,790 --> 00:10:05,830
Itulah digit pertama kunci kami.

232
00:10:05,830 --> 00:10:08,420
Untungnya, meskipun, kita tidak
harus melakukan pekerjaan apapun saat ini.

233
00:10:08,420 --> 00:10:09,919
1 jalur sudah dibersihkan.

234
00:10:09,919 --> 00:10:13,520
Aku dibersihkan itu sebelumnya ketika saya
itu memasukkan Harvard di 1636.

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

236
00:10:18,090 --> 00:10:20,150
Jika bisa bergerak turun 1.

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

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

239
00:10:24,280 --> 00:10:27,050
Aku tahu aku bisa dengan aman
melanjutkan menyusuri jalan 6.

240
00:10:27,050 --> 00:10:29,220
Tapi aku harus melanjutkan pada 7 jalan.

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

242
00:10:30,580 --> 00:10:35,070
Nah, seperti sebelumnya, saya hanya perlu
untuk membersihkan pintu gerbang, keluar dari jalan,

243
00:10:35,070 --> 00:10:38,740
dan membangun node baru dari 7 jalan.

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

245
00:10:40,250 --> 00:10:42,930
>> Jadi sekarang aku sudah pindah 1 dan kemudian 7.

246
00:10:42,930 --> 00:10:45,550
Dan sekarang perhatikan, aku semacam
dari pada ranting baru ini.

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

248
00:10:46,050 --> 00:10:49,260
Segala sesuatu yang lain dari 16
, aku tidak peduli tentang.

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

250
00:10:50,720 --> 00:10:51,750
Aku melakukan hal-hal 17.

251
00:10:51,750 --> 00:10:58,380
>> Jadi sekarang dari 17, saya harus
semacam merintis jalan baru di sini.

252
00:10:58,380 --> 00:11:00,462
Digit berikutnya kunci adalah 0.

253
00:11:00,462 --> 00:11:01,670
Saya jelas tidak bisa mendapatkan tempat.

254
00:11:01,670 --> 00:11:02,628
Aku hanya membangun node ini.

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

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

257
00:11:06,370 --> 00:11:09,360
>> Jadi saya malloc node baru
dan memiliki 0 poin di sana.

258
00:11:09,360 --> 00:11:12,770
Dan kemudian sekali lagi, saya malloc sebuah
node baru dan memiliki satu titik ada.

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

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

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

262
00:11:19,680 --> 00:11:24,660
>> Dan sekarang jika saya merasa perlu untuk melihat apakah Yale
adalah dalam trie ini, saya mulai akar,

263
00:11:24,660 --> 00:11:27,060
Aku turun 1701, dan melihat ke bawah.

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

265
00:11:30,030 --> 00:11:32,200
Aku tahu Yale ada di trie ini.

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

267
00:11:32,950 --> 00:11:36,430
Mari kita masukkan ke dalam Dartmouth ini
trie, yang didirikan pada tahun 1769.

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

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

270
00:11:39,445 --> 00:11:40,820
Aku bisa bergerak turun jalan itu.

271
00:11:40,820 --> 00:11:42,400
Yang sudah ada.

272
00:11:42,400 --> 00:11:44,040
Digit berikutnya dari kunci adalah 7.

273
00:11:44,040 --> 00:11:45,890
Aku bisa bergerak turun jalan itu.

274
00:11:45,890 --> 00:11:47,540
Ini ada juga.

275
00:11:47,540 --> 00:11:49,000
>> Berikutnya adalah 6.

276
00:11:49,000 --> 00:11:52,860
Dari sini, dari tempat saya saat ini saya
kuning ada di node tengah,

277
00:11:52,860 --> 00:11:56,060
6 saat ini terkunci.

278
00:11:56,060 --> 00:11:58,830
Jika saya ingin pergi ke jalan itu,
Saya harus membangun sendiri.

279
00:11:58,830 --> 00:12:02,250
Jadi saya akan malloc node baru
dan memiliki 6 titik ada.

280
00:12:02,250 --> 00:12:04,250
Dan kemudian, sekali lagi, aku
terik jalan baru di sini.

281
00:12:04,250 --> 00:12:10,750
>> Jadi saya malloc node baru sehingga dari
nomor jalan node-- 9-- dan kemudian sekarang

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

283
00:12:13,584 --> 00:12:15,500
Tidak ada saat ini
semprot dicat ada.

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

285
00:12:16,930 --> 00:12:20,710
Dan aku sudah dimasukkan
Dartmouth ke trie.

286
00:12:20,710 --> 00:12:23,450
>> Jadi itu memasukkan
hal dalam trie.

287
00:12:23,450 --> 00:12:25,384
Sekarang kita ingin mencari hal-hal.

288
00:12:25,384 --> 00:12:27,050
Bagaimana kita mencari hal-hal di trie?

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

290
00:12:29,170 --> 00:12:33,620
Sekarang kita hanya menggunakan angka kunci
untuk melihat apakah kita dapat menavigasi dari akar

291
00:12:33,620 --> 00:12:37,170
di mana kita ingin pergi di trie.

292
00:12:37,170 --> 00:12:41,620
>> Jika kita menemui jalan buntu pada setiap titik, maka
kita tahu bahwa elemen yang tidak bisa ada

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

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

295
00:12:45,930 --> 00:12:48,471
adalah melihat ke bawah dan melihat apakah itu
elemen yang kita cari.

296
00:12:48,471 --> 00:12:49,335
Jika ya, sukses.

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 pada trie ini.

299
00:12:54,940 --> 00:12:56,020
Kita mulai pada akar.

300
00:12:56,020 --> 00:12:58,228
Dan, sekali lagi, kita akan
membuat pointer traversal

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

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

303
00:13:02,080 --> 00:13:03,390
kita bisa melakukan itu?

304
00:13:03,390 --> 00:13:03,982
Ya kita bisa.

305
00:13:03,982 --> 00:13:04,690
Jika aman ada.

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

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

308
00:13:08,440 --> 00:13:10,557
Apakah 6 jalan ada dari sini?

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

310
00:13:11,140 --> 00:13:12,690
Kami bisa turun 6 jalan.

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

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

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

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

315
00:13:20,790 --> 00:13:21,982
Ya kita bisa.

316
00:13:21,982 --> 00:13:24,002
>> Kami belum cukup menjawab
pertanyaan belum.

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

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

319
00:13:28,520 --> 00:13:32,660
jika kita sedang mencari Harvard, adalah bahwa
apa yang kita temukan setelah kami knalpot kunci?

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

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

322
00:13:40,280 --> 00:13:44,060
>> Dan bukan memiliki 10 pointer
untuk lokasi saya, Anda mungkin memiliki 26.

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

324
00:13:46,040 --> 00:13:50,350
Dan ada beberapa kata-kata seperti kelelawar,
yang merupakan bagian dari batch, misalnya.

325
00:13:50,350 --> 00:13:53,511
Dan bahkan jika Anda sampai ke
akhir kunci dan Anda melihat ke bawah,

326
00:13:53,511 --> 00:13:55,260
Anda mungkin tidak melihat apa
Anda sedang mencari.

327
00:13:55,260 --> 00:13:58,500
>> Sehingga Anda selalu harus melintasi
seluruh jalan dan kemudian

328
00:13:58,500 --> 00:14:01,540
jika Anda berhasil dapat
untuk melintasi seluruh jalan,

329
00:14:01,540 --> 00:14:03,440
melihat ke bawah dan melakukan satu konfirmasi akhir.

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

331
00:14:05,120 --> 00:14:07,740
Yah, aku melihat ke bawah setelah memulai
di bagian atas dan pergi 1.636.

332
00:14:07,740 --> 00:14:08,240
Aku 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 berhasil.

335
00:14:11,689 --> 00:14:13,980
Bagaimana jika apa yang saya cari
tidak dalam trie, meskipun.

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

337
00:14:17,200 --> 00:14:20,875
Dan 1746 menjadi kunci saya
untuk menavigasi trie.

338
00:14:20,875 --> 00:14:22,040
Yah, aku mulai akar.

339
00:14:22,040 --> 00:14:24,760
Dan tempat pertama yang saya ingin
untuk turun 1 jalur.

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

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

342
00:14:26,490 --> 00:14:28,730
>> Dapatkah saya turun 7 jalan dari sana?

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

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

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

346
00:14:32,460 --> 00:14:35,550
Itu seperti mengajukan pertanyaan, bisa
Saya melanjutkan ke yang kecil persegi

347
00:14:35,550 --> 00:14:37,114
bahwa saya telah ditandai dengan warna kuning?

348
00:14:37,114 --> 00:14:38,030
Tidak ada yang ada.

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

350
00:14:38,610 --> 00:14:41,310
>> Tidak ada cara maju menuruni 4 jalur.

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

352
00:14:46,480 --> 00:14:49,130
Dan pada titik ini
kami telah mencapai jalan buntu.

353
00:14:49,130 --> 00:14:50,250
Kita tidak bisa pergi lebih jauh.

354
00:14:50,250 --> 00:14:53,440
Dan sehingga kita dapat mengatakan, pasti, tidak ada.

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

356
00:14:56,760 --> 00:14:58,860
>> Jadi apa arti dari semua ini?

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

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

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

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

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

362
00:15:07,010 --> 00:15:13,480
Tapi perhatikan setiap kali kita ingin
memeriksa apakah ada sesuatu yang di trie,

363
00:15:13,480 --> 00:15:15,000
kami hanya harus membuat 4 langkah.

364
00:15:15,000 --> 00:15:17,208
>> Setiap kali kita ingin
memasukkan sesuatu di trie,

365
00:15:17,208 --> 00:15:20,440
kita harus membuat 4 langkah, mungkin
mallocing beberapa hal di sepanjang jalan.

366
00:15:20,440 --> 00:15:23,482
Tapi seperti yang kita lihat ketika kita dimasukkan
Dartmouth ke trie,

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 sehingga trie kami akan lebih besar dan
lebih besar, yang harus kita melakukan sedikit pekerjaan setiap kali

369
00:15:30,520 --> 00:15:32,270
untuk menyisipkan hal-hal baru
karena kita sudah sudah

370
00:15:32,270 --> 00:15:35,746
dibangun banyak menengah
cabang di sepanjang jalan.

371
00:15:35,746 --> 00:15:38,370
Jika kita hanya pernah harus melihat
4 hal, 4 hanya konstan.

372
00:15:38,370 --> 00:15:41,750
Kami benar-benar adalah jenis mendekati
waktu penyisipan konstan

373
00:15:41,750 --> 00:15:44,501
dan waktu pencarian konstan.

374
00:15:44,501 --> 00:15:47,500
Tradeoff, tentu saja, adalah bahwa
trie ini, karena Anda mungkin bisa mengatakan,

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

376
00:15:49,030 --> 00:15:51,040
Masing-masing dari node ini
memakan banyak ruang.

377
00:15:51,040 --> 00:15:52,090
>> Tapi itu tradeoff.

378
00:15:52,090 --> 00:15:55,260
Jika kita ingin benar-benar cepat
penyisipan, penghapusan sangat cepat,

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

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

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

382
00:16:04,290 --> 00:16:05,415
>> Dan jadi itu tradeoff.

383
00:16:05,415 --> 00:16:07,310
Tapi sepertinya kita
mungkin telah menemukan itu.

384
00:16:07,310 --> 00:16:09,560
Kita mungkin telah menemukan bahwa
grail suci struktur data

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

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

387
00:16:14,430 --> 00:16:18,890
menggunakan informasi apapun
kita mencoba untuk menyimpan.

388
00:16:18,890 --> 00:16:21,860
Aku Doug Lloyd, ini CS50.

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