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. Maaf. Maaf. 

Menyerang empat. Aku keluar. Maaf. Maaf. Maaf. Maaf untuk membuat orang yang harus mengedit ini gila. 

Maaf. Maaf. Maaf. Maaf. 

SPEAKER 1: Well done. Itu benar-benar dilakukan dengan baik.