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

Jika saya memberi Anda daftar nama karakter Disney dalam urutan abjad dan meminta Anda untuk menemukan Mickey Mouse, bagaimana Anda akan pergi tentang melakukan ini? Salah satu cara yang jelas akan memindai daftar dari awal dan memeriksa setiap nama untuk melihat apakah itu Mickey. Tapi seperti yang Anda baca Aladdin, Alice, Ariel, dan sebagainya, Anda akan segera menyadari bahwa mulai di depan daftar itu bukan ide yang baik. Oke, mungkin Anda harus mulai bekerja mundur dari akhir daftar. Sekarang Anda membaca Tarzan, Stitch, Putri Salju, dan sebagainya. Namun, hal ini tidak tampak seperti cara terbaik untuk pergi tentang itu. 

Nah, cara lain yang bisa Anda pergi untuk melakukan ini adalah untuk mencoba untuk mempersempit daftar nama-nama yang Anda harus melihat. Karena Anda tahu bahwa mereka berada dalam urutan abjad, Anda hanya bisa melihat nama-nama di tengah daftar dan memeriksa apakah Mickey Mouse adalah sebelum atau setelah nama ini. Melihat nama terakhir di kolom kedua Anda akan menyadari bahwa M untuk Mickey datang setelah J untuk Jasmine, sehingga Anda hanya akan mengabaikan paruh pertama daftar. Maka Anda mungkin akan melihat di bagian atas kolom terakhir dan melihat bahwa itu dimulai dengan Rapunzel. Mickey datang sebelum Rapunzel, sepertinya kita dapat mengabaikan kolom terakhir juga. Melanjutkan strategi pencarian, Anda akan segera melihat bahwa Mickey adalah pada paruh pertama dari daftar sisa nama dan akhirnya menemukan Mickey bersembunyi antara Merlin dan Minnie. 

Apa yang baru saja Anda lakukan adalah pencarian biner pada dasarnya. Seperti nama ini menyiratkan, ia melakukan strategi pencarian dalam hitungan biner. Apa artinya ini? Nah, mengingat daftar item diurutkan, algoritma pencarian biner membuat keputusan biner - kiri atau kanan, lebih besar dari atau kurang dari, abjad sebelum atau setelah - pada setiap titik. Sekarang bahwa kita memiliki nama yang sejalan dengan algoritma pencarian, mari kita lihat contoh lain, tapi kali ini dengan daftar nomor diurutkan. Katakanlah kita sedang mencari nomor 144 dalam daftar nomor diurutkan. Sama seperti sebelumnya, kita menemukan nomor yang ada di tengah - yang dalam hal ini adalah 13 - dan melihat apakah lebih besar dari 144 atau kurang dari 13. Karena itu jelas lebih besar dari 13, kita dapat mengabaikan segala sesuatu yang 13 atau kurang dan hanya berkonsentrasi pada tersisa separuhnya. Karena kita sekarang memiliki bahkan jumlah item yang tersisa, kita hanya memilih nomor yang dekat ke tengah. Dalam hal ini kita pilih 55. Kita bisa dengan mudah memilih 89. Oke. Sekali lagi, 144 lebih besar dari 55, jadi kami pergi ke kanan. Untungnya bagi kita, jumlah menengah berikutnya adalah 144, yang kita cari. Jadi dalam rangka untuk menemukan 144 menggunakan pencarian biner, kita dapat menemukannya hanya dalam 3 langkah. Jika kita akan menggunakan pencarian linear di sini, itu akan membawa kami 12 langkah. Sebagai soal fakta, karena ini metode pencarian membagi dua jumlah item itu harus melihat pada setiap langkah, ia akan menemukan item itu mencari di sekitar log dari jumlah item dalam daftar. Sekarang yang kita lihat 2 contoh, mari kita lihat beberapa pseudocode untuk fungsi rekursif yang mengimplementasikan pencarian biner. Mulai di atas, kita melihat bahwa kita harus menemukan fungsi yang mengambil 4 argumen: kunci, array, min, dan max. Kuncinya adalah jumlah yang kita cari, jadi 144 pada contoh sebelumnya. Array adalah daftar nomor yang kita cari. Min dan max adalah indeks dari posisi minimum dan maksimum bahwa kita sedang melihat. Jadi ketika kita mulai, min akan menjadi nol dan max akan menjadi indeks maksimum array. Seperti kita mempersempit pencarian ke bawah, kami akan memperbarui min dan max menjadi hanya kisaran yang kita masih mencari masuk 

Mari kita melompat ke bagian yang menarik pertama. Hal pertama yang kita lakukan adalah menemukan titik tengah, indeks yang setengah jalan antara min dan max dari array yang kita masih mempertimbangkan. Kemudian kita melihat nilai dari array di lokasi titik tengah dan melihat apakah jumlah yang kita cari adalah kurang dari kunci yang. Jika nomor pada posisi yang kurang, maka itu berarti kuncinya adalah lebih besar dari semua nomor di sebelah kiri posisi itu. Jadi kita bisa memanggil fungsi pencarian biner lagi, tapi kali ini memperbarui min dan parameter max untuk membaca hanya setengah yang lebih besar dari atau sama dengan nilai kita hanya melihat. Di sisi lain, jika kuncinya adalah kurang dari jumlah pada titik tengah saat array, kita ingin pergi ke kiri dan mengabaikan semua nomor yang lebih besar. Sekali lagi, kita sebut pencarian biner tapi kali ini dengan kisaran min dan max updated untuk menyertakan hanya bagian bawah. Jika nilai pada titik tengah saat ini dalam array bukanlah lebih besar dari atau lebih kecil dari kunci, maka harus sama dengan kunci. Jadi, kita hanya bisa mengembalikan indeks titik tengah saat ini, dan kami sudah selesai. Akhirnya, cek ini di sini adalah untuk kasus yang nomor tidak benar-benar dalam array angka yang kita cari. Jika indeks maksimum kisaran yang kita cari yang pernah kurang dari minimum, itu berarti bahwa kita sudah terlalu jauh. Karena jumlah itu tidak dalam array masukan, kita kembali -1 untuk menunjukkan bahwa tidak ada yang ditemukan. 

Anda mungkin telah memperhatikan bahwa untuk algoritma ini untuk bekerja, daftar nomor harus diurutkan. Dengan kata lain, kita hanya dapat menemukan 144 menggunakan pencarian biner jika semua nomor yang dipesan dari terendah hingga tertinggi. Jika hal ini tidak terjadi, kita tidak akan dapat mengecualikan setengah dari angka pada setiap langkah. Jadi kita memiliki 2 pilihan. Entah kita dapat mengambil daftar unsorted dan semacam itu sebelum menggunakan pencarian biner, atau kita dapat memastikan bahwa daftar nomor diurutkan seperti kita menambahkan nomor untuk itu. Dengan demikian, bukan hanya menyortir ketika kita harus mencari, mengapa tidak menjaga daftar diurutkan setiap saat? 

Salah satu cara untuk menjaga daftar nomor diurutkan sekaligus memungkinkan satu untuk menambah atau memindahkan nomor dari daftar ini adalah dengan menggunakan sesuatu yang disebut pohon pencarian biner. Sebuah pohon pencarian biner adalah struktur data yang memiliki 3 sifat. Pertama, subtree kiri setiap node hanya mengandung nilai-nilai yang kurang dari atau sama dengan nilai node. Kedua, hak subtree dari node hanya berisi nilai-nilai yang lebih besar dari atau sama dengan nilai node. Dan, akhirnya, baik kiri dan kanan subtrees dari semua node juga pohon pencarian biner. Mari kita lihat contoh dengan angka yang sama kita gunakan sebelumnya. Bagi anda yang belum pernah melihat pohon ilmu komputer sebelumnya, Mari saya mulai dengan mengatakan bahwa pohon ilmu komputer tumbuh ke bawah. Ya, tidak seperti pohon Anda terbiasa, akar pohon ilmu komputer adalah di bagian atas, dan daun di bagian bawah. Setiap kotak kecil yang disebut node, dan node yang terhubung satu sama lain dengan tepi. Jadi akar pohon ini adalah nilai node dengan nilai 13, yang memiliki 2 node anak dengan nilai 5 dan 34. Sebuah subtree adalah pohon yang dibentuk hanya dengan melihat subbagian dari seluruh pohon. 

Misalnya, subtree kiri 3 node pohon diciptakan oleh, node 0 1, dan 2. Jadi, jika kita kembali ke sifat dari pohon pencarian biner, kita melihat bahwa setiap node di pohon sesuai dengan semua 3 sifat, yaitu, subtree kiri hanya berisi nilai-nilai yang kurang dari atau sama dengan nilai node; hak subtree dari semua node hanya berisi nilai-nilai yang lebih besar dari atau sama dengan nilai node, dan subtrees baik kiri dan kanan dari semua node juga merupakan biner pohon pencarian. Meskipun pohon ini terlihat berbeda, ini adalah pohon biner yang sah pencarian untuk set yang sama angka. Sebagai soal fakta, ada banyak cara yang mungkin bahwa Anda dapat membuat pencarian berlaku pohon biner dari angka-angka. Nah, mari kita kembali ke yang pertama kita buat. Jadi apa yang bisa kita lakukan dengan pohon-pohon? Nah, kita bisa sangat sederhana menemukan nilai-nilai minimum dan maksimum. Nilai minimum dapat ditemukan dengan selalu pergi ke kiri sampai ada node lagi untuk mengunjungi. Sebaliknya, untuk menemukan satu maksimum hanya hanya turun ke kanan pada setiap waktu. 

Menemukan nomor lain yang tidak minimum atau maksimum sama mudah. Katakanlah kita sedang mencari nomor 89. Kami hanya memeriksa nilai setiap node dan pergi ke kiri atau kanan, tergantung pada apakah nilai node kurang dari atau lebih besar dari yang kita cari. Jadi, mulai dari akar 13, kita melihat bahwa 89 lebih besar, dan jadi kami pergi ke kanan. Kemudian kita melihat node untuk 34, dan lagi kita pergi ke kanan. 89 masih lebih besar dari 55, jadi kita terus pergi ke kanan. Kami kemudian datang dengan simpul dengan nilai 144 dan pergi ke kiri. Lo dan lihatlah, 89 ada di sana. 

Hal lain yang dapat kita lakukan adalah mencetak semua nomor dengan melakukan traversal inorder. Sebuah traversal inorder berarti untuk mencetak semuanya keluar di subtree kiri diikuti dengan mencetak node itu sendiri dan kemudian diikuti dengan mencetak segala sesuatu di kanan subtree. Sebagai contoh, mari kita biner favorit kami pohon pencarian dan mencetak angka dalam urutan diurutkan. Kami mulai dari akar 13, namun sebelum mencetak 13 kita harus mencetak segala sesuatu di subtree kiri. Jadi kita pergi ke 5. Kami masih harus pergi lebih dalam ke dalam pohon sampai kita menemukan simpul paling kiri, yang adalah nol. Setelah mencetak nol, kita kembali ke 1 dan mencetak yang keluar. Kemudian kami pergi ke kanan subtree, yaitu 2, dan mencetak yang keluar. Sekarang kita sudah selesai dengan itu subtree, kita bisa kembali ke 3 dan mencetaknya. Melanjutkan kembali, kami mencetak 5 dan kemudian 8. Sekarang kami telah menyelesaikan seluruh subtree kiri, kita bisa mencetak 13 dan mulai bekerja di sebelah kanan subtree. Kami melompat turun ke 34, tapi sebelum mencetak 34 kita harus mencetak subtree kiri. Jadi kita mencetak 21; maka kita bisa mencetak 34 dan mengunjungi subpohon kanan nya. Sejak 55 tidak memiliki subtree kiri, kita mencetaknya dan melanjutkan ke subtree kanan. 144 memiliki subtree kiri, dan jadi kami mencetak 89, diikuti oleh 144, dan akhirnya simpul paling kanan dari 233. Di sana Anda memilikinya, semua angka yang dicetak dalam urutan dari terendah hingga tertinggi. 

Menambahkan sesuatu untuk pohon ini relatif tanpa rasa sakit juga. Yang harus kita lakukan adalah memastikan bahwa kita mengikuti 3 sifat pencarian biner pohon dan kemudian memasukkan nilai di mana ada ruang. Katakanlah kita ingin memasukkan nilai 7. Sejak 7 kurang dari 13, kita pergi ke kiri. Tapi itu lebih besar dari 5, jadi kami melintasi ke kanan. Karena itu kurang dari 8 dan 8 adalah simpul daun, kita menambahkan 7 ke anak kiri dari 8. Voila! Kami telah menambahkan nomor ke pohon pencarian kami biner. 

Jika kita dapat menambahkan hal-hal, lebih baik kita bisa menghapus hal-hal juga. Sayangnya bagi kita, menghapus adalah sedikit lebih rumit - tidak banyak, tetapi hanya sedikit. Ada 3 skenario yang berbeda bahwa kita harus mempertimbangkan saat menghapus elemen dari pohon pencarian biner. Pertama, hal termudah adalah bahwa elemen adalah simpul daun. Dalam kasus ini, kita hanya menghapusnya dan melanjutkan bisnis kami. Katakanlah kita ingin menghapus 7 yang baru saja kita menambahkan. Nah, kita hanya menemukan itu, menghapusnya, dan hanya itu. Kasus berikutnya adalah jika node hanya memiliki 1 anak. Di sini kita dapat menghapus node, tapi pertama-tama kita harus memastikan untuk menghubungkan subtree yang sekarang kiri yatim ke node induk kami hanya dihapus. Katakanlah kita ingin menghapus 3 dari pohon kami. Kami mengambil elemen anak dari simpul tersebut dan melampirkannya pada orang tua dari node. Dalam kasus ini, kita sekarang melampirkan 1 ke 5. Ini bekerja tanpa masalah karena kita tahu, menurut properti biner pencarian pohon, bahwa segala sesuatu di subtree kiri 3 adalah kurang dari 5. Sekarang itulah subtree 3 yang diurus, kita bisa menghapusnya. Kasus ketiga dan terakhir adalah yang paling kompleks. Ini adalah kasus ketika node kita ingin menghapus memiliki 2 anak. Untuk melakukan hal ini, pertama-tama kita harus menemukan simpul yang memiliki nilai terbesar berikutnya, swap dua, dan kemudian menghapus node yang bersangkutan. Perhatikan node yang memiliki nilai terbesar berikutnya tidak dapat memiliki 2 anak itu sendiri sejak anak kiri akan menjadi calon yang lebih baik untuk terbesar berikutnya. Oleh karena itu, menghapus simpul dengan 2 anak berjumlah swapping dari 2 node, dan kemudian menghapus ditangani oleh 1 dari 2 aturan tersebut. Sebagai contoh, katakanlah kita ingin menghapus simpul akar, 13. Hal pertama yang kita lakukan adalah kita menemukan nilai terbesar berikutnya dalam pohon yang, dalam hal ini, adalah 21. Kami kemudian swap 2 node, membuat 13 daun dan 21 node kelompok pusat. Sekarang kita hanya dapat menghapus 13. 

Seperti disinggung sebelumnya, ada banyak cara yang mungkin untuk membuat sebuah pohon pencarian biner yang valid. Sayangnya bagi kita, beberapa lebih buruk daripada yang lain. Sebagai contoh, apa yang terjadi ketika kita membangun sebuah pohon pencarian biner dari daftar diurutkan dari nomor? Semua nomor yang hanya ditambahkan ke kanan pada setiap langkah. Ketika kita ingin mencari nomor, kita tidak punya pilihan selain hanya untuk melihat kanan di setiap langkah. Hal ini tidak lebih baik daripada pencarian linear sama sekali. Meskipun kami tidak akan menutupi mereka di sini, ada yang lain, lebih kompleks, Data struktur yang memastikan bahwa hal ini tidak terjadi. Namun, satu hal sederhana yang dapat dilakukan untuk menghindari hal ini adalah hanya secara acak mengocok nilai masukan. Ini sangat tidak mungkin bahwa secara kebetulan acak daftar beringsut dari nomor yang diurutkan. Jika ini terjadi, kasino tidak akan tinggal dalam bisnis untuk waktu yang lama. 

Di sana Anda memilikinya. Anda sekarang tahu tentang pencarian biner dan pohon pencarian biner. Saya Patrick Schmid, dan ini adalah CS50. [CS50.TV] Salah satu cara yang jelas akan memindai daftar dari ... [bip] ... Jumlah item ... yep [Tertawa] ... Posting simpul dari 234 ... Augh. >> Yay! Itu -