[Powered by Google Translate] [Perduaan Search] [Patrick Schmid - Universiti Harvard] [Ini adalah CS50. - CS50.TV] 

Jika saya berikan anda satu senarai nama-nama watak Disney dalam susunan abjad dan meminta anda untuk mencari Mickey Mouse, bagaimana anda akan pergi tentang melakukan perkara ini? Salah satu cara yang jelas akan mengimbas senarai dari awal dan memeriksa setiap nama untuk melihat jika ia adalah Mickey. Tetapi kerana anda membaca Aladdin, Alice, Ariel, dan sebagainya, anda dengan cepat akan menyedari bahawa bermula di hadapan senarai tidak adalah idea yang baik. Okay, mungkin anda perlu mula bekerja ke belakang dari akhir senarai. Sekarang anda membaca Tarzan, Jahit, Snow White, dan sebagainya. Namun, ini tidak kelihatan seperti cara terbaik untuk pergi mengenainya. 

Nah, satu lagi cara yang anda boleh pergi tentang melakukan ini adalah untuk cuba untuk mengecilkan senarai nama-nama yang anda perlu melihat. Sejak anda tahu bahawa mereka berada dalam susunan abjad, anda hanya boleh melihat nama-nama di tengah-tengah senarai dan memeriksa jika Mickey Mouse adalah sebelum atau selepas nama ini. Melihat nama terakhir di dalam lajur kedua anda akan menyedari bahawa M untuk Mickey datang selepas J untuk Jasmine, jadi anda hanya akan mengabaikan separuh pertama senarai. Kemudian anda mungkin akan melihat bahagian atas lajur terakhir dan melihat bahawa ia bermula dengan Rapunzel. Mickey datang sebelum Rapunzel; kelihatan seperti kita boleh mengabaikan lajur terakhir serta. Meneruskan strategi carian, anda dengan cepat akan melihat bahawa Mickey pada separuh pertama senarai nama baki dan akhirnya mendapati Mickey bersembunyi antara Merlin dan Minnie. 

Apa yang anda hanya lakukan adalah carian pada dasarnya binari. Seperti nama ini membayangkan, ia melaksanakan strategi mencari dalam perkara binari. Apa maknanya? Nah, diberi senarai barangan disusun, algoritma carian binari membuat keputusan binari - kiri atau kanan, lebih besar daripada atau kurang daripada, abjad sebelum atau selepas - pada setiap titik. Sekarang bahawa kita mempunyai nama yang pergi bersama-sama dengan algoritma carian ini, mari kita melihat contoh yang lain, tetapi kali ini dengan senarai nombor yang disusun. Katakanlah kami sedang mencari bilangan 144 dalam senarai ini nombor yang disusun. Sama seperti sebelum ini, kita dapati bilangan yang di tengah-tengah - yang dalam kes ini ialah 13 - dan lihat jika 144 adalah lebih besar atau kurang daripada 13. Sejak ia adalah jelas lebih besar daripada 13, kita boleh mengabaikan bahawa segala-galanya adalah 13 atau kurang dan hanya menumpukan perhatian pada separuh baki. Sejak kita kini mempunyai nombor genap item kiri, kita hanya memilih beberapa yang terletak berhampiran ke tengah. Dalam kes ini kita memilih 55. Kita boleh hanya sebagai mudah dipilih 89. Okay. Sekali lagi, 144 adalah lebih daripada 55 tahun, jadi kita pergi ke kanan. Nasib baik untuk kita, bilangan pertengahan seterusnya adalah 144, satu yang kita cari. Jadi untuk mencari 144 menggunakan carian binari, kita dapat mencari ia dalam hanya 3 langkah. Jika kita akan menggunakan carian linear di sini, ia akan kami mengambil 12 langkah. Sebagai hakikatnya, sejak kaedah ini carian bahagian bilangan item ia mempunyai melihat pada setiap langkah, ia akan mencari item yang ia mencari dalam kira-kira log bilangan item dalam senarai. Sekarang kita telah melihat 2 contoh, mari kita lihat pada beberapa pseudokod untuk fungsi rekursi yang melaksanakan gelintaran perduaan. Bermula di bahagian atas, kita melihat bahawa kita perlu untuk mencari fungsi yang mengambil masa 4 hujah: utama, tatasusunan, min, dan maks. Utama adalah nombor yang kita cari, jadi 144 dalam contoh sebelumnya. Tatasusunan adalah senarai nombor yang kita sedang mencari. Min dan max adalah indeks kedudukan minimum dan maksimum bahawa kita sedang melihat. Jadi apabila kita mula, min akan menjadi sifar dan maks akan menjadi indeks maksimum array. Seperti yang kita menyempitkan carian bawah, kami akan mengemaskini min dan maks untuk menjadi hanya pelbagai bahawa kita masih mencari masuk 

Mari kita melangkau ke bahagian yang menarik pertama. Perkara pertama yang kami lakukan ialah mencari titik tengah, indeks yang di tengah-tengah antara min dan maks pelbagai bahawa kita masih mengingati. Kemudian kita melihat nilai array di lokasi titik tengah itu dan melihat jika nombor yang kita cari adalah kurang daripada utama yang. Jika nombor pada kedudukan itu adalah kurang, maka ia bermakna utama adalah lebih besar daripada semua nombor ke kiri jawatan itu. Jadi, kita boleh memanggil fungsi carian binari lagi, tetapi kali ini mengemaskini parameter min dan max untuk membaca hanya separuh yang lebih besar daripada atau sama dengan nilai kita hanya melihat. Sebaliknya, jika kunci kurang daripada bilangan pada titik tengah semasa array, kita mahu pergi ke kiri dan mengabaikan semua nombor yang lebih besar. Sekali lagi, kita panggil carian binari tetapi kali ini dengan julat min dan maks dikemaskini untuk memasukkan hanya separuh lebih rendah. Jika nilai pada titik semasa dalam pelbagai adalah tidak lebih besar daripada mahupun yang lebih kecil daripada kunci, maka ia mesti sama dengan kunci. Oleh itu, kita hanya boleh mengembalikan indeks titik tengah semasa, dan kami sudah selesai. Akhirnya, ini cek di sini adalah untuk kes itu bahawa nombor tidak sebenarnya dalam pelbagai nombor yang kita sedang mencari. Jika indeks maksimum julat yang kita cari pernah kurang daripada minimum, yang bermakna bahawa kita telah pergi terlalu jauh. Sejak nombor tidak dalam pelbagai input, kita kembali -1 untuk menunjukkan apa-apa yang telah dijumpai. 

Anda mungkin perasan bahawa bagi algoritma ini untuk bekerja, mempunyai senarai nombor yang perlu diselesaikan. Dalam erti kata lain, kita hanya boleh mencari 144 menggunakan gelintaran perduaan jika semua nombor disusun dari terendah kepada tertinggi. Jika ini tidak berlaku, kita tidak akan dapat mengecualikan separuh daripada nombor pada setiap langkah. Jadi kita mempunyai 2 pilihan. Sama ada kita boleh mengambil senarai Unsorted dan menyusun ia sebelum menggunakan gelintaran perduaan, atau kita boleh memastikan bahawa senarai nombor yang disusun seperti yang kita menambah nombor. Oleh itu, bukannya sorting hanya apabila kita perlu mencari, mengapa tidak menyimpan senarai yang disusun pada setiap masa? 

Salah satu cara untuk menyimpan senarai nombor disusun pada masa yang sama membenarkan seseorang untuk menambah atau memindahkan nombor dari senarai ini adalah dengan menggunakan sesuatu yang dipanggil pokok carian binari. Satu pokok carian binari adalah satu struktur data yang mempunyai 3 sifat. Pertama, pohon kiri mana-mana nod mengandungi nilai sahaja yang kurang daripada atau sama dengan nilai nod. Kedua, hak pohon nod hanya mengandungi nilai-nilai yang lebih besar daripada atau sama dengan nilai nod. Dan, akhirnya, kedua-dua subtrees kiri dan kanan semua nod juga pohon-pohon carian dedua. Mari kita melihat contoh dengan nombor yang sama kita digunakan lebih awal. Bagi anda yang tidak pernah melihat pokok sains komputer sebelum, biarlah saya mulakan dengan memberitahu anda bahawa pokok sains komputer tumbuh ke bawah. Ya, tidak seperti pokok yang anda biasa, akar pokok sains komputer adalah di bahagian atas, dan daun di bahagian bawah. Setiap kotak kecil dipanggil nod, dan nod disambungkan antara satu sama lain oleh tepi. Jadi akar pokok ini adalah nilai nod dengan nilai 13, yang mempunyai nod 2 kanak-kanak dengan nilai 5 dan 34. Sebuah pohon adalah pokok yang dibentuk hanya dengan melihat pada subseksyen keseluruhan pokok. 

Sebagai contoh, anak pohon kiri nod 3 adalah pokok yang dicipta oleh nod 0, 1, dan 2. Jadi, jika kita kembali kepada sifat-sifat pokok carian binari, kita lihat bahawa setiap nod dalam pokok itu mematuhi semua 3 harta, iaitu, anak pohon kiri sahaja mengandungi nilai-nilai yang kurang daripada atau sama dengan nilai nod; hak pohon semua nod hanya mengandungi nilai-nilai yang lebih besar daripada atau sama dengan nilai nod; kedua-dua kiri dan kanan subtrees semua nod juga adalah pokok gelintaran perduaan. Walaupun pokok ini kelihatan berbeza, ini adalah pokok carian binari sah bagi set nombor yang sama. Sebagai hakikatnya, terdapat banyak cara yang mungkin bahawa anda boleh membuat pokok carian binari yang sah daripada nombor-nombor ini. Nah, mari kita kembali ke satu yang pertama kita dicipta. Jadi apa yang kita boleh lakukan dengan pokok-pokok? Nah, kita hanya boleh mencari nilai minimum dan maksimum. Nilai minimum boleh didapati dengan sentiasa pergi ke kiri sehingga terdapat tidak lebih nod untuk melawat. Sebaliknya, untuk mencari satu maksimum hanya sekadar pergi ke kanan pada setiap kali. 

Mencari mana-mana nombor lain yang tidak adalah minimum atau maksimum hanya sebagai mudah. Katakanlah kita sedang mencari nombor 89. Kami hanya memeriksa nilai setiap nod dan pergi ke kiri atau kanan, bergantung kepada sama ada nilai nod adalah kurang daripada atau lebih daripada satu yang kita cari. Jadi, bermula pada akar 13 tahun, kita melihat bahawa 89 adalah lebih besar, dan sebagainya kita pergi ke kanan. Kemudian kita lihat nod selama 34, dan sekali lagi kita pergi ke kanan. 89 berada masih lebih besar daripada 55 tahun, jadi kami terus pergi ke kanan. Kami kemudian tampil dengan nod dengan nilai sebanyak 144 dan pergi ke kiri. Lo dan tiba-tiba, 89 adalah di sana. 

Satu lagi perkara yang boleh kita lakukan adalah mencetak semua nombor dengan melaksanakan satu inorder traversal. Satu inorder traversal bermakna untuk mencetak segala-galanya dalam anak pohon kiri diikuti oleh percetakan nod sendiri dan kemudian diikuti oleh mencetak semua keluar dalam hak anak pohon. Sebagai contoh, mari kita pokok carian binari kegemaran kami dan mencetak nombor dalam perintah disusun. Kami bermula pada akar 13 tahun, tetapi sebelum 13 percetakan kita perlu untuk mencetak keluar segala-galanya dalam anak pohon yang kiri. Jadi kita pergi ke 5. Kita masih perlu pergi lebih jauh ke dalam pokok itu sehingga kita dapati nod paling kiri, yang adalah sifar. Selepas percetakan sifar, kita kembali sehingga kepada 1 dan mencetak yang keluar. Kemudian kita pergi ke anak pohon yang betul, yang merupakan 2, dan mencetak yang keluar. Sekarang kita sedang dilakukan dengan pohon, kita boleh kembali sehingga ke 3 dan mencetak keluar. Meneruskan sandaran, kita mencetak 5 dan kemudian 8. Sekarang kita telah selesai keseluruhan meninggalkan pohon, kita boleh mencetak out 13 dan mula bekerja di sebelah kanan pohon. Kami hop ke 34, tetapi sebelum 34 percetakan kita mempunyai untuk mencetak pohon kiri. Jadi kita mencetak 21; maka kita akan mendapat untuk mencetak 34 dan melawat pohon haknya. Sejak 55 tidak mempunyai pohon yang kiri, kita cetak keluar dan terus kepada anak pohon kanan. 144 mempunyai pohon yang kiri, dan sebagainya kita mencetak 89, diikuti oleh 144, dan akhirnya nod yang paling kanan ada 233. Terdapat anda memilikinya, semua nombor dicetak dalam perintah dari terendah kepada tertinggi. 

Menambah sesuatu untuk pokok itu adalah agak menyakitkan juga. Semua yang perlu kita lakukan adalah pastikan bahawa kita mengikuti 3 pokok binari hartanah carian dan kemudian memasukkan nilai di mana terdapat ruang. Katakan kita ingin memasukkan nilai 7. Sejak 7 adalah kurang daripada 13, kita pergi ke kiri. Tetapi ia adalah lebih daripada 5, jadi kita merentasi ke kanan. Sejak ia adalah kurang daripada 8 dan 8 adalah nod daun, kita menambah 7 kepada anak kiri 8. Voilà! Kami telah menambah nombor kepada pohon carian dedua kami. 

Jika kita boleh menambah perkara, kita lebih baik dapat untuk memadam perkara serta. Malangnya bagi kita, memotong adalah sedikit lebih rumit - tidak banyak, tetapi hanya sedikit. Terdapat 3 senario yang berbeza yang perlu kita pertimbangkan apabila memotong elemen daripada pokok-pokok carian binari. Pertama, kes yang paling mudah adalah bahawa elemen nod daun. Dalam kes ini, kita hanya memadamnya dan pergi dengan perniagaan kami. Katakan kita mahu memadam 7 yang kita hanya menambah. Nah, kita hanya mencari ia, keluarkan ia, dan itulah ia. Kes seterusnya ialah jika nod mempunyai hanya 1 kanak-kanak. Di sini kita boleh memadam nod, tetapi kita perlu memastikan untuk menyambung anak pohon yang kini ditinggalkan parentless induk nod kita hanya dipadam. Katakanlah kita mahu untuk memadam 3 dari pokok kita. Kami mengambil elemen anak nod tersebut dan lampirkan ia ke induk nod. Dalam kes ini, kita sedang melampirkan 1 hingga 5. Ini kerja-kerja tanpa sebarang masalah kerana kita tahu, mengikut carian pokok harta binari, bahawa segala-galanya di pohon kiri 3 adalah kurang daripada 5. Sekarang bahawa pohon 3 diambil penjagaan, kita boleh memadamnya. Kes ketiga dan terakhir adalah yang paling kompleks. Ini adalah kes apabila nod yang kita mahu untuk memadam mempunyai 2 orang anak. Dalam usaha untuk melakukan ini, kita perlu mencari nod yang mempunyai nilai seterusnya terbesar, swap dua, dan kemudian memadam nod dalam soalan. Notis nod yang mempunyai nilai seterusnya terbesar tidak boleh mempunyai 2 orang anak sendiri sejak anak kiri akan menjadi calon yang lebih baik untuk terbesar seterusnya. Oleh itu, memotong nod dengan 2 kanak-kanak berjumlah bertukar-tukar dari 2 nod, dan kemudian memadam dikendalikan oleh 1 daripada 2 peraturan yang disebutkan di atas. Sebagai contoh, katakan kita mahu memadam nod akar, 13. Perkara pertama yang kita lakukan ialah kita mencari nilai seterusnya terbesar di pokok itu yang, dalam kes ini, ialah 21. Kami kemudian menukar 2 nod, membuat 13 daun dan 21 nod kumpulan pusat. Sekarang kita hanya boleh memadam 13. 

Seperti yang disentuh sebelum ini, terdapat banyak cara yang mungkin untuk membuat carian binari pokok yang sah. Malangnya bagi kita, ada yang lebih teruk daripada yang lain. Sebagai contoh, apa yang berlaku apabila kita membina pokok carian binari dari senarai yang disusun nombor? Semua nombor hanya ditambah ke kanan pada setiap langkah. Apabila kita hendak mencari nombor, kita tidak mempunyai pilihan tetapi hanya untuk melihat di sebelah kanan pada setiap langkah. Ini bukan adalah lebih baik daripada carian linear pada semua. Walaupun kita tidak akan melindungi mereka di sini, terdapat lain, lebih kompleks, struktur data yang memastikan bahawa ini tidak berlaku. Walau bagaimanapun, satu perkara mudah yang boleh dilakukan untuk mengelakkan ini adalah hanya shuffle secara rawak nilai input. Ia adalah sangat tidak mungkin bahawa secara kebetulan rawak senarai yang dikocok nombor disusun. Jika ini berlaku, kasino tidak akan kekal dalam perniagaan untuk tempoh yang lama. 

Terdapat anda memilikinya. Anda kini tahu tentang mencari binari dan pokok gelintaran perduaan. Saya Patrick Schmid, dan ini adalah CS50. [CS50.TV] Salah satu cara yang jelas akan mengimbas senarai dari ... [bip] ... Bilangan item ... Ya [Ketawa] ... Hantar nod 234 ... augh. >> Yay! Itu adalah -