1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Kadang-kadang, ketika membangun sebuah
Program, Anda mungkin ingin memanfaatkan

3
00:00:10,890 --> 00:00:13,190
struktur data yang dikenal sebagai kamus.

4
00:00:13,190 --> 00:00:17,960
Sebuah peta kunci kamus, yang
biasanya string, nilai-nilai, int,

5
00:00:17,960 --> 00:00:21,900
karakter, pointer ke beberapa objek,
apapun yang kita inginkan.

6
00:00:21,900 --> 00:00:26,510
Ini seperti kamus biasa
kata peta bahwa melalui definisi.

7
00:00:26,510 --> 00:00:29,440
>> Kamus menyediakan kami dengan
kemampuan untuk menyimpan informasi

8
00:00:29,440 --> 00:00:32,750
berhubungan dengan sesuatu
dan mencarinya nanti.

9
00:00:32,750 --> 00:00:36,620
Jadi bagaimana kita benar-benar menerapkan
kamus dalam, katakanlah, kode C yang kita bisa

10
00:00:36,620 --> 00:00:38,460
digunakan dalam salah satu program kami?

11
00:00:38,460 --> 00:00:41,790
Well, ada banyak cara yang
kita bisa menerapkan kamus.

12
00:00:41,790 --> 00:00:45,930
>> Untuk satu, kita bisa menggunakan array yang kita
kembali ukuran dinamis atau kita bisa menggunakan

13
00:00:45,930 --> 00:00:49,150
linked list, tabel hash
atau pohon biner.

14
00:00:49,150 --> 00:00:52,250
Tapi apa pun yang kita pilih, kita harus
berhati-hati dari efisiensi dan

15
00:00:52,250 --> 00:00:54,300
kinerja pelaksanaan.

16
00:00:54,300 --> 00:00:57,930
Kita harus memikirkan algoritma yang digunakan
untuk menyisipkan dan mencari barang-barang ke dalam

17
00:00:57,930 --> 00:00:59,120
struktur data kami.

18
00:00:59,120 --> 00:01:03,060
>> Untuk saat ini, mari kita asumsikan bahwa kita
ingin menggunakan string sebagai kunci.

19
00:01:03,060 --> 00:01:07,290
Mari kita bicara tentang satu kemungkinan,
struktur data yang disebut trie.

20
00:01:07,290 --> 00:01:11,210
Jadi, inilah representasi visual
dari trie.

21
00:01:11,210 --> 00:01:14,590
>> Seperti gambar menunjukkan, trie
adalah struktur data pohon dengan

22
00:01:14,590 --> 00:01:16,050
node dihubungkan bersama.

23
00:01:16,050 --> 00:01:19,420
Kita melihat bahwa jelas ada root
simpul dengan beberapa link untuk memperluas

24
00:01:19,420 --> 00:01:20,500
node lain.

25
00:01:20,500 --> 00:01:23,040
Tapi apa setiap node terdiri dari?

26
00:01:23,040 --> 00:01:26,700
Jika kita mengasumsikan bahwa kita menyimpan kunci
dengan hanya karakter abjad, dan

27
00:01:26,700 --> 00:01:30,150
kita tidak peduli tentang kapitalisasi,
berikut adalah definisi dari sebuah node yang

28
00:01:30,150 --> 00:01:31,100
akan cukup.

29
00:01:31,100 --> 00:01:34,130
>> Sebuah benda yang tipenya struct
node memiliki dua bagian

30
00:01:34,130 --> 00:01:35,740
disebut data dan anak-anak.

31
00:01:35,740 --> 00:01:39,200
Kami telah meninggalkan bagian data sebagai komentar
untuk digantikan oleh komponen

32
00:01:39,200 --> 00:01:43,190
deklarasi ketika struct node
tergabung dalam program C.

33
00:01:43,190 --> 00:01:47,040
Data bagian dari sebuah node mungkin
Nilai Boolean untuk menunjukkan apakah atau

34
00:01:47,040 --> 00:01:51,160
tidak node merupakan penyelesaian
dari kunci kamus atau mungkin

35
00:01:51,160 --> 00:01:54,240
string yang mewakili definisi
dari sebuah kata dalam kamus.

36
00:01:54,240 --> 00:01:58,870
>> Kami akan menggunakan wajah tersenyum untuk menunjukkan
ketika data hadir dalam node.

37
00:01:58,870 --> 00:02:02,310
Ada 26 elemen dalam kami
anak array, satu indeks

38
00:02:02,310 --> 00:02:03,690
per karakter abjad.

39
00:02:03,690 --> 00:02:06,570
Kita akan melihat signifikansi
ini segera.

40
00:02:06,570 --> 00:02:10,759
>> Mari kita lihat lebih dekat dari simpul akar
dalam diagram kita, yang tidak memiliki data

41
00:02:10,759 --> 00:02:14,740
terkait dengan itu, seperti yang ditunjukkan oleh
tidak adanya wajah smiley di

42
00:02:14,740 --> 00:02:16,110
bagian data.

43
00:02:16,110 --> 00:02:19,910
Panah membentang dari bagian-bagian
anak-anak array yang merupakan non-node

44
00:02:19,910 --> 00:02:21,640
pointer ke node lain.

45
00:02:21,640 --> 00:02:25,500
Misalnya, panah membentang dari
elemen kedua anak-anak

46
00:02:25,500 --> 00:02:28,400
mewakili huruf B
dalam kunci kamus.

47
00:02:28,400 --> 00:02:31,920
Dan dalam diagram yang lebih besar
kami label dengan B.

48
00:02:31,920 --> 00:02:35,810
>> Perhatikan bahwa dalam diagram yang lebih besar, ketika kita
menggambar pointer ke node lain,

49
00:02:35,810 --> 00:02:39,100
Tidak peduli di mana panah
memenuhi bahwa node lainnya.

50
00:02:39,100 --> 00:02:43,850
Kami sampel kamus trie berisi
dua kata, itu dan zoom.

51
00:02:43,850 --> 00:02:47,040
Mari kita berjalan melalui contoh
mencari data untuk kunci.

52
00:02:47,040 --> 00:02:50,800
>> Misalkan kita ingin mencari dengan
sesuai nilai untuk mandi utama.

53
00:02:50,800 --> 00:02:53,610
Kami akan mulai melihat kami up
pada simpul akar.

54
00:02:53,610 --> 00:02:57,870
Kemudian kita akan mengambil huruf pertama dari kami
kunci, B, dan menemukan yang sesuai

55
00:02:57,870 --> 00:03:00,020
tempat dalam array anak-anak kita.

56
00:03:00,020 --> 00:03:04,490
Perhatikan bahwa ada tepat 26 spot
dalam array, satu untuk setiap huruf dari

57
00:03:04,490 --> 00:03:05,330
alfabet.

58
00:03:05,330 --> 00:03:08,800
Dan kita akan memiliki tempat mewakili
huruf alfabet dalam rangka.

59
00:03:08,800 --> 00:03:13,960
>> Kita akan melihat indeks kedua kemudian,
Indeks satu, untuk B. Secara umum, jika kita

60
00:03:13,960 --> 00:03:17,990
memiliki beberapa karakter abjad C kami
bisa menentukan tempat yang sesuai

61
00:03:17,990 --> 00:03:21,520
pada anak-anak array menggunakan
perhitungan seperti ini.

62
00:03:21,520 --> 00:03:25,140
Kita bisa menggunakan anak-anak yang lebih besar
Array jika kita ingin menawarkan tampilan up

63
00:03:25,140 --> 00:03:28,380
kunci dengan jangkauan yang lebih luas dari karakter,
seperti seluruh yang

64
00:03:28,380 --> 00:03:29,880
Karakter ASCII set.

65
00:03:29,880 --> 00:03:32,630
>> Dalam hal ini, pointer
dalam array anak-anak kita di

66
00:03:32,630 --> 00:03:34,320
Indeks satu tidak null.

67
00:03:34,320 --> 00:03:36,600
Jadi kita akan terus mencari
up mandi utama.

68
00:03:36,600 --> 00:03:40,130
Jika kita pernah mengalami pointer nol
di tempat yang tepat pada anak-anak

69
00:03:40,130 --> 00:03:43,230
Array sementara kami melintasi node,
maka kita harus mengatakan bahwa kita

70
00:03:43,230 --> 00:03:45,630
tidak bisa menemukan apa pun untuk kunci itu.

71
00:03:45,630 --> 00:03:49,370
>> Sekarang, kami akan mengambil surat kedua
kunci kami, A, dan terus mengikuti

72
00:03:49,370 --> 00:03:52,400
pointer dengan cara ini sampai kita
mencapai akhir kunci kami.

73
00:03:52,400 --> 00:03:56,530
Jika kita mencapai akhir kunci tanpa
memukul apapun buntu, pointer null,

74
00:03:56,530 --> 00:03:59,730
seperti yang terjadi di sini, maka kita hanya
harus memeriksa satu hal lagi.

75
00:03:59,730 --> 00:04:02,110
Apakah kunci ini benar-benar
dalam kamus?

76
00:04:02,110 --> 00:04:07,660
>> Jika demikian, kita harus mencari nilai, sumur
icon wajah tersenyum di mana kami diagram

77
00:04:07,660 --> 00:04:08,750
kata berakhir.

78
00:04:08,750 --> 00:04:12,270
Jika ada sesuatu yang lain yang tersimpan dengan
data, maka kita bisa mengembalikannya.

79
00:04:12,270 --> 00:04:16,500
Misalnya, kebun binatang kunci bukan dalam
kamus, meskipun kita bisa memiliki

80
00:04:16,500 --> 00:04:19,810
mencapai akhir kunci ini tanpa pernah
memukul pointer null, sementara kita

81
00:04:19,810 --> 00:04:21,089
iterate melalui trie.

82
00:04:21,089 --> 00:04:25,436
>> Jika kita mencoba untuk mencari mandi kunci,
kedua untuk indeks array simpul lalu,

83
00:04:25,436 --> 00:04:28,750
sesuai dengan huruf H, akan
telah mengadakan pointer null.

84
00:04:28,750 --> 00:04:31,120
Jadi mandi tidak ada dalam kamus.

85
00:04:31,120 --> 00:04:34,800
Dan trie adalah unik karena tombol
tidak pernah secara eksplisit disimpan dalam

86
00:04:34,800 --> 00:04:36,650
struktur data.

87
00:04:36,650 --> 00:04:38,810
Jadi bagaimana kita memasukkan sesuatu
menjadi trie?

88
00:04:38,810 --> 00:04:41,780
>> Mari kita memasukkan kunci
zoo ke trie kami.

89
00:04:41,780 --> 00:04:46,120
Ingat bahwa wajah tersenyum pada node
bisa sesuai kode dengan sederhana

90
00:04:46,120 --> 00:04:50,170
Nilai Boolean untuk menunjukkan kebun binatang yang
adalah dalam kamus atau bisa

91
00:04:50,170 --> 00:04:53,710
sesuai dengan informasi lebih lanjut yang kami
ingin Anda kaitkan dengan kebun binatang kunci,

92
00:04:53,710 --> 00:04:56,860
seperti definisi
kata atau sesuatu yang lain.

93
00:04:56,860 --> 00:05:00,350
Dalam beberapa hal, proses untuk menyisipkan
sesuatu ke trie mirip dengan

94
00:05:00,350 --> 00:05:02,060
mencari sesuatu dalam trie.

95
00:05:02,060 --> 00:05:05,720
>> Kita akan mulai dengan simpul akar lagi,
berikut pointer sesuai dengan

96
00:05:05,720 --> 00:05:07,990
huruf kunci kami.

97
00:05:07,990 --> 00:05:11,310
Untungnya, kami mampu mengikuti pointer
semua jalan sampai kami mencapai

98
00:05:11,310 --> 00:05:12,770
akhir kunci.

99
00:05:12,770 --> 00:05:16,480
Karena kebun binatang adalah awalan dari kata
zoom, yang merupakan anggota dari

100
00:05:16,480 --> 00:05:19,440
kamus, kita tidak perlu
mengalokasikan node baru.

101
00:05:19,440 --> 00:05:23,140
>> Kita dapat memodifikasi node untuk menunjukkan bahwa
jalan yang mengarah ke karakter

102
00:05:23,140 --> 00:05:25,360
itu merupakan kunci dalam kamus kami.

103
00:05:25,360 --> 00:05:28,630
Sekarang, mari kita coba memasukkan
BATH kunci ke trie.

104
00:05:28,630 --> 00:05:32,260
Kita akan mulai pada simpul akar
dan ikuti petunjuk lagi.

105
00:05:32,260 --> 00:05:35,620
Tapi dalam situasi ini, kita memukul mati seorang
berakhir sebelum kita dapat sampai ke

106
00:05:35,620 --> 00:05:36,940
akhir kunci.

107
00:05:36,940 --> 00:05:40,980
Sekarang, kita harus mengalokasikan beberapa baru
node akan perlu untuk mengalokasikan baru

108
00:05:40,980 --> 00:05:43,660
simpul untuk setiap tersisa
surat kunci kami.

109
00:05:43,660 --> 00:05:46,740
>> Dalam hal ini, kita hanya perlu
untuk mengalokasikan satu node baru.

110
00:05:46,740 --> 00:05:50,590
Kemudian kita harus membuat indeks H
referensi node baru ini.

111
00:05:50,590 --> 00:05:54,070
Sekali lagi, kita dapat memodifikasi node untuk
menunjukkan bahwa jalan karakter

112
00:05:54,070 --> 00:05:57,120
menuju itu merupakan
kunci dalam kamus kami.

113
00:05:57,120 --> 00:06:00,730
Mari kita alasan tentang asymptotic
kompleksitas prosedur untuk ini

114
00:06:00,730 --> 00:06:02,110
dua operasi.

115
00:06:02,110 --> 00:06:06,420
>> Kami melihat bahwa dalam kedua kasus nomor
dari langkah algoritma kami mengambil itu

116
00:06:06,420 --> 00:06:09,470
sebanding dengan jumlah
huruf dalam kata kunci.

117
00:06:09,470 --> 00:06:10,220
Itu benar.

118
00:06:10,220 --> 00:06:13,470
Bila Anda ingin mencari kata dalam
trie Anda hanya perlu iterate melalui

119
00:06:13,470 --> 00:06:17,100
huruf satu per satu sampai Anda baik
mencapai akhir kata atau

120
00:06:17,100 --> 00:06:19,060
menemui jalan buntu dalam trie.

121
00:06:19,060 --> 00:06:22,470
>> Dan ketika Anda ingin memasukkan kunci
nilai pasangan menjadi trie menggunakan

122
00:06:22,470 --> 00:06:26,250
Prosedur kita bahas, kasus terburuk
akan memiliki Anda mengalokasikan sebuah node baru

123
00:06:26,250 --> 00:06:27,550
untuk setiap huruf.

124
00:06:27,550 --> 00:06:31,290
Dan kita akan berasumsi bahwa alokasi
adalah operasi waktu konstan.

125
00:06:31,290 --> 00:06:35,850
Jadi jika kita asumsikan bahwa panjang kunci adalah
dibatasi oleh sebuah konstanta tetap, baik

126
00:06:35,850 --> 00:06:39,400
penyisipan dan mencari konstan
operasi waktu untuk trie.

127
00:06:39,400 --> 00:06:42,930
>> Jika kita tidak membuat asumsi bahwa
panjang kunci dibatasi oleh tetap

128
00:06:42,930 --> 00:06:46,650
konstan, maka penyisipan dan mencari,
dalam kasus terburuk, yang linear di

129
00:06:46,650 --> 00:06:48,240
panjang kunci.

130
00:06:48,240 --> 00:06:51,800
Perhatikan bahwa jumlah item yang disimpan
dalam trie tidak mempengaruhi tampilan up

131
00:06:51,800 --> 00:06:52,820
atau waktu penyisipan.

132
00:06:52,820 --> 00:06:55,360
Ini hanya dipengaruhi oleh
panjang kunci.

133
00:06:55,360 --> 00:06:59,300
>> Sebaliknya, menambahkan entri untuk, katakanlah,
tabel hash cenderung membuat

134
00:06:59,300 --> 00:07:01,250
masa depan terlihat lebih lambat.

135
00:07:01,250 --> 00:07:04,520
Meskipun hal ini mungkin terdengar menarik pada awalnya,
kita harus diingat bahwa

136
00:07:04,520 --> 00:07:08,740
kompleksitas asimtotik menguntungkan tidak
berarti bahwa dalam prakteknya data

137
00:07:08,740 --> 00:07:11,410
Struktur niscaya
tercela.

138
00:07:11,410 --> 00:07:15,860
Kita juga harus mempertimbangkan bahwa untuk menyimpan
kata dalam trie kita butuhkan, di terburuk

139
00:07:15,860 --> 00:07:19,700
kasus, sejumlah node proporsional
dengan panjang dari kata itu sendiri.

140
00:07:19,700 --> 00:07:21,880
>> Tries cenderung menggunakan banyak ruang.

141
00:07:21,880 --> 00:07:25,620
Itu berbeda dengan tabel hash,
di mana kita hanya perlu satu node baru

142
00:07:25,620 --> 00:07:27,940
menyimpan beberapa pasangan nilai kunci.

143
00:07:27,940 --> 00:07:31,370
Sekarang, sekali lagi dalam teori, ruang besar
konsumsi tidak tampak seperti besar

144
00:07:31,370 --> 00:07:34,620
menangani, terutama mengingat bahwa yang modern
komputer memiliki gigabyte dan

145
00:07:34,620 --> 00:07:36,180
gigabyte memori.

146
00:07:36,180 --> 00:07:39,200
Tapi ternyata bahwa kita masih memiliki
khawatir tentang penggunaan memori dan

147
00:07:39,200 --> 00:07:42,540
organisasi demi
kinerja, karena komputer modern

148
00:07:42,540 --> 00:07:46,960
memiliki mekanisme di tempat di bawah
hood untuk mempercepat akses memori.

149
00:07:46,960 --> 00:07:51,180
>> Tapi mekanisme ini bekerja dengan baik ketika
Akses memori yang dibuat kompak

150
00:07:51,180 --> 00:07:52,810
wilayah atau daerah.

151
00:07:52,810 --> 00:07:55,910
Dan simpul dari trie bisa berada
di mana saja di tumpukan itu.

152
00:07:55,910 --> 00:07:58,390
Tapi ini trade-off
bahwa kita harus mempertimbangkan.

153
00:07:58,390 --> 00:08:01,440
>> Ingatlah bahwa, ketika memilih data
struktur untuk suatu tugas tertentu, kita

154
00:08:01,440 --> 00:08:04,420
harus berpikir tentang apa jenis
operasi struktur data perlu

155
00:08:04,420 --> 00:08:07,140
dukungan dan berapa banyak kinerja
dari masing-masing

156
00:08:07,140 --> 00:08:09,080
operasi penting bagi kami.

157
00:08:09,080 --> 00:08:11,300
Operasi ini bahkan mungkin
melampaui hanya

158
00:08:11,300 --> 00:08:13,430
tampilan dasar dan penyisipan.

159
00:08:13,430 --> 00:08:17,010
Misalkan kita ingin menerapkan jenis
auto-lengkap fungsi, banyak

160
00:08:17,010 --> 00:08:18,890
seperti mesin pencari Google tidak.

161
00:08:18,890 --> 00:08:22,210
Artinya, mengembalikan semua kunci dan
berpotensi nilai-nilai yang

162
00:08:22,210 --> 00:08:24,130
memiliki awalan yang diberikan.

163
00:08:24,130 --> 00:08:27,050
>> Sebuah trie unik berguna
untuk operasi ini.

164
00:08:27,050 --> 00:08:29,890
Ini mudah untuk iterate melalui
yang trie untuk masing-masing karakter

165
00:08:29,890 --> 00:08:30,950
awalan.

166
00:08:30,950 --> 00:08:33,559
Sama seperti mencari operasi,
kita bisa mengikuti pointer

167
00:08:33,559 --> 00:08:35,400
karakter demi karakter.

168
00:08:35,400 --> 00:08:38,659
Kemudian, ketika kami tiba di akhir
awalan, kita bisa iterate melalui

169
00:08:38,659 --> 00:08:42,049
sisa bagian dari struktur data
karena salah satu tombol di luar

170
00:08:42,049 --> 00:08:43,980
titik ini memiliki awalan.

171
00:08:43,980 --> 00:08:47,670
>> Ini juga mudah untuk mendapatkan daftar ini
dalam urutan abjad sejak

172
00:08:47,670 --> 00:08:50,970
elemen dari array yang anak
diperintahkan abjad.

173
00:08:50,970 --> 00:08:54,420
Jadi mudah-mudahan Anda akan mempertimbangkan
Pemberian mencoba mencoba.

174
00:08:54,420 --> 00:08:56,085
Aku Kevin Schmid, dan ini adalah CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, ini adalah awal
dari penurunan.

177
00:09:00,790 --> 00:09:01,350
Maafkan aku.

178
00:09:01,350 --> 00:09:01,870
Maaf.

179
00:09:01,870 --> 00:09:02,480
Maaf.

180
00:09:02,480 --> 00:09:03,130
Maaf.

181
00:09:03,130 --> 00:09:03,950
>> Menyerang empat.

182
00:09:03,950 --> 00:09:04,360
Aku keluar.

183
00:09:04,360 --> 00:09:05,280
Maaf.

184
00:09:05,280 --> 00:09:06,500
Maaf.

185
00:09:06,500 --> 00:09:07,490
Maaf.

186
00:09:07,490 --> 00:09:12,352
Maaf untuk membuat orang yang
harus mengedit ini gila.

187
00:09:12,352 --> 00:09:13,280
>> Maaf.

188
00:09:13,280 --> 00:09:13,880
Maaf.

189
00:09:13,880 --> 00:09:15,080
Maaf.

190
00:09:15,080 --> 00:09:15,680
Maaf.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Well done.

192
00:09:16,280 --> 00:09:17,530
Itu benar-benar dilakukan dengan baik.

193
00:09:17,530 --> 00:09:18,430