[MUSIC PLAYING] Doug LLOYD: Jadi kita sudah beringsut lebih dekat dan lebih dekat yang grail suci data struktur, salah satu yang kita dapat menyisipkan dalam, menghapus dari, dan mencari dalam waktu yang konstan. Benar. Itu semacam tujuan. Kami ingin dapat melakukan hal yang sangat, sangat cepat. 

Memiliki kami menemukan itu di sini ketika kita berbicara tentang mencoba? Nah, mari kita lihat. Jadi kita telah melihat beberapa struktur data yang berbeda yang menangani pemetaan disebut pasangan kunci-nilai, pemetaan beberapa bagian dari data untuk beberapa bagian lain dari data yang jadi kami tahu di mana untuk menemukan informasi dalam struktur. 

Jadi untuk array, misalnya, kunci adalah indeks elemen atau array Lokasi 0 atau array 1 dan seterusnya. Dan nilai data yang ada di lokasi tersebut. Jadi apa yang disimpan dalam array 0? Apa yang disimpan dalam array 1 versus hanya 0 dan 1, yang akan menjadi kunci. 

Dengan tabel hash itu semacam gagasan yang sama. Dengan tabel hash, kita memiliki hash ini fungsi yang menghasilkan kode hash. Jadi kuncinya adalah kode hash dari data. Dan nilai, terutama kita berbicara tentang chaining dalam video pada tabel hash, adalah bahwa linked list data yang hash untuk kode hash itu. Benar. Bagaimana pendekatan lain metode ini, meskipun? Bagaimana metode mana kunci dijamin untuk menjadi unik, tidak seperti tabel hash, di mana kita bisa berakhir dengan dua buah data memiliki kode hash yang sama. Dan kemudian kita harus berurusan dengan bahwa dengan baik probing atau lebih sebaiknya chaining untuk memperbaiki masalah itu. 

Jadi sekarang kita bisa menjamin bahwa kunci kami akan menjadi unik. Dan bagaimana jika nilai kami hanya sesuatu yang mudah sebagai benar dan salah yang memberitahu kita apakah atau tidak sepotong informasi ada dalam struktur? Sebuah Boolean bisa sesederhana sedikit. Realistis itu mungkin byte lebih mungkin dibandingkan sedikit. Tapi itu jauh lebih kecil daripada menyimpan mungkin string 50-karakter, sebagai contoh. 

Jadi mencoba, mirip dengan hash tabel, yang menggabungkan array dan linked list, mencoba menggabungkan array, struktur, dan pointer bersama-sama untuk menyimpan data dalam cara yang menarik yang cukup berbeda dari apa yang telah kita lihat sejauh ini. Sekarang kita menggunakan data sebagai peta jalan untuk menavigasi struktur data. Dan jika kita dapat mengikuti roadmap, jika kita bisa ikuti data dari awal sampai akhir, kami akan mengetahui apakah data yang ada di trie. 

Dan jika kita tidak bisa mengikuti peta dari yang berarti untuk mengakhiri sama sekali, data tidak bisa eksis. Sekali lagi, kunci di sini adalah dijamin untuk menjadi unik. Dan tidak seperti tabel hash, kita tidak akan pernah harus berurusan dengan tabrakan di sini. Dan tidak ada dua buah data memiliki persis roadmap yang sama kecuali data yang identik. 

Jika kita memasukkan John, maka kita mencari John. Itu dua potong identik data, kanan, kita melihat melalui. Tapi sebaliknya, setiap dua potong data dijamin untuk memiliki peta jalan yang unik melalui struktur data. Dan kita akan melihat pada visual ini hanya dalam beberapa saat. 

Kami akan melakukan ini dengan mencoba membuat struktur data baru, pemetaan pasangan nilai kunci berikut. Dalam hal ini, kita tidak akan menggunakan sesuatu yang sederhana seperti Boolean. Kami benar-benar akan menyimpan string. Dan string yang akan menjadi nama sebuah universitas. 

Dan kunci akan menjadi tahun ketika universitas yang didirikan. Semua tahun untuk universitas akan menjadi empat angka. Dan jadi kita akan menggunakan empat angka menavigasi melalui struktur data. Dan kita akan melihat, lagi, bagaimana kami melakukan itu hanya satu detik. 

Pada ujung jalan, kita akan melihat nama dari universitas yang sesuai untuk kunci itu, empat digit. Ide dasar di balik trie adalah kita memiliki rute sentral. Jadi pikirkan tentang hal itu seperti pohon. Dan ini mirip dalam ejaan dan dalam konsep pohon. Umumnya ketika kita berpikir tentang pohon di dunia nyata, mereka memiliki akar yang dalam tanah dan mereka tumbuh ke atas dan mereka memiliki cabang dan mereka memiliki daun. Dan pada dasarnya ide trie adalah persis sama, kecuali root yang berlabuh di suatu tempat di langit. Dan daun di bagian bawah. 

Jadi itu semacam seperti mengambil pohon dan hanya membalik terbalik. Namun masih ada cabang. Dan mereka akan menjadi jalur kami, mereka akan koneksi kami dari akar ke daun. Dalam hal ini, orang-orang jalan, cabang-cabang diberi label dengan angka yang kami kirim cara untuk pergi dari tempat kami berada. 

Jika kita melihat 0, kita turun cabang ini, jika kita melihat 1, kita turun cabang ini, dan sebagainya dan sebagainya. Nah, apa artinya ini? Nah, itu berarti bahwa di setiap titik persimpangan dan setiap node dalam tengah dan setiap cabang, ada 10 kemungkinan tempat-tempat yang kita bisa pergi. Jadi ada 10 pointer dari setiap lokasi. 

Dan ini adalah di mana mencoba bisa mendapatkan sedikit menakutkan bagi seseorang siapa yang tidak memiliki banyak Pengalaman dalam ilmu komputer sebelumnya. Tapi mencoba benar-benar cukup mengagumkan. Dan jika Anda memiliki kesempatan untuk bekerja dengan mereka dan Anda bersedia untuk menggali-in dan bereksperimen dengan mereka, mereka benar-benar cukup menarik struktur data untuk bekerja dengan. Jika kita ingin memasukkan unsur dalam trie, semua yang perlu kita lakukan adalah membangun jalan yang benar dari akar ke daun. Inilah yang setiap langkah bersama jalan mungkin terlihat seperti. Kita akan mendefinisikan data baru struktur untuk node baru yang disebut trie. 

Dan di dalam data yang struktur ada dua buah. Kita akan menyimpan nama universitas. Dan kita akan menyimpan array pointer ke node lain dari jenis yang sama. Jadi, sekali lagi, ini adalah semacam itu dari konsep di mana-mana kita, kami di 10 mungkin tempat kita bisa pergi. Jika kita melihat 0, kita turun cabang ini. Jika kita melihat 1, cabang ini, dan seterusnya dan seterusnya dan seterusnya. Jika kita berkata 9, kita turun cabang ini. Jadi di setiap titik persimpangan, kita bisa pergi 10 tempat mungkin. Jadi setiap node memiliki mengandung 10 pointer ke node lain, untuk 10 node lain. 

Dan data kita menyimpan adalah hanya nama universitas. Jadi mari kita membangun trie. Mari kita masukkan beberapa item dalam trie kami. Jadi di bagian paling atas, ini adalah simpul akar kami. Ini mungkin akan menjadi sesuatu Anda akan secara global declare. Dan Anda akan secara global mempertahankan pointer ke node ini selalu. 

Anda akan mengatakan, akar sama, dan Anda akan malloc sendiri trie simpul. Dan Anda tidak akan pernah menyentuh akar lagi. Setiap kali Anda ingin mulai menavigasi melalui, Anda mengatur pointer lain sama dengan akar, seperti trav, yang merupakan contoh saya digunakan dalam banyak video saya di sini di tumpukan dan antrian dan daftar link and sebagainya. 

Anda mengatur pointer lain disebut trav untuk traversal. Dan Anda menggunakan trav untuk menavigasi melalui struktur data. Jadi mari kita lihat bagaimana ini mungkin terlihat. Jadi sekarang, apa tidak node terlihat seperti? Nah, seperti data kami Struktur deklarasi ditunjukkan, kita memiliki string, yang dalam hal ini adalah kosong. Ada apa di sini. 

Dan sebuah array dari 10 pointer. Dan sekarang, kita hanya memiliki 1 node dalam trie ini. Tidak ada yang lain di dalamnya. Jadi semua 10 dari mereka pointer titik untuk null. Itulah yang merah menunjukkan. 

Mari kita masukkan string Harvard. Mari kita masukkan Universitas Harvard ke trie ini, yang didirikan pada tahun 1636. Kami ingin menggunakan kunci, 1636, untuk memberitahu kami di mana kami akan menyimpan Harvard di trie. Sekarang, bagaimana kita bisa melakukan itu? 

Ini mungkin terlihat seperti ini. Kita mulai pada akar. Dan kami memiliki 10 tempat ini kita bisa pergi. Akar adalah sama seperti simpul lain dari trie. Ada 10 tempat kita bisa pergi dari sini. 

Di mana kita mungkin ingin untuk pergi jika kuncinya adalah 1636? Ada benar-benar dua pilihan. Benar. Kita dapat membangun kunci dari kanan ke kiri dan mulai dengan 6. Atau kita bisa membangun kunci dari kiri ke kanan dan mulai dengan 1. 

Ini mungkin lebih intuitif sebagai manusia untuk memahami kita akan hanya ke kiri ke kanan. Dan jadi jika saya ingin memasukkan Harvard ke trie ini, Saya mungkin ingin memulai dengan memulai pada akar, melihat 10 pilihan saya di depan saya, dan mengatakan Saya ingin pergi ke 1 jalur. OKE. 

Sekarang, 1 jalan saat ini nol. Jadi jika saya ingin melanjutkan ke jalan yang untuk memasukkan unsur ini ke trie, Saya harus malloc node baru, memiliki 1 titik di sana, dan kemudian aku baik untuk pergi. 

Jadi saya pada dasarnya saya di titik di mana aku berdiri pada akar pohon atau trie dan ada 10 cabang. Tapi setiap cabang memiliki gerbang di depannya. Benar. Karena tidak ada yang lain ada. Tidak ada perjalanan yang aman. Itu berarti bahwa tidak ada bawah salah satu dari mereka cabang. Jika saya ingin mulai membangun sesuatu, saya ingin menghapus gerbang. Saya ingin menghapus gerbang di depan nomor 1. Dan saya ingin berjalan itu. Dan saya ingin membangun tempat lain bagi saya untuk pergi. 

Dan itulah yang saya lakukan di sini. Jadi 1 tidak lagi menunjuk ke null. Aku sudah mengatakan itu aman untuk turun di sini sekarang. Saya membangun node lain. Dan ketika saya sampai ke simpul itu, saya memiliki keputusan lain untuk membuat. Di mana aku akan pergi dari sini? 

Yah, aku sudah turun 1. Jadi sekarang saya mungkin ingin pergi ke 6. Benar. Sekali lagi, saya memiliki 10 lokasi saya dapat memilih. Jadi mari kita sekarang turun nomor 6. Jadi saya menghapus gerbang di depan nomor 6. Dan aku berjalan di sana. Dan saya membangun node lain. Dan aku sudah mencapai titik persimpangan lain. 

Sekali lagi, saya memiliki 10 pilihan untuk mana aku bisa pergi. Aku pindah 1-6. Jadi sekarang saya mungkin ingin pergi ke 3. 3, yang mana aku bisa pergi ke sana. Jadi saya harus membersihkan jalan dan membangun sendiri ruang baru. Dan kemudian dari 3, di mana saya ingin pergi? Saya ingin pergi ke 6. 

Dan, sekali lagi, saya harus menghapus cara untuk melakukannya. Jadi sekarang aku telah menggunakan kunci untuk menyisipkan membuat node dan mulai membangun trie ini. Saya sudah mulai pada akar. Aku sudah turun 1.636. Dan sekarang aku di bagian bawah ada pada simpul tersebut. Dan Anda mungkin bisa melihatnya di layar Anda. 

Ini ditandai dengan warna kuning. Di situlah saya saat saya. Kunci saya dilakukan. Saya telah kehabisan setiap posisi di kunci. Jadi saya tidak bisa pergi lebih jauh. Jadi pada titik ini, semua saya benar-benar perlu lakukan adalah mengatakan, OK. Ini semacam seperti mencari turun di tanah, jika Anda membayangkan diri semacam ini jalan dengan koneksi yang berbeda. Semacam melihat ke bawah dan semacam semprot lukisan Harvard di tanah. Itulah nama ini. Tahu itu apa di lokasi ini. Jika kita mulai dari akar dan kami turun 1 dan kemudian 6 dan kemudian 3 dan kemudian 6, di mana kita? Nah jika kita melihat ke bawah dan kita melihat Harvard, kemudian kita tahu bahwa Harvard adalah didirikan pada 1636 berdasarkan cara kita menerapkan struktur data. Jadi itu mudah-mudahan langsung. Kita akan melakukan dua sisipan lagi. Dan mudah-mudahan itu akan membantu untuk melihat ini dilakukan dua kali lagi. 

Sekarang, mari kita masukkan universitas lain. Mari kita masukkan ke dalam Yale trie ini. Yale didirikan pada 1701. Jadi kita akan mulai di akar, seperti yang kita selalu lakukan. Dan kami menetapkan pointer traversal. Kita akan menggunakannya untuk bergerak melalui. Hal pertama yang ingin kita lakukan adalah pergi ke 1 jalur. Itulah digit pertama kunci kami. Untungnya, meskipun, kita tidak harus melakukan pekerjaan apapun saat ini. 1 jalur sudah dibersihkan. Aku dibersihkan itu sebelumnya ketika saya itu memasukkan Harvard di 1636. Jadi aku bisa bergerak turun 1 dan hanya pergi ke sana. Jika bisa bergerak turun 1. 

Sekarang, meskipun, saya ingin pergi ke 7. Aku membuka jalan pada 6. Aku tahu aku bisa dengan aman melanjutkan menyusuri jalan 6. Tapi aku harus melanjutkan pada 7 jalan. Jadi apa yang harus saya lakukan? Nah, seperti sebelumnya, saya hanya perlu untuk membersihkan pintu gerbang, keluar dari jalan, dan membangun node baru dari 7 jalan. Seperti ini. 

Jadi sekarang aku sudah pindah 1 dan kemudian 7. Dan sekarang perhatikan, aku semacam dari pada ranting baru ini. Benar. Segala sesuatu yang lain dari 16 , aku tidak peduli tentang. Aku tidak melakukan apa-apa 16. Aku melakukan hal-hal 17. 

Jadi sekarang dari 17, saya harus semacam merintis jalan baru di sini. Digit berikutnya kunci adalah 0. Saya jelas tidak bisa mendapatkan tempat. Aku hanya membangun node ini. Jadi saya tahu tidak ada jalur ke depan dari sini. Jadi saya harus membuat satu sendiri. 

Jadi saya malloc node baru dan memiliki 0 poin di sana. Dan kemudian sekali lagi, saya malloc sebuah node baru dan memiliki satu titik ada. Sekali lagi, saya telah kehabisan kunci, 1701. Jadi saya melihat ke bawah dan saya semprot cat Yale. Itulah nama node ini. 

Dan sekarang jika saya merasa perlu untuk melihat apakah Yale adalah dalam trie ini, saya mulai akar, Aku turun 1701, dan melihat ke bawah. Dan jika saya melihat Yale semprot dicat ke tanah, maka Aku tahu Yale ada di trie ini. Mari kita lakukan satu lagi. Mari kita masukkan ke dalam Dartmouth ini trie, yang didirikan pada tahun 1769. 

Mulai dari akar lagi. Digit pertama saya kunci saya adalah 1. Aku bisa bergerak turun jalan itu. Yang sudah ada. Digit berikutnya dari kunci adalah 7. Aku bisa bergerak turun jalan itu. Ini ada juga. 

Berikutnya adalah 6. Dari sini, dari tempat saya saat ini saya kuning ada di node tengah, 6 saat ini terkunci. Jika saya ingin pergi ke jalan itu, Saya harus membangun sendiri. Jadi saya akan malloc node baru dan memiliki 6 titik ada. Dan kemudian, sekali lagi, aku terik jalan baru di sini. 

Jadi saya malloc node baru sehingga dari nomor jalan node-- 9-- dan kemudian sekarang jika saya bepergian 1769, dan saya melihat ke bawah. Tidak ada saat ini semprot dicat ada. Saya bisa menulis Dartmouth. Dan aku sudah dimasukkan Dartmouth ke trie. 

Jadi itu memasukkan hal dalam trie. Sekarang kita ingin mencari hal-hal. Bagaimana kita mencari hal-hal di trie? Nah, itu cukup banyak ide yang sama. Sekarang kita hanya menggunakan angka kunci untuk melihat apakah kita dapat menavigasi dari akar di mana kita ingin pergi di trie. 

Jika kita menemui jalan buntu pada setiap titik, maka kita tahu bahwa elemen yang tidak bisa ada atau jalan yang akan telah dibersihkan. Jika kita membuat semua jalan ke akhirnya, semua yang perlu kita lakukan adalah melihat ke bawah dan melihat apakah itu elemen yang kita cari. Jika ya, sukses. Jika tidak, gagal. 

Jadi mari kita mencari Harvard pada trie ini. Kita mulai pada akar. Dan, sekali lagi, kita akan membuat pointer traversal untuk melakukan langkah kami untuk kami. Dari akar kita tahu bahwa Tempat pertama yang perlu kita pergi adalah 1, kita bisa melakukan itu? Ya kita bisa. Jika aman ada. Kita bisa pergi ke sana. 

Sekarang, tempat berikutnya kita perlu pergi adalah 6. Apakah 6 jalan ada dari sini? Ya, itu tidak. Kami bisa turun 6 jalan. Dan kita berakhir di sini. 

Bisakah kita pergi ke 3 jalan dari sini? Nah, ternyata, ya, yang ada juga. Dan kita bisa mendapatkan di 6 jalan dari sini? Ya kita bisa. 

Kami belum cukup menjawab pertanyaan belum. Masih ada satu lagi langkah, yang sekarang kita perlu untuk melihat ke bawah dan melihat apakah itu actually-- jika kita sedang mencari Harvard, adalah bahwa apa yang kita temukan setelah kami knalpot kunci? Dalam contoh kita gunakan di sini, tahun selalu empat digit. Tetapi Anda mungkin menggunakan contoh di mana Anda menyimpan kamus kata-kata. 

Dan bukan memiliki 10 pointer untuk lokasi saya, Anda mungkin memiliki 26. Satu untuk setiap huruf dari alfabet. Dan ada beberapa kata-kata seperti kelelawar, yang merupakan bagian dari batch, misalnya. Dan bahkan jika Anda sampai ke akhir kunci dan Anda melihat ke bawah, Anda mungkin tidak melihat apa Anda sedang mencari. 

Sehingga Anda selalu harus melintasi seluruh jalan dan kemudian jika Anda berhasil dapat untuk melintasi seluruh jalan, melihat ke bawah dan melakukan satu konfirmasi akhir. Adalah bahwa apa yang saya cari? Yah, aku melihat ke bawah setelah memulai di bagian atas dan pergi 1.636. Aku melihat ke bawah. Saya melihat Harvard. Jadi, ya, saya berhasil. Bagaimana jika apa yang saya cari tidak dalam trie, meskipun. Bagaimana jika saya sedang mencari Princeton, yang didirikan pada tahun 1746. Dan 1746 menjadi kunci saya untuk menavigasi trie. Yah, aku mulai akar. Dan tempat pertama yang saya ingin untuk turun 1 jalur. Bisakah saya melakukannya? Ya saya bisa. 

Dapatkah saya turun 7 jalan dari sana? Ya saya bisa. Yang ada juga. Tapi saya bisa turun 4 jalan dari sini? Itu seperti mengajukan pertanyaan, bisa Saya melanjutkan ke yang kecil persegi bahwa saya telah ditandai dengan warna kuning? Tidak ada yang ada. Benar. 

Tidak ada cara maju menuruni 4 jalur. Jika Princeton berada di trie ini, yang 4 akan telah dibersihkan untuk kita sudah. Dan pada titik ini kami telah mencapai jalan buntu. Kita tidak bisa pergi lebih jauh. Dan sehingga kita dapat mengatakan, pasti, tidak ada. Princeton tidak ada dalam trie ini. 

Jadi apa arti dari semua ini? Benar. Ada banyak hal yang terjadi di sini. Ada petunjuk di semua tempat. Dan, seperti yang Anda lihat hanya dari diagram, ada banyak node yang adalah jenis terbang di sekitar. Tapi perhatikan setiap kali kita ingin memeriksa apakah ada sesuatu yang di trie, kami hanya harus membuat 4 langkah. 

Setiap kali kita ingin memasukkan sesuatu di trie, kita harus membuat 4 langkah, mungkin mallocing beberapa hal di sepanjang jalan. Tapi seperti yang kita lihat ketika kita dimasukkan Dartmouth ke trie, kadang-kadang beberapa jalan mungkin sudah dibersihkan untuk kita. Dan sehingga trie kami akan lebih besar dan lebih besar, yang harus kita melakukan sedikit pekerjaan setiap kali untuk menyisipkan hal-hal baru karena kita sudah sudah dibangun banyak menengah cabang di sepanjang jalan. Jika kita hanya pernah harus melihat 4 hal, 4 hanya konstan. Kami benar-benar adalah jenis mendekati waktu penyisipan konstan dan waktu pencarian konstan. Tradeoff, tentu saja, adalah bahwa trie ini, karena Anda mungkin bisa mengatakan, sangat besar. Masing-masing dari node ini memakan banyak ruang. 

Tapi itu tradeoff. Jika kita ingin benar-benar cepat penyisipan, penghapusan sangat cepat, dan lookup benar-benar cepat, kita harus memiliki banyak data terbang di sekitar. Kita harus menyisihkan banyak ruang dan memori untuk struktur data untuk eksis. 

Dan jadi itu tradeoff. Tapi sepertinya kita mungkin telah menemukan itu. Kita mungkin telah menemukan bahwa grail suci struktur data dengan penyisipan cepat, penghapusan, dan pencarian. Dan mungkin ini akan menjadi struktur data yang sesuai menggunakan informasi apapun kita mencoba untuk menyimpan. Aku Doug Lloyd, ini CS50.