Apa itu Pohon Carian Binari?
Pohon carian binari adalah algoritma lanjutan yang digunakan untuk menganalisis nod, cabang kiri dan kanannya, yang dimodelkan dalam struktur pokok dan mengembalikan nilainya. BST dibuat berdasarkan seni bina algoritma carian binari asas; oleh itu ia membolehkan pencarian, penyisipan, dan penyingkiran nod yang lebih pantas. Ini menjadikan program ini sangat pantas dan tepat.
Dalam tutorial Struktur Data ini, anda akan belajar:
- Apa itu Pohon Carian Binari?
- Atribut Pokok Carian Binari
- Mengapa kita memerlukan Binary Search Tree?
- Jenis Pokok Perduaan
- Bagaimana Pokok Carian Binari Berfungsi?
- Syarat Penting
Atribut Pokok Carian Binari
BST terbuat dari beberapa nod dan terdiri daripada atribut berikut:
- Node pokok ditunjukkan dalam hubungan ibu bapa-anak
- Setiap nod ibu bapa boleh mempunyai node anak sifar atau maksimum dua subnode atau subtrees di sebelah kiri dan kanan.
- Setiap sub-pokok, juga dikenali sebagai pokok carian binari, mempunyai sub-cabang di sebelah kanan dan kiri mereka sendiri.
- Semua nod dihubungkan dengan pasangan nilai-kunci.
- Kekunci nod yang terdapat di subtree kiri lebih kecil daripada kunci nod induknya
- Begitu juga, kunci nod subtree kiri mempunyai nilai yang lebih rendah daripada kunci nod induknya.
- Terdapat nod utama atau tahap induk 11. Di bawahnya, terdapat simpul / cabang kiri dan kanan dengan nilai utama mereka sendiri
- Sub-pokok yang betul mempunyai nilai kunci yang lebih besar daripada nod induk
- Sub-pokok kiri mempunyai nilai daripada nod induk
Mengapa kita memerlukan Binary Search Tree?
- Dua faktor utama yang menjadikan pokok carian binari sebagai penyelesaian optimum untuk sebarang masalah di dunia nyata ialah Kepantasan dan Ketepatan.
- Oleh kerana carian binari dalam format seperti cabang dengan hubungan ibu bapa-anak, algoritma tahu di mana lokasi pokok unsur-unsur perlu dicari. Ini mengurangkan jumlah perbandingan nilai-kunci yang harus dibuat oleh program untuk mencari elemen yang diinginkan.
- Selain itu, sekiranya elemen yang hendak dicari lebih besar atau lebih kecil daripada nod induk, simpul akan mengetahui bahagian pokok mana yang hendak dicari. Sebabnya, sub-pokok kiri selalu lebih rendah daripada simpul induk, dan sub-pokok kanan mempunyai nilai selalu sama atau lebih besar daripada nod induk.
- BST biasanya digunakan untuk melaksanakan pencarian yang kompleks, logik permainan yang kuat, aktiviti yang lengkap secara otomatis, dan grafik.
- Algoritma dengan cekap menyokong operasi seperti carian, memasukkan, dan memadam.
Jenis Pokok Perduaan
Tiga jenis pokok binari adalah:
- Pokok binari lengkap: Semua peringkat di pokok penuh dengan kemungkinan pengecualian tahap terakhir. Begitu juga, semua nod penuh, menghala ke kiri paling kanan.
- Pokok binari penuh: Semua nod mempunyai 2 simpul anak kecuali daun.
- Pokok binari seimbang atau Sempurna: Di pokok, semua nod mempunyai dua anak. Selain itu, terdapat tahap yang sama untuk setiap subnode.
Bagaimana Pokok Carian Binari Berfungsi?
Pokok ini selalu mempunyai simpul akar dan simpul anak lebih jauh, sama ada di kiri atau kanan. Algoritma melakukan semua operasi dengan membandingkan nilai dengan akar dan nod anak selanjutnya di sub-pokok kiri atau kanan dengan sewajarnya.
Bergantung pada elemen yang akan dimasukkan, dicari, atau dihapus, setelah perbandingan, algoritma dapat dengan mudah menjatuhkan subtree kiri atau kanan simpul akar.
BST terutamanya menawarkan tiga jenis operasi berikut untuk penggunaan anda:
- Cari: mencari elemen dari pokok binari
- Sisipkan: menambahkan elemen pada pokok binari
- Padam: hapus elemen dari pokok binari
Setiap operasi mempunyai struktur dan kaedah pelaksanaan / analisisnya yang tersendiri, tetapi yang paling kompleks adalah operasi Hapus.
Operasi Carian
Sentiasa mulakan menganalisis pokok di simpul akar dan kemudian bergerak lebih jauh ke subtree kanan atau kiri simpul akar bergantung pada elemen yang akan berada sama ada kurang atau lebih besar daripada akar.
- Elemen yang hendak dicari adalah 10
- Bandingkan elemen dengan nod akar 12, 10 <12, oleh itu anda beralih ke subtree kiri. Tidak perlu menganalisis subtree kanan
- Sekarang bandingkan 10 dengan nod 7, 10> 7, jadi beralih ke subtree kanan
- Kemudian bandingkan 10 dengan nod seterusnya, iaitu 9, 10> 9, lihat pada anak pokok yang betul
- 10 sepadan dengan nilai di simpul, 10 = 10, kembalikan nilainya kepada pengguna.
Masukkan Operasi
Ini adalah operasi ke hadapan yang sangat lurus. Pertama, simpul akar dimasukkan, kemudian nilai seterusnya dibandingkan dengan nod akar. Sekiranya nilainya lebih besar daripada root, maka akan ditambahkan ke subtree kanan, dan jika lebih rendah dari root, maka akan ditambahkan ke subtree kiri.
- Terdapat senarai 6 elemen yang perlu dimasukkan dalam BST mengikut urutan dari kiri ke kanan
- Masukkan 12 sebagai simpul akar dan bandingkan nilai seterusnya 7 dan 9 untuk memasukkan dengan tepat ke subtree kanan dan kiri
- Bandingkan nilai baki 19, 5, dan 10 dengan simpul akar 12 dan letakkan dengan sewajarnya. 19> 12 letakkan sebagai anak kanan 12, 5 <12 & 5 <7, oleh itu letakkan sebagai anak kiri 7.
- Sekarang bandingkan 10, 10 ialah <12 & 10 adalah> 7 & 10 adalah> 9, letakkan 10 sebagai subtore kanan 9.
Padam Operasi
Hapus adalah yang paling maju dan kompleks di antara semua operasi lain. Terdapat beberapa kes yang dikendalikan untuk penghapusan di BST.
- Kes 1- Node dengan anak-anak sifar: ini adalah keadaan paling mudah, anda hanya perlu memadam simpul yang tidak mempunyai anak lagi di sebelah kanan atau kiri.
- Kes 2 - Node dengan satu anak: setelah anda menghapus node, sambungkan simpul anak dengan node ibu bapa dari nilai yang dihapuskan.
- Kes 3 Node dengan dua orang anak: ini adalah keadaan yang paling sukar, dan ia berfungsi berdasarkan dua peraturan berikut
- 3a - Pendahuluan Dalam Urutan: anda perlu memadam simpul dengan dua anak dan menggantinya dengan nilai terbesar pada subtitre kiri dari nod yang dipadamkan
- 3b - Dalam Pengganti Pesanan: anda perlu memadam node dengan dua anak dan menggantinya dengan nilai terbesar pada subtitre kanan nod yang dipadamkan
- Ini adalah kes penghapusan pertama di mana anda menghapus nod yang tidak mempunyai anak. Seperti yang anda lihat dalam rajah bahawa 19, 10 dan 5 tidak mempunyai anak. Tetapi kita akan memadamkan 19.
- Padamkan nilai 19 dan alih keluar pautan dari nod.
- Lihat struktur baru BST tanpa 19
- Ini adalah kes penghapusan kedua di mana anda menghapus nod yang mempunyai 1 anak, seperti yang anda lihat dalam rajah bahawa 9 mempunyai satu anak.
- Padamkan nod 9 dan ganti dengan anak 10 dan tambahkan pautan dari 7 hingga 10
- Lihat struktur baru BST tanpa 9
- Di sini anda akan memadamkan nod 12 yang mempunyai dua anak
- Penghapusan nod akan berlaku berdasarkan peraturan pendahuluan dalam urutan, yang bermaksud bahawa unsur terbesar pada subtree kiri 12 akan menggantikannya.
- Padamkan nod 12 dan gantikan dengan 10 kerana ia adalah nilai terbesar pada subtree kiri
- Lihat struktur baru BST setelah memadam 12
- 1 Padamkan nod 12 yang mempunyai dua anak
- 2 Penghapusan nod akan berlaku berdasarkan peraturan In Order Successor, yang bermaksud bahawa elemen terbesar pada subtree kanan 12 akan menggantikannya
- 3 Padamkan nod 12 dan gantikan dengan 19 kerana ia adalah nilai terbesar pada subtree kanan
- 4 Lihat struktur baru BST setelah menghapus 12
Syarat Penting
- Insert - Memasukkan elemen dalam pokok / membuat pokok.
- Cari - Mencari elemen dalam pokok.
- Preorder Traversal - Melintasi pokok dengan cara pra-pesanan.
- Inorder Traversal - Melintasi sebatang pokok secara tertib.
- Postorder Traversal - Melintasi sebatang pokok secara post-order.
Ringkasan
- BST adalah algoritma tahap lanjutan yang melakukan pelbagai operasi berdasarkan perbandingan nilai nod dengan nod akar.
- Mana-mana titik dalam hirarki ibu bapa-anak mewakili simpul. Sekurang-kurangnya satu nod induk atau root tetap ada sepanjang masa.
- Terdapat subtree kiri dan subtree kanan. Subtree kiri mengandungi nilai yang kurang daripada simpul akar. Walau bagaimanapun, subtree kanan mengandungi nilai yang lebih besar daripada simpul akar.
- Setiap simpul boleh mempunyai sifar, satu, atau dua anak.
- Pohon carian binari memudahkan operasi utama seperti mencari, memasukkan dan memadam.
- Hapus menjadi yang paling kompleks mempunyai banyak kes, misalnya, simpul tanpa anak, simpul dengan satu anak, dan simpul dengan dua anak.
- Algoritma ini digunakan dalam penyelesaian dunia nyata seperti permainan, data pelengkap automatik, dan grafik.