Apa itu Pohon Pencarian Biner?
Pohon pencarian biner adalah algoritma tingkat lanjut yang digunakan untuk menganalisis node, cabang kiri dan kanannya, yang dimodelkan dalam struktur pohon dan mengembalikan nilainya. BST dirancang pada arsitektur algoritma pencarian biner dasar; karenanya memungkinkan pencarian, penyisipan, dan penghapusan node yang lebih cepat. Ini membuat program menjadi sangat cepat dan akurat.
Dalam tutorial Struktur Data ini, Anda akan mempelajari:
- Apa itu Pohon Pencarian Biner?
- Atribut Pohon Pencarian Biner
- Mengapa kita membutuhkan Pohon Pencarian Biner?
- Jenis Pohon Biner
- Bagaimana Binary Search Tree Bekerja?
- Istilah Penting
Atribut Pohon Pencarian Biner
BST terdiri dari beberapa node dan terdiri dari atribut berikut:
- Node pohon direpresentasikan dalam hubungan induk-anak
- Setiap node induk dapat memiliki nol node anak atau maksimal dua subnode atau subpohon di sisi kiri dan kanan.
- Setiap sub-pohon, juga dikenal sebagai pohon pencarian biner, memiliki sub-cabang di kanan dan kirinya.
- Semua node ditautkan dengan key-value pair.
- Kunci dari node yang ada di subpohon kiri lebih kecil dari kunci node induknya
- Demikian pula, kunci node subtree kiri memiliki nilai yang lebih rendah daripada kunci node induknya.
- Ada node utama atau parent level 11. Di bawahnya, ada node / cabang kiri dan kanan dengan nilai key masing-masing
- Sub-pohon kanan memiliki nilai kunci yang lebih besar dari simpul induk
- Sub-pohon kiri memiliki nilai daripada simpul induk
Mengapa kita membutuhkan Pohon Pencarian Biner?
- Dua faktor utama yang membuat pohon pencarian biner menjadi solusi optimal untuk masalah dunia nyata adalah Kecepatan dan Akurasi.
- Karena fakta bahwa pencarian biner dalam format seperti cabang dengan relasi orang tua-anak, algoritme mengetahui di lokasi pohon mana elemen perlu dicari. Ini mengurangi jumlah perbandingan nilai kunci yang harus dibuat oleh program untuk menemukan elemen yang diinginkan.
- Selain itu, jika elemen yang akan dicari lebih besar atau lebih kecil dari node induk, node mengetahui sisi pohon mana yang harus dicari. Alasannya adalah, sub-pohon kiri selalu lebih kecil dari simpul induk, dan sub-pohon kanan memiliki nilai yang selalu sama atau lebih besar dari simpul induk.
- BST biasanya digunakan untuk mengimplementasikan pencarian kompleks, logika permainan yang kuat, aktivitas pelengkapan otomatis, dan grafik.
- Algoritme secara efisien mendukung operasi seperti pencarian, penyisipan, dan penghapusan.
Jenis Pohon Biner
Tiga jenis pohon biner adalah:
- Pohon biner lengkap: Semua level di pepohonan penuh dengan kemungkinan pengecualian level terakhir. Demikian pula, semua node penuh, mengarahkan paling kiri.
- Pohon biner penuh: Semua simpul memiliki 2 simpul anak kecuali daun.
- Pohon biner Seimbang atau Sempurna: Di pohon, semua node memiliki dua anak. Selain itu, ada level yang sama untuk setiap subnode.
Bagaimana Binary Search Tree Bekerja?
Pohon selalu memiliki simpul akar dan simpul anak selanjutnya, baik di kiri atau kanan. Algoritme melakukan semua operasi dengan membandingkan nilai dengan root dan node turunan selanjutnya di sub-pohon kiri atau kanan yang sesuai.
Bergantung pada elemen yang akan disisipkan, dicari, atau dihapus, setelah perbandingan, algoritme dapat dengan mudah melepaskan subpohon kiri atau kanan dari simpul akar.
BST terutama menawarkan tiga jenis operasi berikut untuk penggunaan Anda:
- Pencarian: mencari elemen dari pohon biner
- Sisipkan: menambahkan elemen ke pohon biner
- Hapus: hapus elemen dari pohon biner
Setiap operasi memiliki struktur dan metode eksekusi / analisisnya sendiri, tetapi yang paling kompleks dari semuanya adalah operasi Hapus.
Operasi Pencarian
Selalu mulai menganalisis pohon pada simpul akar dan kemudian pindah lebih jauh ke subpohon kanan atau kiri dari simpul akar tergantung pada elemen yang akan ditempatkan apakah lebih kecil atau lebih besar dari akar.
- Elemen yang akan dicari adalah 10
- Bandingkan elemen dengan simpul akar 12, 10 <12, maka Anda pindah ke subtree kiri. Tidak perlu menganalisis subtree kanan
- Sekarang bandingkan 10 dengan simpul 7, 10> 7, jadi pindah ke subtree kanan
- Kemudian bandingkan 10 dengan node berikutnya, yaitu 9, 10> 9, lihat anak subpohon kanan
- 10 cocok dengan nilai di node, 10 = 10, mengembalikan nilai ke pengguna.
Sisipkan Operasi
Ini adalah operasi yang sangat mudah. Pertama, simpul akar dimasukkan, kemudian nilai selanjutnya dibandingkan dengan simpul akar. Jika nilainya lebih besar dari akar, ia ditambahkan ke subtree kanan, dan jika lebih kecil dari akar, ia ditambahkan ke subtree kiri.
- Ada daftar 6 elemen yang perlu disisipkan dalam BST secara berurutan dari kiri ke kanan
- Masukkan 12 sebagai simpul akar dan bandingkan nilai 7 dan 9 berikutnya untuk disisipkan sesuai dengan subpohon kanan dan kiri
- Bandingkan nilai 19, 5, dan 10 yang tersisa dengan simpul akar 12 dan tempatkan sesuai. 19> 12 tempatkan itu sebagai anak kanan 12, 5 <12 & 5 <7, maka tempatkan itu sebagai anak kiri 7.
- Sekarang bandingkan 10, 10 adalah <12 & 10 adalah> 7 & 10 adalah> 9, tempatkan 10 sebagai subtree kanan dari 9.
Hapus Operasi
Hapus adalah yang paling canggih dan kompleks di antara semua operasi lainnya. Ada beberapa kasus yang ditangani untuk dihapus di BST.
- Kasus 1- Node dengan nol anak: ini adalah situasi termudah, Anda hanya perlu menghapus simpul yang tidak memiliki anak lagi di kanan atau kiri.
- Kasus 2 - Node dengan satu anak: setelah Anda menghapus node, cukup hubungkan node turunannya dengan node induk dari nilai yang dihapus.
- Kasus 3 Node dengan dua anak: ini adalah situasi yang paling sulit, dan bekerja pada dua aturan berikut
- 3a - In Order Predecessor: Anda perlu menghapus node dengan dua anak dan menggantinya dengan nilai terbesar di sub-pohon kiri dari node yang dihapus
- 3b - In Order Successor: Anda perlu menghapus node dengan dua anak dan menggantinya dengan nilai terbesar di sub-pohon kanan dari node yang dihapus
- Ini adalah kasus penghapusan pertama di mana Anda menghapus node yang tidak memiliki turunan. Seperti yang Anda lihat pada diagram bahwa 19, 10 dan 5 tidak memiliki anak. Tapi kami akan menghapus 19.
- Hapus nilai 19 dan hapus link dari node.
- Lihat struktur baru BST tanpa 19
- Ini adalah kasus kedua penghapusan di mana Anda menghapus node yang memiliki 1 anak, seperti yang Anda lihat pada diagram bahwa 9 memiliki satu anak.
- Hapus simpul 9 dan ganti dengan anak 10 dan tambahkan tautan dari 7 ke 10
- Lihat struktur baru BST tanpa 9
- Di sini Anda akan menghapus simpul 12 yang memiliki dua anak
- Penghapusan node akan terjadi berdasarkan aturan pendahulu berurutan, yang berarti bahwa elemen terbesar di subpohon kiri 12 akan menggantikannya.
- Hapus simpul 12 dan ganti dengan 10 karena itu adalah nilai terbesar di subpohon kiri
- Lihat struktur baru BST setelah menghapus 12
- 1 Hapus simpul 12 yang memiliki dua anak
- 2 Penghapusan node akan terjadi berdasarkan aturan In Order Successor, yang berarti elemen terbesar di subpohon kanan 12 akan menggantikannya
- 3 Hapus simpul 12 dan ganti dengan 19 karena itu adalah nilai terbesar di sub-pohon kanan
- 4 Lihat struktur baru BST setelah menghapus 12
Istilah Penting
- Sisipkan - Menyisipkan elemen di pohon / membuat pohon.
- Search - Mencari elemen di pohon.
- Preorder Traversal - Melintasi pohon dengan cara memesan di muka.
- Inorder Traversal - Melintasi pohon secara berurutan.
- Postorder Traversal - Melintasi pohon dengan cara post-order.
Ringkasan
- BST adalah algoritma tingkat lanjut yang melakukan berbagai operasi berdasarkan perbandingan nilai node dengan node root.
- Salah satu poin dalam hierarki orang tua-anak mewakili node. Setidaknya satu orang tua atau simpul akar tetap ada sepanjang waktu.
- Ada subtree kiri dan subtree kanan. Subpohon kiri berisi nilai yang kurang dari simpul akar. Namun, subtree kanan berisi nilai yang lebih besar dari node root.
- Setiap node dapat memiliki nol, satu, atau dua turunan.
- Pohon pencarian biner memfasilitasi operasi utama seperti pencarian, penyisipan, dan penghapusan.
- Hapus menjadi yang paling kompleks memiliki banyak kasus, misalnya node tanpa anak, node dengan satu anak, dan node dengan dua anak.
- Algoritme ini digunakan dalam solusi dunia nyata seperti game, data pelengkapan otomatis, dan grafik.