>> KEVIN Schmid: Kadang-kadang, ketika membangun sebuah Program, Anda mungkin ingin memanfaatkan
struktur data yang dikenal sebagai kamus.
Sebuah peta kunci kamus, yang biasanya string, nilai-nilai, int,
karakter, pointer ke beberapa objek, apapun yang kita inginkan.
Ini seperti kamus biasa kata peta bahwa melalui definisi.
>> Kamus menyediakan kami dengan kemampuan untuk menyimpan informasi
berhubungan dengan sesuatu dan mencarinya nanti.
Jadi bagaimana kita benar-benar menerapkan kamus dalam, katakanlah, kode C yang kita bisa
digunakan dalam salah satu program kami?
Well, ada banyak cara yang kita bisa menerapkan kamus.
>> Untuk satu, kita bisa menggunakan array yang kita kembali ukuran dinamis atau kita bisa menggunakan
linked list, tabel hash atau pohon biner.
Tapi apa pun yang kita pilih, kita harus berhati-hati dari efisiensi dan
kinerja pelaksanaan.
Kita harus memikirkan algoritma yang digunakan untuk menyisipkan dan mencari barang-barang ke dalam
struktur data kami.
>> Untuk saat ini, mari kita asumsikan bahwa kita ingin menggunakan string sebagai kunci.
Mari kita bicara tentang satu kemungkinan, struktur data yang disebut trie.
Jadi, inilah representasi visual dari trie.
>> Seperti gambar menunjukkan, trie adalah struktur data pohon dengan
node dihubungkan bersama.
Kita melihat bahwa jelas ada root simpul dengan beberapa link untuk memperluas
node lain.
Tapi apa setiap node terdiri dari?
Jika kita mengasumsikan bahwa kita menyimpan kunci dengan hanya karakter abjad, dan
kita tidak peduli tentang kapitalisasi, berikut adalah definisi dari sebuah node yang
akan cukup.
>> Sebuah benda yang tipenya struct node memiliki dua bagian
disebut data dan anak-anak.
Kami telah meninggalkan bagian data sebagai komentar untuk digantikan oleh komponen
deklarasi ketika struct node tergabung dalam program C.
Data bagian dari sebuah node mungkin Nilai Boolean untuk menunjukkan apakah atau
tidak node merupakan penyelesaian dari kunci kamus atau mungkin
string yang mewakili definisi dari sebuah kata dalam kamus.
>> Kami akan menggunakan wajah tersenyum untuk menunjukkan ketika data hadir dalam node.
Ada 26 elemen dalam kami anak array, satu indeks
per karakter abjad.
Kita akan melihat signifikansi ini segera.
>> Mari kita lihat lebih dekat dari simpul akar dalam diagram kita, yang tidak memiliki data
terkait dengan itu, seperti yang ditunjukkan oleh tidak adanya wajah smiley di
bagian data.
Panah membentang dari bagian-bagian anak-anak array yang merupakan non-node
pointer ke node lain.
Misalnya, panah membentang dari elemen kedua anak-anak
mewakili huruf B dalam kunci kamus.
Dan dalam diagram yang lebih besar kami label dengan B.
>> Perhatikan bahwa dalam diagram yang lebih besar, ketika kita menggambar pointer ke node lain,
Tidak peduli di mana panah memenuhi bahwa node lainnya.
Kami sampel kamus trie berisi dua kata, itu dan zoom.
Mari kita berjalan melalui contoh mencari data untuk kunci.
>> Misalkan kita ingin mencari dengan sesuai nilai untuk mandi utama.
Kami akan mulai melihat kami up pada simpul akar.
Kemudian kita akan mengambil huruf pertama dari kami kunci, B, dan menemukan yang sesuai
tempat dalam array anak-anak kita.
Perhatikan bahwa ada tepat 26 spot dalam array, satu untuk setiap huruf dari
alfabet.
Dan kita akan memiliki tempat mewakili huruf alfabet dalam rangka.
>> Kita akan melihat indeks kedua kemudian, Indeks satu, untuk B. Secara umum, jika kita
memiliki beberapa karakter abjad C kami bisa menentukan tempat yang sesuai
pada anak-anak array menggunakan perhitungan seperti ini.
Kita bisa menggunakan anak-anak yang lebih besar Array jika kita ingin menawarkan tampilan up
kunci dengan jangkauan yang lebih luas dari karakter, seperti seluruh yang
Karakter ASCII set.
>> Dalam hal ini, pointer dalam array anak-anak kita di
Indeks satu tidak null.
Jadi kita akan terus mencari up mandi utama.
Jika kita pernah mengalami pointer nol di tempat yang tepat pada anak-anak
Array sementara kami melintasi node, maka kita harus mengatakan bahwa kita
tidak bisa menemukan apa pun untuk kunci itu.
>> Sekarang, kami akan mengambil surat kedua kunci kami, A, dan terus mengikuti
pointer dengan cara ini sampai kita mencapai akhir kunci kami.
Jika kita mencapai akhir kunci tanpa memukul apapun buntu, pointer null,
seperti yang terjadi di sini, maka kita hanya harus memeriksa satu hal lagi.
Apakah kunci ini benar-benar dalam kamus?
>> Jika demikian, kita harus mencari nilai, sumur icon wajah tersenyum di mana kami diagram
kata berakhir.
Jika ada sesuatu yang lain yang tersimpan dengan data, maka kita bisa mengembalikannya.
Misalnya, kebun binatang kunci bukan dalam kamus, meskipun kita bisa memiliki
mencapai akhir kunci ini tanpa pernah memukul pointer null, sementara kita
iterate melalui trie.
>> Jika kita mencoba untuk mencari mandi kunci, kedua untuk indeks array simpul lalu,
sesuai dengan huruf H, akan telah mengadakan pointer null.
Jadi mandi tidak ada dalam kamus.
Dan trie adalah unik karena tombol tidak pernah secara eksplisit disimpan dalam
struktur data.
Jadi bagaimana kita memasukkan sesuatu menjadi trie?
>> Mari kita memasukkan kunci zoo ke trie kami.
Ingat bahwa wajah tersenyum pada node bisa sesuai kode dengan sederhana
Nilai Boolean untuk menunjukkan kebun binatang yang adalah dalam kamus atau bisa
sesuai dengan informasi lebih lanjut yang kami ingin Anda kaitkan dengan kebun binatang kunci,
seperti definisi kata atau sesuatu yang lain.
Dalam beberapa hal, proses untuk menyisipkan sesuatu ke trie mirip dengan
mencari sesuatu dalam trie.
>> Kita akan mulai dengan simpul akar lagi, berikut pointer sesuai dengan
huruf kunci kami.
Untungnya, kami mampu mengikuti pointer semua jalan sampai kami mencapai
akhir kunci.
Karena kebun binatang adalah awalan dari kata zoom, yang merupakan anggota dari
kamus, kita tidak perlu mengalokasikan node baru.
>> Kita dapat memodifikasi node untuk menunjukkan bahwa jalan yang mengarah ke karakter
itu merupakan kunci dalam kamus kami.
Sekarang, mari kita coba memasukkan BATH kunci ke trie.
Kita akan mulai pada simpul akar dan ikuti petunjuk lagi.
Tapi dalam situasi ini, kita memukul mati seorang berakhir sebelum kita dapat sampai ke
akhir kunci.
Sekarang, kita harus mengalokasikan beberapa baru node akan perlu untuk mengalokasikan baru
simpul untuk setiap tersisa surat kunci kami.
>> Dalam hal ini, kita hanya perlu untuk mengalokasikan satu node baru.
Kemudian kita harus membuat indeks H referensi node baru ini.
Sekali lagi, kita dapat memodifikasi node untuk menunjukkan bahwa jalan karakter
menuju itu merupakan kunci dalam kamus kami.
Mari kita alasan tentang asymptotic kompleksitas prosedur untuk ini
dua operasi.
>> Kami melihat bahwa dalam kedua kasus nomor dari langkah algoritma kami mengambil itu
sebanding dengan jumlah huruf dalam kata kunci.
Itu benar.
Bila Anda ingin mencari kata dalam trie Anda hanya perlu iterate melalui
huruf satu per satu sampai Anda baik mencapai akhir kata atau
menemui jalan buntu dalam trie.
>> Dan ketika Anda ingin memasukkan kunci nilai pasangan menjadi trie menggunakan
Prosedur kita bahas, kasus terburuk akan memiliki Anda mengalokasikan sebuah node baru
untuk setiap huruf.
Dan kita akan berasumsi bahwa alokasi adalah operasi waktu konstan.
Jadi jika kita asumsikan bahwa panjang kunci adalah dibatasi oleh sebuah konstanta tetap, baik
penyisipan dan mencari konstan operasi waktu untuk trie.
>> Jika kita tidak membuat asumsi bahwa panjang kunci dibatasi oleh tetap
konstan, maka penyisipan dan mencari, dalam kasus terburuk, yang linear di
panjang kunci.
Perhatikan bahwa jumlah item yang disimpan dalam trie tidak mempengaruhi tampilan up
atau waktu penyisipan.
Ini hanya dipengaruhi oleh panjang kunci.
>> Sebaliknya, menambahkan entri untuk, katakanlah, tabel hash cenderung membuat
masa depan terlihat lebih lambat.
Meskipun hal ini mungkin terdengar menarik pada awalnya, kita harus diingat bahwa
kompleksitas asimtotik menguntungkan tidak berarti bahwa dalam prakteknya data
Struktur niscaya tercela.
Kita juga harus mempertimbangkan bahwa untuk menyimpan kata dalam trie kita butuhkan, di terburuk
kasus, sejumlah node proporsional dengan panjang dari kata itu sendiri.
>> Tries cenderung menggunakan banyak ruang.
Itu berbeda dengan tabel hash, di mana kita hanya perlu satu node baru
menyimpan beberapa pasangan nilai kunci.
Sekarang, sekali lagi dalam teori, ruang besar konsumsi tidak tampak seperti besar
menangani, terutama mengingat bahwa yang modern komputer memiliki gigabyte dan
gigabyte memori.
Tapi ternyata bahwa kita masih memiliki khawatir tentang penggunaan memori dan
organisasi demi kinerja, karena komputer modern
memiliki mekanisme di tempat di bawah hood untuk mempercepat akses memori.
>> Tapi mekanisme ini bekerja dengan baik ketika Akses memori yang dibuat kompak
wilayah atau daerah.
Dan simpul dari trie bisa berada di mana saja di tumpukan itu.
Tapi ini trade-off bahwa kita harus mempertimbangkan.
>> Ingatlah bahwa, ketika memilih data struktur untuk suatu tugas tertentu, kita
harus berpikir tentang apa jenis operasi struktur data perlu
dukungan dan berapa banyak kinerja dari masing-masing
operasi penting bagi kami.
Operasi ini bahkan mungkin melampaui hanya
tampilan dasar dan penyisipan.
Misalkan kita ingin menerapkan jenis auto-lengkap fungsi, banyak
seperti mesin pencari Google tidak.
Artinya, mengembalikan semua kunci dan berpotensi nilai-nilai yang
memiliki awalan yang diberikan.
>> Sebuah trie unik berguna untuk operasi ini.
Ini mudah untuk iterate melalui yang trie untuk masing-masing karakter
awalan.
Sama seperti mencari operasi, kita bisa mengikuti pointer
karakter demi karakter.
Kemudian, ketika kami tiba di akhir awalan, kita bisa iterate melalui
sisa bagian dari struktur data karena salah satu tombol di luar
titik ini memiliki awalan.
>> Ini juga mudah untuk mendapatkan daftar ini dalam urutan abjad sejak
elemen dari array yang anak diperintahkan abjad.
Jadi mudah-mudahan Anda akan mempertimbangkan Pemberian mencoba mencoba.
Aku Kevin Schmid, dan ini adalah CS50.
>> Ah, ini adalah awal dari penurunan.
Maafkan aku.
Maaf.
>> Menyerang empat.
Aku keluar.
Maaf.
Maaf untuk membuat orang yang harus mengedit ini gila.
>> Maaf.
Maaf.
>> SPEAKER 1: Well done.
Itu benar-benar dilakukan dengan baik.