[MUSIC PLAYING] DAVID Malan: Ini adalah CS50. Dan ini adalah baik awal dan end-- seperti literally-- hampir akhir minggu enam. 

Saya pikir saya akan berbagi sedikit dari fakta yang menyenangkan. Aku sudah menarik ini naik dari mengatur data masa lalu semester. Anda mungkin ingat bahwa kami meminta Anda pada setiap bentuk set p jika Anda telah menyaksikan secara online atau jika Anda telah menghadiri secara pribadi. Dan di sini adalah data. Jadi hari ini sangat banyak diprediksi. Tapi kami ingin menghabiskan sedikit waktu dengan Anda tetap. Apakah ada yang mau menerka mengapa hal ini Grafik begitu bergerigi, naik turun, naik turun, begitu konsisten? Apa masing-masing puncak dan palung mewakili? 

AUDIENCE: [tidak terdengar] DAVID Malan: Memang. Dan yang lebih menggelikan, Allah melarang, kita memegang salah satu kuliah pada hari Jumat pada awal semester, itulah yang kita lihat terjadi. Jadi hari ini, kami ikut serta dalam sedikit lebih lanjut tentang struktur data. Dan untuk memberikan Anda lebih dari yang solid model mental untuk masalah jam lima, yang sekarang keluar. Salah ejaan, dimana, kita akan tangan Anda file teks 100.000 ditambah kata-kata bahasa Inggris, dan Anda akan memiliki untuk mengetahui bagaimana cerdik beban mereka ke dalam memori, ke dalam RAM, dengan menggunakan beberapa data struktur pilihan Anda. 

Sekarang satu struktur data tersebut bisa jadi, tapi mungkin tidak boleh, yang terkait daftar yang cukup sederhana, yang kami memperkenalkan terakhir kali. Dan sebuah linked list memiliki setidaknya satu keuntungan atas array. Apa salah satu keuntungan dari linked list bisa dibilang? 

AUDIENCE: Penyisipan. 

DAVID Malan: Penyisipan. Apa yang Anda maksud dengan itu? 

AUDIENCE: Di mana saja sepanjang daftar [tidak terdengar]. 

DAVID Malan: Baik. Jadi Anda dapat memasukkan unsur mana pun Anda ingin di tengah-tengah daftar tanpa harus mengocok apa-apa, yang kami menyimpulkan, dalam pemilahan kami diskusi, tidak selalu hal yang baik, karena butuh waktu untuk benar-benar bergerak semua orang manusia ke kiri atau kanan. Dan dengan linked list, Anda dapat hanya mengalokasikan dengan malloc, node baru, dan kemudian memperbarui beberapa pointers-- dua, tiga operasi max-- dan kami dapat slot seseorang di mana saja ke dalam daftar. 

Apa lagi yang menguntungkan tentang linked list? Ya? 

AUDIENCE: [tidak terdengar] DAVID Malan: Perfect. Sempurna. Ini benar-benar dinamis. Dan bahwa Anda tidak melakukan, di muka, beberapa ukuran tetap sepotong memori, seperti Anda akan memiliki untuk dengan array, terbalik dari yang adalah bahwa Anda dapat mengalokasikan node hanya pada permintaan sehingga hanya menggunakan banyak ruang karena Anda benar-benar membutuhkan. Sebaliknya dengan array, Anda mungkin sengaja mengalokasikan terlalu sedikit. Dan kemudian itu hanya akan menjadi sakit di leher untuk mengalokasikan array yang lebih besar baru, copy semuanya berakhir, membebaskan array tua, dan kemudian bergerak tentang bisnis Anda. Atau lebih buruk, Anda mungkin mengalokasikan cara memori lebih dari yang sebenarnya Anda butuhkan, dan sehingga Anda akan memiliki yang sangat jarang penduduknya array, sehingga untuk berbicara. 

Jadi sebuah linked list memberikan Anda ini keuntungan dari dinamika dan fleksibilitas dengan sisipan dan penghapusan. Tapi tentunya harus ada harga yang harus dibayar. Bahkan, salah satu tema dieksplorasi pada kuis nol adalah beberapa trade-off kita lihat sejauh ini. Jadi apa harga yang harus dibayar atau downside dari linked list? Ya. 

AUDIENCE: Tidak ada akses random. 

DAVID Malan: Tidak ada akses random. Tapi siapa yang peduli? Akses acak tidak terdengar menarik. 

AUDIENCE: [tidak terdengar] DAVID Malan: Tepat. Jika Anda ingin memiliki a algorithm-- tertentu dan biarkan aku benar-benar mengusulkan pencarian biner khususnya, yang adalah salah satu kami telah digunakan cukup bit-- sebuah jika Anda tidak memiliki akses acak, Anda tidak bisa melakukan itu aritmatika sederhana menemukan seperti elemen tengah dan melompat tepat untuk itu. Anda malah harus mulai dari pertama elemen dan linear mencari dari kiri ke kanan jika Anda ingin menemukan tengah atau elemen lainnya. 

AUDIENCE: Mungkin membutuhkan lebih banyak memori. 

DAVID Malan: Membawa lebih banyak memori. Dimana adalah bahwa tambahan biaya datang dari dalam memori? 

AUDIENCE: [tidak terdengar] DAVID Malan: Tepat. Dalam hal ini di sini, kami memiliki daftar link untuk bilangan bulat, namun kami dua kali lipat jumlah memori kita perlu dengan juga menyimpan pointer ini. Sekarang kurang dari masalah besar karena struct Anda mendapatkan lebih besar dan Anda menyimpan bukan angka tapi mungkin seorang mahasiswa atau objek lain. Tetapi intinya pasti tetap. Dan sejumlah operasi pada daftar terkait dipanggil adalah O besar linear n--. Hal-hal seperti penyisipan atau pencarian atau penghapusan dalam kasus elemen kebetulan berada di bagian paling akhir daftar apakah itu diurutkan atau tidak. 

Kadang-kadang Anda mungkin beruntung dan di batas sehingga lebih rendah pada operasi ini mungkin juga menjadi waktu yang konstan jika Anda selalu melihat elemen pertama, misalnya. Tetapi pada akhirnya, kami berjanji untuk mencapai grail suci struktur data, atau beberapa daripadanya pendekatan, dengan cara konstanta waktu. Dapatkah kita menemukan elemen atau menambahkan elemen atau menghapus elemen dari daftar? Kita akan melihat cukup segera. Dan ternyata salah satu yang mekanisme kami akan mulai menggunakan hari ini, Penggunaan tahunan p set lima, sebenarnya cukup akrab. Misalnya, jika ini adalah a bunch buku ujian, masing-masing memiliki siswa pertama nama dan nama belakang di atasnya, dan saya menjemput mereka dari pada akhir ujian, dan mereka semua cantik banyak dalam urutan acak, dan kami ingin pergi tentang pemilahan ujian ini sehingga setelah dinilai itu hanya jauh lebih mudah dan lebih cepat untuk menyerahkan mereka kembali kepada siswa abjad. Apa yang akan naluri Anda menjadi untuk tumpukan ujian seperti ini? 

Nah, jika Anda seperti saya, Anda mungkin melihat bahwa ini adalah m, jadi aku akan semacam menempatkan ini dalam, jika ini adalah meja saya atau lantai mana Saya menyebarkan hal-hal out-- atau array saya really-- Aku mungkin menempatkan semua Ms di sana. Oh. Berikut ini adalah A. Jadi saya mungkin menempatkan Seperti di sini. Oh. Berikut A. lain aku akan untuk menempatkan bahwa di sini. Berikut Z. sebuah Berikut ini adalah M. lain Dan Aku mungkin mulai membuat tumpukan seperti ini. Dan kemudian mungkin aku akan pergi nanti dan semacam sangat nitpicky-ly semacam tumpukan individu. Tapi yang penting saya akan melihat pada masukan bahwa aku tangan dan saya akan membuat beberapa dihitung keputusan berdasarkan masukan itu. Jika dimulai dengan A, meletakkannya di sana. Jika dimulai dengan Z, meletakkannya di atas di sana, dan segala sesuatu di antaranya. 

Jadi ini adalah teknik yang umumnya dikenal sebagai hashing-- H-A-S-H-- yang umumnya berarti mengambil sebagai input dan menggunakan input tersebut untuk menghitung nilai, umumnya angka, dan bahwa nomor adalah indeks ke penyimpanan wadah, seperti array. Jadi dengan kata lain, saya mungkin memiliki Fungsi hash, seperti yang saya lakukan di kepalaku, bahwa jika saya melihat seseorang yang Nama yang dimulai dengan A, Aku akan memetakan bahwa ke nol di kepala saya. Dan jika saya melihat seseorang dengan Z, aku akan memetakan bahwa untuk 25 di kepala saya dan kemudian memasukkan ke dalam paling tumpukan terakhir. 

Sekarang, jika Anda berpikir tentang tidak otakku tapi program C, nomor apa bisa Anda andalkan untuk mencapai itu hasil yang sama? Dengan kata lain, jika Anda memiliki ASCII karakter A, bagaimana Anda menentukan apa ember untuk memasukkannya ke dalam? Anda mungkin tidak ingin memasukkannya ke dalam ember 65, yang akan seperti di sana tanpa alasan. Di mana Anda ingin menempatkan A dalam hal nilai ASCII nya? Di mana Anda ingin lakukan untuk ASCII Nilai untuk datang dengan lebih cerdas ember untuk memasukkannya ke dalam? 

AUDIENCE: Minus A. 

DAVID Malan: Ya. Jadi dikurangi A atau minus khusus 65 jika A. modal Atau 98 jika itu adalah huruf kecil a. Dan sehingga akan memungkinkan kita untuk, sangat sederhana dan sangat deret hitung, menempatkan sesuatu ke dalam ember seperti itu. Jadi ternyata kita benar-benar melakukan ini juga bahkan dengan kuis. 

Jadi, Anda mungkin ingat Anda dilingkari Anda Nama mengajar sesama pada penutup. Dan nama TF yang terorganisir ke kolom ini abjad, baik, percaya atau tidak, ketika semua 80 plus kami berkumpul malam itu untuk kelas, langkah terakhir dalam proses penilaian kami adalah untuk hash kuis menjadi besar ruang lantai di [tidak terdengar] dan untuk meletakkan kuis semua orang keluar persis urutan TF mereka nama pada cover, karena maka itu jauh lebih mudah bagi kita untuk mencari melalui bahwa menggunakan linear pencarian atau semacam kepandaian untuk TF untuk menemukan atau kuis siswanya. 

Jadi ini ide hashing yang akan Anda lihat adalah cukup kuat sebenarnya cukup biasa dan sangat intuitif, seperti mungkin membagi dan Mendatuk berada di minggu nol. Saya maju cepat untuk hackathon yang beberapa tahun yang lalu. Ini adalah Zamyla dan beberapa siswa staf ucapan lainnya ketika mereka datang. Dan kami memiliki sejumlah besar lipat tabel ada dengan tag nama. Dan kami telah tag nama terorganisir dengan seperti As di sana dan Zs di sana. Dan salah satu TF sangat cerdik menulis ini sebagai petunjuk untuk hari. Dan dalam minggu ke-12 semester ini semua masuk akal dan semua orang tahu apa yang harus dilakukan. Tapi kapan saja Anda sudah antri dengan cara yang sama, Anda menerapkan gagasan yang sama hash. Jadi mari kita memformalkan itu sedikit. Berikut adalah array. Ini diambil untuk menjadi sedikit lebar hanya untuk menggambarkan, secara visual, bahwa kita mungkin menempatkan string dalam hal seperti ini. Dan array ini adalah jelas dari ukuran total 26. Dan hal ini disebut tabel sewenang-wenang. Tapi ini hanya rendition artis apa tabel hash mungkin. 

Jadi tabel hash sekarang akan menjadi lebih tinggi struktur data tingkat. Pada akhir hari kita akan melihat bahwa Anda dapat menerapkan tabel hash, yang jauh seperti garis check-in pada hackathon seperti ini tabel yang digunakan untuk menyortir buku ujian. Tapi tabel hash adalah semacam tingkat tinggi ini Konsep yang bisa menggunakan array di bawah tenda untuk menerapkannya, atau bisa menggunakan daftar panjang, atau bahkan mungkin beberapa struktur data lainnya. Dan sekarang itu pengambilan theme-- beberapa dari bahan dasar seperti array dan bangunan ini memblokir sekarang dari daftar panjang dan melihat apa lagi yang bisa kita membangun di atas mereka, seperti bahan menjadi resep, membuat semakin banyak hasil akhir yang menarik dan berguna. 

Jadi dengan tabel hash kita mungkin menerapkannya dalam memori pictorially seperti ini, tapi bagaimana mungkin itu benar-benar dikodekan up? Yah, mungkin hanya sebagai adalah ini. Jika KAPASITAS di semua topi, hanya beberapa constant-- misalnya 26, untuk 26 surat alphabet-- yang Saya sebut meja variabel saya, dan aku mungkin mengklaim bahwa aku akan menempatkan bintang char dalam sana, atau tali. Jadi itu yang sederhana seperti ini jika Anda ingin menerapkan tabel hash. Namun, ini benar-benar hanya sebuah array. Tapi sekali lagi, hash tabel sekarang apa yang kita akan memanggil tipe data abstrak yang hanya semacam layering konseptual di atas sesuatu yang lebih biasa sekarang seperti sebuah array. 

Sekarang, bagaimana kita pergi tentang memecahkan masalah? Nah, sebelumnya aku punya kemewahan memiliki ruang meja yang cukup di sini sehingga saya bisa menempatkan kuis di mana saja yang saya inginkan. Jadi Seperti yang mungkin pergi di sini. Zs mungkin pergi di sini. Ms mungkin pergi di sini. Dan kemudian aku punya beberapa ruang tambahan. Tapi ini adalah sedikit dari hak contekan sekarang karena tabel ini, jika aku benar-benar menganggapnya sebagai sebuah array, hanya akan beberapa ukuran tetap. 

Jadi secara teknis, jika saya menarik up kuis lain siswa dan lihat, oh, orang ini namanya dimulai dengan A juga, Aku agak ingin menaruhnya di sana. Tapi begitu aku taruh di sana, jika tabel ini memang merupakan sebuah array, Aku akan meng-override atau clobbering siapa kuis ini siswa adalah. Benar? Jika ini adalah array, hanya satu hal dapat pergi di setiap sel-sel ini atau elemen. Dan jadi aku agak punya untuk memilih. 

Sekarang sebelumnya aku agak ditipu dan melakukan ini atau aku hanya jenis ditumpuk mereka di atas satu sama lain. Tapi itu tidak akan terbang dalam kode. Jadi di mana aku bisa meletakkan mahasiswa kedua yang namanya adalah A jika semua yang saya punya adalah ini tersedia ruang meja? Dan aku telah menggunakan tiga slot dan Sepertinya hanya ada beberapa orang lain. Apa yang bisa Anda lakukan? AUDIENCE: [tidak terdengar] DAVID Malan: Ya. Mungkin mari kita tetap sederhana. Benar? Ini tidak cocok di mana saya ingin menaruhnya. Jadi aku akan meletakkannya teknis di mana B akan pergi. Sekarang, tentu saja, aku mulai melukis diri ke sudut. Jika saya bisa mahasiswa yang namanya sebenarnya B, sekarang B akan dipindahkan sedikit maju, seperti yang mungkin terjadi, ya, jika ini adalah B, sekarang harus pergi di sini. 

Dan jadi ini sangat cepat bisa menjadi bermasalah, tapi teknik yang benar-benar disebut sebagai linear probing, dimana Anda hanya mempertimbangkan Anda array untuk menjadi sepanjang garis. Dan Anda hanya jenis menyelidiki atau memeriksa setiap elemen tersedia mencari tempat yang tersedia. Dan segera setelah Anda menemukan satu, Anda menaruhnya di sana. 

Sekarang, harga yang dibayar sekarang untuk solusi ini adalah apa? Kami memiliki ukuran array tetap, dan ketika saya menyisipkan nama ke dalamnya, paling tidak pada awalnya, apa waktu berjalan penyisipan untuk menempatkan siswa kuis di ember yang tepat? Big O apa? 

AUDIENCE: n. DAVID Malan: Aku mendengar O besar n. Tidak benar. Tapi kita akan menggoda terpisah mengapa hanya dalam beberapa saat. Apa lagi mungkin itu? 

AUDIENCE: [tidak terdengar] DAVID Malan: Dan biarkan aku melakukannya secara visual. Jadi kira ini adalah huruf S. 

AUDIENCE: Itu salah satu. DAVID Malan: Itu salah satu. Benar? Ini adalah array, yang berarti kita memiliki akses random. Dan jika kita berpikir tentang hal ini sebagai nol dan ini sebagai 25, dan kami menyadari bahwa, oh, inilah saya masukan S, Saya pasti dapat mengkonversi S, karakter ASCII, ke angka yang sesuai antara nol dan 25 dan kemudian segera meletakkannya di tempatnya. 

Tapi tentu saja, segera setelah saya sampai ke orang kedua yang memiliki nama adalah A atau B atau C akhirnya, jika saya telah menggunakan linear probing sebagai solusi saya, waktu berjalan dari penyisipan dalam kasus terburuk sebenarnya akan berpindah ke apa? Dan aku mendengarnya di sini benar sejak dini. AUDIENCE: [tidak terdengar] DAVID Malan: Jadi n memang sekali Anda memiliki satu set data yang cukup besar. Jadi, di satu sisi, jika array cukup besar dan data Anda jarang cukup, Anda mendapatkan ini waktu konstan yang indah. Tapi begitu Anda mulai semakin elemen, dan hanya statistik Anda mendapatkan lebih banyak orang dengan huruf A sebagai nama mereka atau huruf B, itu bisa berpotensi berpindah ke sesuatu yang lebih linier. Jadi tidak cukup sempurna. Jadi kita bisa berbuat lebih baik? 

Nah, apa yang kami solusi sebelumnya ketika kita ingin memiliki lebih dinamisme dari sesuatu seperti sebuah array diperbolehkan? AUDIENCE: [tidak terdengar] DAVID Malan: Apa yang kami memperkenalkan? Ya. Jadi sebuah linked list. Nah, mari kita lihat apa yang terkait daftar mungkin lakukan untuk kita sebagai gantinya. Nah, biarkan aku mengusulkan kita bahwa menggambar gambar sebagai berikut. Sekarang ini adalah berbeda gambar dari contoh dari teks yang berbeda, sebenarnya, bahwa sebenarnya menggunakan sebuah array dari ukuran 31. Dan penulis ini hanya memutuskan untuk hash string tidak didasarkan pada nama-nama orang tersebut, namun berdasarkan tanggal lahir mereka. Terlepas dari bulan, mereka pikir jika Anda lahir pada hari pertama dari bulan atau 31 bulan, penulis akan hash berdasarkan nilai tersebut, sehingga untuk menyebarkan nama-nama keluar sedikit lebih dari sekedar 26 spot mungkin mengizinkan. Dan mungkin itu adalah lebih seragam sedikit daripada pergi dengan huruf abjad, karena tentu saja mungkin ada lebih banyak orang di dunia dengan nama yang mulai dengan A daripada tentu beberapa surat lainnya dari alfabet. Jadi mungkin ini sedikit lebih seragam, dengan asumsi distribusi seragam bayi di bulan. 

Tapi, tentu saja, ini masih tidak sempurna. Benar? Kami mengalami tabrakan. Beberapa orang di ini struktur data masih memiliki tanggal lahir yang sama setidaknya Anda terlepas dari bulan. Tapi apa yang telah penulis lakukan? Yah, sepertinya kita memiliki sebuah array di sisi kiri ditarik secara vertikal, tapi itu hanya rendition seorang seniman. Tidak peduli apa arah Anda menggambar sebuah array, itu masih sebuah array. Apa ini sebuah array rupanya? 

AUDIENCE: Daftar Linked. 

DAVID Malan: Ya. Sepertinya itu adalah array linked list. Jadi sekali lagi, ke titik ini semacam menggunakan struktur data ini sekarang sebagai bahan untuk lebih solusi yang menarik, Anda benar-benar dapat mengambil mendasar, seperti sebuah array, dan kemudian mengambil sesuatu yang lebih menarik seperti linked list dan bahkan menggabungkan mereka ke dalam bahkan struktur data yang lebih menarik. Dan memang, ini juga akan disebut tabel hash, dimana array adalah benar-benar tabel hash, tapi itu tabel hash memiliki rantai, sehingga untuk berbicara, yang dapat tumbuh atau menyusut berdasarkan jumlah elemen yang ingin Anda masukkan. 

Sekarang, oleh karena itu, apa yang sekarang waktu berjalan? Jika saya ingin memasukkan seseorang yang berulang tahun tanggal 31 Oktober mana dia pergi? Baik. Di bagian paling bawah di mana dikatakan 31. Dan itu sempurna. Itu adalah waktu yang konstan. Tapi bagaimana kalau kita menemukan orang lain yang ulang tahun adalah, mari kita lihat, Oktober, November, Desember 31? Dimanakah dia akan pergi? Hal yang sama. Dua langkah sekalipun. Itu konstan meskipun bukan? Baik. Pada saat itu. Tetapi dalam kasus umum, semakin banyak orang kita tambahkan, probabilistically, kita akan untuk mendapatkan lebih banyak dan lebih banyak tabrakan. 

Sekarang ini sedikit lebih baik karena secara teknis sekarang rantai saya bisa di kasus terburuk berapa lama? Jika saya memasukkan n orang ke dalam ini lebih struktur data yang canggih, n orang, dalam kasus terburuk itu akan menjadi n. Mengapa? 

AUDIENCE: Karena jika semua orang memiliki ulang tahun yang sama, mereka akan menjadi satu baris. DAVID Malan: Perfect. Ini mungkin sedikit dibikin, tapi benar-benar dalam kasus terburuk, jika setiap orang memiliki ulang tahun yang sama, diberikan input yang Anda miliki, Anda akan memiliki rantai besar-besaran panjang. Dan, Anda bisa menyebutnya hash table, tapi benar-benar hanya linked list besar dengan seluruh banyak ruang kosong. Tapi secara umum, jika kita mengasumsikan bahwa setidaknya ulang tahun yang uniform-- dan mungkin tidak. Aku membuat bahwa sampai. Tetapi jika kita berasumsi, untuk kepentingan diskusi bahwa mereka, maka secara teori, jika ini adalah representasi vertikal dari array, baik maka mudah-mudahan Anda akan mendapatkan rantai yang, Anda tahu, panjang kurang lebih sama di mana masing-masing ini merupakan hari bulan. 

Sekarang jika ada 31 hari dalam sebulan, yang berarti waktu berjalan saya benar-benar adalah O besar n lebih dari 31, yang merasa lebih baik daripada linear. Tapi apa yang salah dari kami komitmen beberapa minggu lalu setiap kali datang untuk mengekspresikan waktu berjalan dari algoritma? Hanya saja melihat istilah urutan tinggi. Benar? 31 pasti membantu. Tapi ini masih O besar n. Tapi salah satu tema masalah set lima akan menjadi ke mengakui bahwa benar-benar, asimtotik, secara teoritis struktur data tidak lebih baik dari sekedar satu linked list besar. Dan memang, dalam kasus terburuk, ini tabel hash mungkin berpindah ke dalam. 

Tapi di dunia nyata, dengan kita manusia yang sendiri Mac atau PC atau apa pun dan menjalankan dunia nyata perangkat lunak data dunia nyata, yang algoritma yang akan Anda sukai? Salah satu yang mengambil langkah akhir atau salah satu yang memakan waktu n dibagi dengan 31 langkah untuk menemukan beberapa bagian dari data atau untuk mencari beberapa informasi? Maksudku, benar-benar 31 merek perbedaan di dunia nyata. Ini adalah 31 kali lebih cepat. Dan kita manusia pasti akan menghargai itu. 

Jadi menyadari dikotomi ada antara benar-benar berbicara tentang hal-hal yang secara teoritis dan asimtotik yang pasti memiliki nilai seperti yang kita lihat, tapi di dunia nyata, jika Anda peduli tentang hanya membuat senang manusia untuk input umum, Anda mungkin sangat baik ingin menerima fakta bahwa, ya, ini adalah linear, tapi itu 31 kali lebih cepat linear mungkin. Dan lebih baik lagi, kita tidak hanya harus melakukan sesuatu sewenang-wenang seperti tanggal lahir seorang, kita bisa menghabiskan sedikit lebih banyak waktu dan kepandaian dan berpikir tentang apa yang bisa kita lakukan, diberi nama seseorang dan mungkin tanggal lahir mereka untuk menggabungkan mereka bahan untuk mencari tahu sesuatu yang benar-benar lebih seragam dan kurang bergerigi, sehingga untuk berbicara daripada gambar ini saat ini menunjukkan mungkin. Bagaimana kita bisa menerapkan ini dalam kode? Nah, biarkan aku mengusulkan kita bahwa hanya meminjam beberapa sintaks kita sudah digunakan beberapa kali sejauh ini. Dan aku akan menentukan node, yang lagi-lagi adalah istilah umum untuk hanya beberapa wadah untuk beberapa struktur data. Aku akan mengusulkan bahwa string akan di sana. Tapi kita akan mulai mengambil mereka pelatihan roda off sekarang. 

Tidak ada lagi CS50 perpustakaan benar-benar, kecuali jika Anda ingin menggunakannya untuk akhir Anda Proyek, yang baik-baik saja, tapi sekarang kita akan menarik kembali tirai dan mengatakan itu hanya bintang arang. Jadi kata ada akan menjadi nama orang yang bersangkutan. Dan sekarang aku punya link di sini untuk node berikutnya sehingga ini mewakili masing-masing node dalam rantai, berpotensi, dari linked list. 

Dan sekarang bagaimana cara mendeklarasikan tabel hash itu sendiri? Bagaimana cara mendeklarasikan seluruh struktur ini? Nah, benar-benar, seperti saya menggunakan pointer hanya elemen pertama dari daftar sebelumnya, sama bisa saya katakan Aku hanya perlu sekelompok pointer untuk menerapkan tabel ini hash keseluruhan. Aku akan memiliki sebuah array disebut meja untuk tabel hash. Ini akan menjadi ukuran kapasitas. Itu berapa banyak elemen bisa muat di dalamnya. Dan masing-masing elemen dalam hal ini array akan menjadi bintang simpul. Mengapa? Nah, per gambar ini, apa yang saya menerapkan tabel hash sebagai efektif pada awalnya hanya array ini bahwa kita telah ditarik secara vertikal, masing-masing kotak yang merupakan pointer. Bahwa orang yang memiliki garis miring melalui mereka hanya nol. Dan orang-orang yang memiliki panah akan ke kanan pointer sebenarnya untuk node yang sebenarnya, ergo awal dari linked list. 

Jadi di sini, kemudian, adalah bagaimana kita mungkin menerapkan tabel hash yang mengimplementasikan chaining terpisah. Sekarang kita bisa berbuat lebih baik? Baiklah saya berjanji terakhir kali kita bisa mencapai waktu konstan. Dan aku agak memberi Anda waktu yang konstan di sini, tapi kemudian mengatakan tidak benar-benar konstanta waktu karena masih tergantung pada total jumlah elemen Anda memasukkan ke dalam struktur data. Tapi bagaimana kalau kita melakukan hal ini. Biarkan aku pergi kembali ke layar di sini. Saya juga memproyeksikan ini di sini, jelas layar, dan kira saya melakukan ini. Misalkan saya ingin memasukkan nama Daven di dalam struktur data saya. 

Jadi saya ingin menyisipkan string Daven ke dalam struktur data. Bagaimana jika saya tidak menggunakan hash table, tapi saya menggunakan sesuatu yang lebih seperti pohon seperti pohon keluarga, di mana Anda memiliki beberapa akar di node atas dan kemudian dan daun yang pergi ke bawah dan ke luar. Misalkan saat itu, bahwa saya ingin memasukkan Daven ini menjadi apa yang saat ini daftar kosong. Aku akan melakukan hal berikut: Aku akan membuat simpul di keluarga ini seperti pohon struktur data yang terlihat sedikit seperti ini, masing-masing persegi panjang telah, katakanlah, untuk saat ini 26 elemen di dalamnya. Dan masing-masing sel dalam array ini akan untuk mewakili huruf dari alfabet. 

Secara khusus, aku akan mengobati ini adalah A, maka B, maka C, maka D, satu ini di sini. Jadi ini akan efektif mewakili huruf D. Tetapi untuk memasukkan semua Daven ini nama saya perlu melakukan sedikit lebih. Jadi aku pertama akan hash, sehingga untuk berbicara. Aku akan melihat huruf pertama di Daven ini yang jelas D, dan aku akan mengalokasikan node yang terlihat seperti this-- persegi panjang besar besar cukup untuk memenuhi seluruh alfabet. 

Sekarang D dilakukan. Sekarang A. D-A-V-E-N adalah tujuan. Jadi sekarang apa yang akan saya lakukan adalah ini. Segera setelah saya mulai pemberitahuan D tidak ada pointer di sana. Ini nilai sampah saat ini, atau aku mungkin menginisialisasi ke null. Tapi biarkan aku terus berjalan dengan ide ini membangun pohon. Mari saya mengalokasikan salah satu dari ini node yang memiliki 26 elemen di dalamnya. 

Dan kau tahu apa? Jika ini hanyalah sebuah node dalam memori yang Saya buat dengan malloc, menggunakan struct karena kami akan segera melihat, Aku akan melakukan this-- Aku akan menggambar panah dari hal yang diwakili D turun untuk node baru ini. Dan sekarang, pertama berikutnya huruf di nama Daven ini, V-- D-A-V-- Aku akan pergi ke depan dan menarik node lain seperti ini, dimana, elemen V di sini, yang kami akan menarik untuk whoops instance--. Kami tidak akan menarik di sana. Itu akan pergi di sini. 

Maka kita akan menganggap hal ini menjadi V. Dan kemudian di sini kita akan indeks turun dari V ke dalam apa yang akan kita pertimbangkan E. Dan kemudian dari sini kita akan pergi memiliki satu node ini di sini. Dan sekarang kita memiliki pertanyaan untuk menjawab. Saya perlu entah bagaimana menunjukkan bahwa kita berada di akhir string Daven. Jadi saya hanya bisa meninggalkannya null. 

Tapi bagaimana jika kita memiliki Daven ini nama lengkap juga, yang adalah, seperti yang kita katakan, Davenport? Jadi bagaimana jika Daven adalah sebenarnya substring, awalan string lebih lama? Kita tidak bisa hanya secara permanen mengatakan apa-apa yang terjadi untuk pergi ke sana, karena kita bisa tidak pernah memasukkan kata seperti Davenport ke ini Struktur Data 

Jadi apa yang bisa kita lakukan sebagai gantinya adalah memperlakukan masing-masing elemen sebagai mungkin memiliki dua unsur dalam diri mereka. Salah satunya adalah pointer, memang, seperti yang telah saya lakukan. Jadi masing-masing kotak-kotak ini bukan hanya satu sel. Tapi bagaimana kalau atas satu-- bawah seseorang akan menjadi nol, karena tidak ada Davenport dulu. Bagaimana jika orang yang top beberapa nilai khusus? Dan itu akan menjadi sedikit sulit untuk menggambar ukuran ini. Tapi rasa itu hanya tanda centang. Periksa. D-A-V-E-N adalah string dalam struktur data. 

Sementara itu, jika saya memiliki lebih banyak ruang di sini, aku bisa melakukan P-O-R-T, dan saya bisa menempatkan cek di node yang memiliki huruf T di akhir. Jadi ini adalah besar-besaran Kompleks tampak struktur data. Dan tulisan tangan saya tentu tidak membantu. Tapi jika saya ingin memasukkan sesuatu lain, pertimbangkan apa yang akan kita lakukan. Jika kita ingin menempatkan David in, kami akan mengikuti logika yang sama, D-A-V, tapi sekarang saya akan menunjukkan di depan elemen tidak dari E, tapi dari saya ke D. Jadi ada akan menjadi node lainnya di pohon ini. Kita akan memiliki panggilan malloc lagi. Tapi aku tidak ingin membuat berantakan lengkap gambar ini. Jadi mari kita malah melihat salah satu yang telah pra-dirumuskan seperti ini dengan tidak dot, dot, titik, tapi array hanya disingkat. Tetapi masing-masing dari node di pohon ini di sini mewakili thing-- sama array Ray ukuran 26. 

Atau jika kita ingin menjadi benar-benar tepat sekarang, apa jika nama seseorang sebagai apostrof, mari kita mengasumsikan bahwa setiap node sebenarnya memiliki seperti 27 indeks di dalamnya, bukan hanya 26. Jadi sekarang ini akan menjadi data struktur disebut trie-- T-R-I-E. Sebuah trie, yang diduga historis nama pintar untuk pohon yang dioptimalkan untuk pengambilan, yang tentu saja, dieja dengan I-E sehingga trie. Tapi itu adalah sejarah trie. 

Jadi trie data seperti pohon ini struktur seperti pohon keluarga yang pada akhirnya berperilaku seperti itu. Dan di sini hanyalah contoh lain dari Seluruh sekelompok nama orang lain. Tetapi pertanyaan sekarang di tangan adalah apa yang harus kami memperoleh dengan memperkenalkan dibilang lebih struktur data yang rumit, dan satu, terus terang, yang menggunakan banyak memori. 

Karena meskipun, pada saat ini, aku hanya menggunakan D's pointer dan A dan V dan Es dan Ns, Aku membuang-buang heck of banyak memori. Tapi di mana saya menghabiskan satu sumber daya, Saya cenderung untuk melakukan mendapatkan kembali lain. Jadi jika saya menghabiskan lebih banyak ruang, apa mungkin harapan? Bahwa aku menghabiskan kurang apa? AUDIENCE: Kurang waktu. DAVID Malan: Time. Sekarang mengapa mungkin itu? Nah, apa penyisipan waktu, dalam hal O besar sekarang, dari nama seperti Daven atau Davenport atau David? Nah, Daven adalah lima langkah. Davenport akan sembilan langkah, sehingga akan langkah beberapa lagi. David akan menjadi lima langkah juga. Jadi mereka adalah beton angka, tapi pasti ada atas terikat pada panjang nama seseorang. Dan memang, dalam masalah set lima spesifikasi, kita akan mengusulkan bahwa itu sesuatu itulah karakter 40-beberapa-aneh. 

Realistis, tidak ada yang memiliki nama panjang tak terhingga, yang berarti bahwa panjang dari nama atau panjang string kita mungkin memiliki beberapa keadaan Struktur ini bisa dibilang apa? Ini konstan. Benar? Mungkin konstan besar seperti 40-sesuatu, tapi itu adalah konstan. Dan tidak memiliki ketergantungan pada berapa banyak Nama-nama lain dalam struktur data. Dengan kata lain, jika saya ingin sekarang memasukkan Colton atau Gabriel atau Rob atau Zamyla atau Alison atau Belinda atau nama lain dari staf menjadi data ini struktur, adalah waktu yang berjalan memasukkan nama lain akan sama sekali terkena dampak oleh berapa banyak elemen lain yang dalam struktur data yang telah? Hal ini tidak. Benar? Karena kita secara efektif menggunakan tabel hash multi-layer. Dan waktu berjalan dari salah satu operasi ini tergantung bukan pada jumlah elemen yang berada di struktur data atau yang pada akhirnya akan berada di struktur data, tetapi pada panjang apa yang secara khusus? 

String yang dimasukkan, yang tidak membuat ini asimtotik konstan time-- O besar satu. Dan terus terang, hanya dalam dunia nyata, ini berarti memasukkan nama Daven ini membawa seperti lima langkah, atau Davenport sembilan langkah, atau David lima langkah. Itu pretty darn kali berjalan kecil. Dan, memang, itu sangat hal yang baik, terutama ketika itu tidak tergantung pada total jumlah elemen dalam sana. Jadi bagaimana mungkin kita menerapkan ini jenis struktur dalam kode? Ini sedikit lebih kompleks, tapi tetap saja hanya aplikasi blok bangunan dasar. Aku akan mendefinisikan kembali kita simpul sebagai berikut: bool disebut word-- dan ini bisa disebut apa-apa. Tapi bool merupakan apa yang saya menarik sebagai tanda centang. Ya. Ini adalah akhir dari string dalam struktur data. 

Dan, tentu saja, bintang simpul ada adalah mengacu pada anak-anak. Dan, memang, sama seperti pohon keluarga, Anda akan mempertimbangkan node yang menggantung dari bagian bawah beberapa orangtua elemen untuk menjadi anak-anak. Dan anak-anak akan menjadi sebuah array dari 27, yang 27 hanya menjadi untuk tanda kutip. Kita akan memilah kasus khusus yang. Sehingga Anda dapat memiliki tertentu nama dengan apostrof. Mungkin bahkan tanda hubung harus masuk ke sana, tapi Anda akan lihat dalam p set 5 kita hanya perawatan tentang surat dan apostrof. 

Dan kemudian bagaimana Anda mewakili struktur data itu sendiri? Bagaimana Anda mewakili akar dari trie ini, sehingga untuk berbicara? Nah, sama seperti dengan linked list, Anda membutuhkan pointer ke elemen pertama. Dengan trie Anda hanya perlu satu pointer ke akar trie ini. Dan dari sana Anda dapat hash jalan turun lebih dalam dan lebih ke setiap node lain dalam struktur. Jadi hanya dengan kaleng ini kami mewakili struct itu. 

Sekarang Meanwhile-- Oh, pertanyaan. 

AUDIENCE: Apa kata bool? 

DAVID Malan: Kata Bool adalah hanya inkarnasi C ini dari apa yang saya jelaskan dalam kotak ini di sini, ketika Aku mulai membelah masing-masing elemen array menjadi dua bagian. Salah satunya adalah pointer ke node berikutnya. Yang lain harus sesuatu seperti kotak centang untuk mengatakan ya, ada kata Daven yang berakhir di sini, karena kita tidak ingin, pada saat, Dave. 

Meskipun Dave akan menjadi Kata yang sah, dia tidak dalam trie Belum. Dan D tidak sepatah kata pun. Dan D-A bukanlah sebuah kata atau nama. Jadi tanda centang menunjukkan hanya sekali Anda memukul node ini adalah jalur sebelumnya karakter sebenarnya string yang telah Anda masukkan. Jadi itu semua bool ada lakukan untuk kita. 

Pertanyaan lain pada mencoba? Ya. 

AUDIENCE: Apa tumpang tindih? Bagaimana jika Anda memiliki Dave dan Daven? DAVID Malan: Perfect. Bagaimana jika Anda memiliki Dave dan Daven? Jadi jika kita memasukkan, mengatakan nama panggilan, untuk David-- Dave-- D-A-V-E? Ini sebenarnya super sederhana. Jadi kita hanya akan mengambil empat langkah. D-A V-E. Dan apa yang harus saya lakukan setelah aku memukul simpul keempat? Hanya akan memeriksa. Kita sudah baik untuk pergi. Selesai. Empat langkah. Konstanta waktu asimtotik. Dan sekarang kita sudah menunjukkan bahwa kedua Dave dan Daven adalah string dalam struktur. Jadi tidak masalah. Dan perhatikan bagaimana kehadiran dari Daven tidak berhasil mengambil lebih banyak waktu atau kurang waktu untuk Dave dan sebaliknya. 

Jadi apa lagi yang bisa kita lakukan sekarang? Kami telah menggunakan metafora ini sebelum nampan yang mewakili sesuatu. Tapi ternyata bahwa tumpukan nampan sebenarnya demonstratif data abstrak lain type-- lebih tinggi struktur data tingkat bahwa pada akhir hari hanya seperti array atau linked list atau sesuatu yang lebih biasa. Tapi itu lebih menarik Konsep konseptual. Sebuah stack, seperti ini baki sini di Mather, umumnya disebut hanya itu-- stack. 

Dan dalam jenis struktur data Anda memiliki dua operations-- Anda memiliki satu disebut dorongan untuk menambahkan sesuatu ke stack, seperti meletakkan baki lainnya kembali di atas tumpukan. Dan kemudian pop, yang berarti Anda mengambil baki off paling atas. Tapi apa kunci tentang stack adalah bahwa itu punya karakteristik penasaran ini. Sebagai staf ruang makan yang menata ulang baki untuk makan berikutnya, apa yang akan menjadi benar tentang bagaimana siswa berinteraksi dengan struktur data? AUDIENCE: Mereka akan pop satu. DAVID Malan: Mereka akan pop satu dari, mudah-mudahan atas. Jika itu hanya agak bodoh untuk pergi semua jalan ke bawah. Benar? Struktur data tidak benar-benar memungkinkan Anda untuk mengambil baki bawah setidaknya mudah. Jadi ada ini penasaran properti untuk stack bahwa item terakhir dalam adalah akan menjadi yang pertama keluar. Dan ilmuwan komputer panggilan ini LIFO-- bertahan, keluar pertama. Dan itu benar-benar tidak memiliki aplikasi menarik. Ini tidak selalu sejelas beberapa lain, tetapi bisa, memang, berguna, dan dapat, memang, dilaksanakan dalam beberapa cara yang berbeda. 

Jadi satu, dan benar-benar, biarkan saya untuk tidak menyelam ke dalam. Mari kita lakukan ini sebagai gantinya. Mari kita lihat satu yang hampir ide yang sama, tapi itu lebih adil sedikit. Benar? Jika Anda salah satu dari penggemar anak-anak ini atau gadis-gadis yang benar-benar menyukai produk Apple dan Anda bangun pukul 03:00 untuk berbaris di beberapa toko untuk mendapatkan iPhone sangat terbaru, Anda mungkin antri seperti ini. 

Sekarang antrian sangat sengaja bernama. Ini garis karena ada beberapa keadilan untuk itu. Benar? Ini akan mengisap jenis jika Anda sudah sampai di sana pertama di Apple Store tetapi Anda efektif yang terendah yang nampan karena Karyawan Apple kemudian pop orang terakhir yang benar-benar mendapat sejalan. Jadi tumpukan dan antrian, meskipun fungsional mereka agak same-- yang itu hanya koleksi ini sumber daya yang akan tumbuh dan shrink-- ada yang Aspek keadilan ini untuk itu, setidaknya di dunia nyata, di mana operasi Anda berolahraga pada dasarnya berbeda. Sebuah stack-- antrian rather-- dikatakan memiliki dua operasi: n antrian dan d antrian. Atau Anda dapat memanggil mereka banyak hal. Tapi Anda hanya ingin menangkap gagasan bahwa seseorang menambahkan dan satu pada akhirnya mengurangi. 

Sekarang di bawah kap mesin, baik stack dan antrian dapat diterapkan bagaimana? Kami tidak akan masuk ke kode itu karena tingkat yang lebih tinggi Ide adalah semacam lebih jelas. Maksudku, apa yang manusia lakukan? Jika aku orang pertama di Apple Menyimpan dan ini adalah pintu depan, Anda tahu, aku akan berdiri di sini. Dan orang berikutnya akan berdiri di sini. Dan orang berikutnya akan berdiri di sini. Jadi apa struktur data cocok untuk antrian? 

AUDIENCE: antrian A. DAVID Malan: Yah, antrian. Tentu. Apa lagi? 

AUDIENCE: Sebuah linked list. 

DAVID Malan: A terkait daftar Anda bisa menerapkan. Dan daftar link bagus karena kemudian itu dapat tumbuh sewenang-wenang panjang sebagai lawan untuk memiliki beberapa nomor tetap orang di toko. Tapi mungkin sejumlah tetap tempat yang sah. Karena jika mereka hanya memiliki seperti 20 iPhone pada hari pertama, mungkin mereka hanya perlu sebuah array dari ukuran 20 untuk mewakili bahwa antrian, yang hanya untuk mengatakan sekarang setelah kami mulai berbicara tentang masalah-masalah tingkat yang lebih tinggi, Anda dapat menerapkannya dalam berbagai cara. Dan ada mungkin hanya akan menjadi trade off dalam ruang dan waktu atau hanya dalam kompleksitas kode Anda sendiri. 

Bagaimana dengan stack? Nah, stack, kita telah melihat terlalu bisa saja nampan ini. Dan Anda bisa menerapkan ini array. Tapi di beberapa titik jika Anda menggunakan sebuah array, apa yang akan terjadi pada nampan Anda mencoba untuk meletakkan? Baik. Anda hanya akan bisa pergi begitu tinggi. Dan saya pikir di Mather mereka sebenarnya tersembunyi dalam membuka itu. Jadi memang, hampir seperti Mather menggunakan array ukuran tetap, karena Anda hanya bisa cocok begitu banyak nampan dalam pembukaan di dinding bawah lutut orang. Dan sehingga mungkin dikatakan array, tapi kita pasti bisa menerapkan bahwa lebih umum dengan linked list. 

Nah, bagaimana dengan struktur data lain? Biarkan aku menarik yang lain visual yang di sini. Sesuatu seperti bagaimana satu ini di sini? Mengapa itu berguna untuk memiliki tidak sesuatu yang mewah sebagai trie, yang kami melihat memiliki ini node yang sangat luas, masing-masing adalah dalam array? Tapi bagaimana kalau kita melakukan sesuatu yang lebih sederhana, seperti pohon keluarga sekolah tua, masing-masing yang node di sini hanya menyimpan nomor. Alih-alih nama atau keturunan sebuah hanya menyimpan nomor seperti ini. 

Nah, jargon yang kami gunakan dalam struktur data adalah baik mencoba dan pohon-pohon, di mana trie, sekali lagi, adalah hanya satu yang node array, masih apa yang Anda mungkin gunakan dari sekolah dasar ketika Anda membuat sebuah keluarga daun tree-- dan akar pohon dan anak-anak dari orang tua dan saudara kandung tersebut. Dan kita mungkin menerapkan pohon, misalnya, sesederhana ini. Sebuah pohon, jika sebagai node, salah satu kalangan ini yang memiliki nomor, itu tidak akan memiliki satu pointer, tapi dua. Dan segera setelah Anda menambahkan pointer kedua, Anda benar-benar dapat sekarang membuat semacam data dua dimensi struktur dalam memori. Sama seperti dua dimensi array, Anda dapat memiliki jenis dua dimensi daftar terhubung tapi yang yang mengikuti pola di mana tidak ada siklus. Ini benar-benar sebuah pohon dengan satu cara nenek di sini dan kemudian beberapa orang tua dan anak-anak dan cucu dan cicit. dan lain sebagainya. 

Tapi apa benar-benar rapi tentang ini juga, hanya untuk menggoda Anda dengan sedikit kode, ingat rekursi dari beberapa waktu yang lalu, dimana Anda menulis fungsi yang memanggil dirinya sendiri. Ini adalah kesempatan yang indah untuk melaksanakan sesuatu seperti rekursi, karena menganggap ini. 

Ini adalah pohon. Dan aku sudah anal kecil dengan cara Aku meletakkan bilangan bulat ke jalan. Begitu banyak sehingga ia memiliki khusus name-- pohon pencarian biner. Sekarang kita telah mendengar tentang biner pencarian, tapi Anda juga bisa bekerja mundur dari nama hal ini? Bagaimana pola dari bagaimana saya memasukkan bilangan bulat ke pohon ini? Hal ini tidak sewenang-wenang. Ada beberapa pola. Ya. 

AUDIENCE: yang lebih kecil di sebelah kiri. 

DAVID Malan: Ya. Yang lebih kecil berada di sebelah kiri. Yang lebih besar berada di sebelah kanan. Sehingga pernyataan yang benar adalah orang tua lebih besar dari anak kiri, tetapi kurang dari anak kanan. Dan itu saja bahkan definisi lisan rekursif karena Anda dapat menerapkan bahwa Logika yang sama ke setiap node dan hanya pantat out, kasus dasar jika Anda akan, ketika anda menekan salah satu daun, sehingga untuk berbicara, di mana cuti tidak memiliki anak lagi. 

Sekarang bagaimana mungkin Anda menemukan nomor 44? Anda akan mulai pada akar dan berkata, hm. 55 tidak 44 Jadi apakah saya ingin pergi benar atau apakah saya ingin ke kiri? Yah, jelas Anda ingin pergi kiri. Dan itu hanya seperti telepon contoh buku dalam pencarian biner lebih umum. Tapi kita mengimplementasikannya sekarang sedikit lebih dinamis dari array mungkin mengizinkan. Dan pada kenyataannya, jika Anda ingin terlihat kode tersebut, sekilas yakin. Sepertinya sejumlah besar baris. Tapi itu indah sederhana. Jika Anda ingin menerapkan fungsi disebut pencarian yang tujuannya dalam hidup adalah untuk mencari nilai seperti n, integer, dan Anda lulus dalam satu pointer-- pointer ke node akar, bukan, pohon itu dari mana Anda dapat mengakses segala sesuatu yang lain, perhatikan bagaimana tedeng aling-aling Anda dapat menerapkan logika. Jika pohon null, jelas itu tidak ada di sana. Mari kita kembali palsu. Benar? Jika Anda menyerahkannya apa-apa, tidak ada ada. 

Lain, jika n kurang dari pohon panah n-- sekarang panah n, ingat kami memperkenalkan Super singkat hari lain, dan itu hanya berarti de-referensi pointer dan melihat lapangan yang disebut n. Jadi itu berarti pergi ke sana dan melihat lapangan yang disebut n. Jadi jika n, nilai Anda diberi, kurang dari nilai di pohon-pohon integer, di mana Anda ingin pergi? Ke kiri. 

Jadi melihat rekursi. Aku returning-- tidak benar. Tidak salah. Aku kembali apa pun jawabannya adalah dari panggilan untuk diriku sendiri, melewati n lagi, yang berlebihan, tapi apa yang sedikit berbeda sekarang? Bagaimana aku membuat masalah yang lebih kecil? Aku lewat di sebagai yang kedua argumen, bukan akar pohon, tapi anak kiri dalam kasus ini. Jadi aku lewat di anak kiri. 

Sementara itu, jika n lebih besar dari node Saat ini saya melihat, Saya mencari sisi kanan. Lain, jika pohon tidak null, dan jika elemen tidak ke kiri dan itu tidak ke kanan, apa yang biasa terjadi? Kami telah benar-benar menemukan node di pertanyaan, dan jadi kami kembali benar. 

Jadi kami baru saja menggaruk permukaan sekarang beberapa struktur data tersebut. Dalam permasalahan yang lima Anda akan mengeksplorasi ini belum lebih lanjut, dan Anda akan diberi desain Anda pilihan tentang bagaimana untuk pergi tentang ini. Apa yang saya ingin menyimpulkan tentang hanya teaser 30 detik dari apa yang menanti minggu depan dan seterusnya. 

Seperti yang kita begin-- untungnya Anda mungkin think-- transisi kita perlahan-lahan dari dunia C dan rendah Rincian pelaksanaan tingkat, untuk sebuah dunia di mana kita dapat mengambil untuk saja bahwa orang lain memiliki akhirnya diimplementasikan data ini struktur bagi kita, dan kami akan mulai memahami dunia nyata berarti pelaksanaan program berbasis web dan website lebih umum dan juga sangat keamanan implikasi yang kita baru mulai menggores permukaan. Berikut adalah apa yang menanti kita di masa yang akan datang. 

[VIDEO PLAYBACK] 

-Dia Datang dengan pesan, dengan protokol semua sendiri. Dia datang ke dunia yang kejam firewall, router tidak peduli, dan bahaya yang jauh lebih buruk daripada kematian. Dia cepat. Dia kuat. Dia TCP / IP, dan dia punya alamat Anda. "Warriors of the Net." [END VIDEO PLAYBACK] DAVID Malan: Segera minggu depan. Kami akan melihat Anda kemudian. [VIDEO PLAYBACK] -Dan Sekarang, "Deep Thoughts" oleh Daven Farnham. -David Selalu dimulai kuliah dengan, "Baiklah." Mengapa tidak, "Inilah solusinya untuk minggu ini masalah set " atau "Kami memberikan anda semua A?" [Tertawa] [END VIDEO PLAYBACK]