Pelaksanaan pepohon carian binari

2024 Pengarang: Angel Austin | [email protected]. Diubah suai terakhir: 2023-12-17 05:36

Pokok carian binari - pangkalan data berstruktur yang mengandungi nod, dua pautan ke nod lain, kanan dan kiri. Nod ialah objek kelas yang mempunyai data dan NULL ialah tanda yang menandakan penamat pokok.

Ia sering dirujuk sebagai BST, yang mempunyai sifat istimewa: nod yang lebih besar daripada akar terletak di sebelah kanannya dan yang lebih kecil di sebelah kiri.

Teori dan istilah umum

Dalam pepohon carian binari, setiap nod, tidak termasuk punca, disambungkan dengan tepi terarah dari satu nod ke nod yang lain, yang dipanggil induk. Setiap daripada mereka boleh disambungkan kepada bilangan nod sewenang-wenangnya, dipanggil kanak-kanak. Nod tanpa "kanak-kanak" dipanggil daun (nod luar). Unsur yang bukan daun dipanggil dalaman. Nod dengan ibu bapa yang sama adalah adik beradik. Nod paling atas dipanggil akar. Dalam BST, tetapkan elemen pada setiap nod dan pastikan ia mempunyai sifat khas yang ditetapkan untuknya.

Istilah pokok:

1. Kedalaman nod ialah bilangan tepi yang ditakrifkan daripada punca kepada nod.
2. Ketinggian nod ialah bilangan tepi yang ditakrifkan daripadanya hingga ke daun terdalam.
3. Ketinggian pokok ditentukan oleh ketinggian akar.
4. Pokok carian binari ialah reka bentuk khas, ia memberikan nisbah ketinggian dan bilangan nod yang terbaik.
5. Tinggi h dengan N nod paling banyak O (log N).

Anda boleh membuktikannya dengan mudah dengan mengira nod pada setiap peringkat, bermula dari akar, dengan mengandaikan bahawa ia mengandungi bilangan terbesar: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Menyelesaikan ini untuk h memberikan h=O (log n).

Faedah kayu:

1. Mencerminkan perhubungan struktur data.
2. Digunakan untuk mewakili hierarki.
3. Pastikan pemasangan dan carian cekap.
4. Pokok ialah data yang sangat fleksibel, membolehkan anda memindahkan subpokok dengan usaha yang minimum.

Kaedah carian

Secara umum, untuk menentukan sama ada nilai berada dalam BST, mulakan pepohon carian binari pada akarnya dan tentukan sama ada ia memenuhi keperluan:

• berada di akar umbi;
• berada di subpokok kiri akar;
• di subpokok kanan akar.

Jika tiada daftar asas berpuas hati, carian rekursif dilakukan dalam subpohon yang sepadan. Sebenarnya terdapat dua pilihan asas:

1. Pokok itu kosong - pulangkan palsu.
2. Nilai berada dalam nod akar - kembalikan benar.

Perlu diingat bahawa pokok carian binari dengan skema yang dibangunkan sentiasa mula mencari di sepanjang laluan dari akar ke daun. Dalam kes yang paling teruk, ia pergi ke daun. Oleh itu, masa yang paling teruk adalah berkadar dengan panjang laluan terpanjang dari akar ke daun, iaitu ketinggian pokok. Secara umum, ini adalah masa anda perlu mengetahui tempoh masa yang diperlukan untuk mencari sebagai fungsi bilangan nilai yang disimpan dalam pepohon.

Dengan kata lain, terdapat hubungan antara bilangan nod dalam BST dan ketinggian pokok, bergantung pada "bentuk"nya. Dalam kes yang paling teruk, nod hanya mempunyai seorang anak, dan pokok carian binari seimbang pada asasnya ialah senarai terpaut. Contohnya:

50

/

10

15

30

/

20

Pokok ini mempunyai 5 nod dan ketinggian=5. Mencari nilai dalam julat 16-19 dan 21-29 akan memerlukan laluan berikut dari akar ke daun (nod yang mengandungi nilai 20), i.e., ia akan mengambil masa berkadar dengan bilangan nod. Paling baik, mereka semua mempunyai 2 orang anak, dan daunnya terletak pada kedalaman yang sama.

Pokok carian binari ini mempunyai 7 nod dan ketinggian=3. Secara umumnya, pokok seperti ini (pokok penuh) akan mempunyai ketinggian lebih kurang log 2 (N), di mana N ialah bilangan nod dalam pokok. Nilai log 2 (N) ialah bilangan kali (2) N boleh dibahagikan sebelum sifar dicapai.

Merumuskan: masa paling teruk yang diperlukan untuk mencari dalam BST ialah O (ketinggian pokok). Pokok "linear" kes terburuk ialah O(N), dengan N ialah bilangan nod dalam pokok itu. Paling baik, pokok "lengkap" ialah O(log N).

sisipan binari BST

Tertanya-tanya di mana sepatutnyanod baru terletak di BST, anda perlu memahami logik, ia mesti diletakkan di mana pengguna menemuinya. Di samping itu, anda perlu mengingati peraturan:

1. Pendua tidak dibenarkan, percubaan untuk memasukkan nilai pendua akan mengeluarkan pengecualian.
2. Kaedah sisipan awam menggunakan kaedah "pembantu" rekursif pembantu untuk benar-benar memasukkan.
3. Nod yang mengandungi nilai baharu sentiasa disisipkan sebagai daun dalam BST.
4. Kaedah sisipan awam mengembalikan batal, tetapi kaedah pembantu mengembalikan BSTnode. Ia melakukan ini untuk mengendalikan kes di mana nod yang dihantar kepadanya adalah batal.

Secara umum, kaedah pembantu menunjukkan bahawa jika pepohon carian binari asal kosong, hasilnya ialah pepohon dengan satu nod. Jika tidak, hasilnya akan menjadi penunjuk ke nod yang sama yang telah diluluskan sebagai hujah.

Pemadaman dalam algoritma binari

Seperti yang anda jangkakan, pemadaman elemen melibatkan mencari nod yang mengandungi nilai untuk dialih keluar. Terdapat beberapa perkara dalam kod ini:

1. BST menggunakan pembantu, kaedah pemadaman terlebih beban. Jika elemen yang anda cari tiada dalam pokok, maka kaedah pembantu akhirnya akan dipanggil dengan n==null. Ini tidak dianggap sebagai ralat, pokok itu tidak berubah dalam kes ini. Kaedah delete helper mengembalikan nilai - penunjuk ke pepohon yang dikemas kini.
2. Apabila daun dialih keluar, pengalihan keluar daripada pepohon carian binari menetapkan penuding anak yang sepadan bagi induknya kepada null, atau akar kepada null jika yang dialih keluar adalahnod ialah akar dan tidak mempunyai anak.
3. Perhatikan bahawa panggilan padam mestilah salah satu daripada yang berikut: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), kunci)). Oleh itu, dalam ketiga-tiga kes adalah betul bahawa kaedah padam hanya mengembalikan null.
4. Apabila carian untuk nod yang mengandungi nilai yang akan dipadamkan berjaya, terdapat tiga pilihan: nod yang akan dipadamkan ialah daun (tiada anak), nod yang akan dipadamkan mempunyai satu anak, ia mempunyai dua kanak-kanak.
5. Apabila nod yang dialih keluar mempunyai seorang anak, anda boleh menggantikannya dengan anak, mengembalikan penunjuk kepada anak itu.
6. Jika nod yang akan dipadamkan mempunyai sifar atau 1 anak, maka kaedah padam akan "mengikut laluan" dari akar ke nod itu. Jadi masa yang paling teruk adalah berkadar dengan ketinggian pokok, untuk kedua-dua carian dan sisipan.

Jika nod yang akan dialih keluar mempunyai dua anak, langkah berikut diambil:

1. Cari nod yang hendak dipadamkan, mengikut laluan dari akar ke nod.
2. Cari nilai terkecil bagi v dalam subpokok kanan, meneruskan sepanjang laluan ke daun.
3. Alih keluar nilai v secara rekursif, ikut laluan yang sama seperti dalam langkah 2.
4. Oleh itu, dalam kes yang paling teruk, laluan dari akar ke daun dilakukan dua kali.

Tertib lintasan

Traversal ialah proses yang melawati semua nod dalam pokok. Oleh kerana pepohon carian binari C ialah struktur data bukan linear, tiada traversal yang unik. Sebagai contoh, kadangkala beberapa algoritma traversaldikumpulkan kepada dua jenis berikut:

• kedalaman lintasan;
• lulus pertama.

Hanya terdapat satu jenis lintasan lebar - memintas aras. Lintasan ini melawati nod aras ke bawah dan kiri, atas dan kanan.

Terdapat tiga jenis lintasan dalam yang berbeza:

1. Meluluskan PraPesan - mula-mula lawati ibu bapa dan kemudian anak kiri dan kanan.
2. Meluluskan Pesanan - melawat anak kiri, kemudian ibu bapa dan anak kanan.
3. Lepasi PostOrder - melawat anak kiri, kemudian anak kanan, kemudian ibu bapa.

Contoh untuk empat traversal pepohon carian binari:

1. Prapesan - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. PosPesan - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Angka menunjukkan susunan nod yang dilawati. Nombor 1 ialah nod pertama dalam traversal tertentu dan 7 ialah nod terakhir.

Perjalanan umum ini boleh diwakili sebagai algoritma tunggal, dengan mengandaikan bahawa setiap nod dilawati tiga kali. Lawatan Euler ialah berjalan di sekitar pokok binari di mana setiap tepi dianggap sebagai dinding yang tidak boleh dilalui oleh pengguna. Dalam perjalanan ini, setiap nod akan dilawati sama ada di sebelah kiri, atau di bawah, atau di sebelah kanan. Lawatan Euler, yang melawati nod di sebelah kiri, menyebabkan preposisi dipintas. Apabila nod di bawah dilawati, ia akan dilalui mengikut urutan. Dan apabila nod di sebelah kanan dilawati - dapatkanpintasan langkah demi langkah.

Navigasi dan Nyahpepijat

Untuk memudahkan menavigasi pepohon, buat fungsi yang mula-mula menyemak sama ada ia adalah anak kiri atau kanan. Untuk menukar kedudukan nod, mesti ada akses mudah kepada penuding pada nod induk. Melaksanakan pokok dengan betul adalah sangat sukar, jadi anda perlu mengetahui dan menggunakan proses penyahpepijatan. Pepohon carian binari dengan pelaksanaan selalunya mempunyai penunjuk yang sebenarnya tidak menunjukkan arah perjalanan.

Untuk memikirkan semua ini, fungsi digunakan yang menyemak sama ada pokok itu boleh betul dan membantu mencari banyak ralat. Sebagai contoh, ia menyemak sama ada nod induk ialah nod anak. Dengan assert(is_wellformed(root)) banyak ralat boleh ditangkap lebih awal. Menggunakan beberapa titik putus yang diberikan dalam fungsi ini, anda juga boleh menentukan dengan tepat penunjuk mana yang salah.

Fungsi Konsolenausgabe

Fungsi ini mengalirkan seluruh pokok ke konsol dan oleh itu sangat berguna. Urutan di mana matlamat output pokok dilaksanakan ialah:

1. Untuk melakukan ini, anda perlu terlebih dahulu menentukan maklumat yang akan dikeluarkan melalui nod.
2. Dan anda juga perlu tahu sejauh mana lebar dan tinggi pokok itu untuk mengambil kira berapa banyak ruang untuk ditinggalkan.
3. Fungsi berikut mengira maklumat ini untuk pokok dan setiap subpokok. Memandangkan anda hanya boleh menulis pada konsol baris demi baris, anda juga perlu mencetak pokok baris demi baris.
4. Sekarang kita memerlukan cara lain untuk menarik diriseluruh pokok, bukan hanya baris demi baris.
5. Dengan bantuan fungsi dump, anda boleh membaca pokok dan meningkatkan algoritma output dengan ketara, setakat kelajuan.

Namun, fungsi ini sukar digunakan pada pokok besar.

Salin pembina dan pemusnah

Oleh kerana pepohon bukan struktur data yang remeh, adalah lebih baik untuk melaksanakan pembina salinan, pemusnah dan pengendali tugasan. Pemusnah mudah dilaksanakan secara rekursif. Untuk pokok yang sangat besar, ia boleh mengendalikan "limpahan timbunan". Dalam kes ini, ia dirumus secara berulang. Ideanya adalah untuk mengeluarkan daun yang mewakili nilai terkecil semua daun, jadi ia berada di sebelah kiri pokok. Memotong daun pertama menghasilkan daun baru, dan pokok itu mengecut sehingga akhirnya tidak lagi wujud.

Pembina salinan juga boleh dilaksanakan secara rekursif, tetapi berhati-hati jika pengecualian dilemparkan. Jika tidak, pokok itu dengan cepat menjadi mengelirukan dan terdedah kepada ralat. Itulah sebabnya versi berulang lebih disukai. Ideanya adalah untuk melalui pokok lama dan pokok baru, seperti yang anda lakukan dalam pemusnah, mengklon semua nod yang ada dalam pokok lama tetapi bukan yang baru.

Dengan kaedah ini, pelaksanaan pepohon carian binari sentiasa dalam keadaan sihat dan boleh dialih keluar oleh pemusnah walaupun dalam keadaan tidak lengkap. Jika pengecualian berlaku, semua yang anda perlu lakukan ialah mengarahkan pemusnah untuk memadam pokok separuh siap. pengendali tugasanboleh dilaksanakan dengan mudah menggunakan Salin & Tukar.

Membuat pepohon carian binari

Pokok carian binari yang optimum adalah sangat cekap jika diuruskan dengan betul. Beberapa peraturan untuk pepohon carian binari:

1. Nod induk mempunyai paling banyak 2 nod anak.
2. Nod anak kiri sentiasa kurang daripada nod induk.
3. Nod anak yang sah sentiasa lebih besar daripada atau sama dengan nod induk.

Susun atur yang akan digunakan untuk membina pepohon carian binari:

1. Susunsusunan integer asas tujuh nilai dalam susunan tidak diisih.
2. Nilai pertama dalam tatasusunan ialah 10, jadi langkah pertama dalam membina pepohon ialah mencipta 10 nod akar, seperti yang ditunjukkan di sini.
3. Dengan set nod akar, semua nilai lain akan menjadi anak nod ini. Merujuk kepada peraturan, langkah pertama yang perlu diambil untuk menambah 7 pada pokok ialah membandingkannya dengan nod akar.
4. Jika nilai 7 kurang daripada 10, ia akan menjadi nod anak kiri.
5. Jika nilai 7 lebih besar daripada atau sama dengan 10, ia akan bergerak ke kanan. Memandangkan 7 diketahui kurang daripada 10, ia ditetapkan sebagai nod anak kiri.
6. Lakukan perbandingan secara rekursif untuk setiap elemen.
7. Mengikut corak yang sama, lakukan perbandingan yang sama terhadap nilai ke-14 dalam tatasusunan.
8. Membandingkan nilai 14 dengan nod akar 10, mengetahui bahawa 14 adalah anak yang betul.
9. Berjalan melalui tatasusunan,sampai ke 20.
10. Mulakan dengan membandingkan tatasusunan dengan 10, yang mana lebih besar. Jadi bergerak ke kanan dan bandingkan dengan 14, dia berusia lebih 14 tahun dan tidak mempunyai anak di sebelah kanan.
11. Kini terdapat nilai 1. Mengikut corak yang sama seperti nilai lain, bandingkan 1 hingga 10, bergerak ke kiri dan bandingkan dengan 7 dan akhirnya ke 1 anak kiri nod ke-7.
12. Jika nilainya ialah 5, bandingkan dengan 10. Memandangkan 5 adalah kurang daripada 10, hantar ke kiri dan bandingkan dengan 7.
13. Mengetahui bahawa 5 adalah kurang daripada 7, teruskan ke bawah pokok dan bandingkan 5 dengan 1 nilai.
14. Jika 1 tidak mempunyai anak dan 5 lebih besar daripada 1, maka 5 ialah anak yang sah daripada 1 nod.
15. Akhir sekali masukkan nilai 8 ke dalam pepohon.
16. Apabila 8 kurang daripada 10, gerakkannya ke kiri dan bandingkan dengan 7, 8 lebih besar daripada 7, jadi gerakkannya ke kanan dan lengkapkan pokok itu, jadikan 8 anak 7 yang betul.

Mendapatkan dan menilai keanggunan ringkas pepohon carian binari optimum. Seperti kebanyakan topik dalam pengaturcaraan, kuasa pepohon carian binari datang daripada keupayaan mereka untuk menyelesaikan data kepada komponen kecil yang berkaitan. Mulai sekarang, anda boleh bekerja dengan set data penuh dengan cara yang teratur.

Isu Carian Perduaan Berpotensi

Pokok carian binari bagus, tetapi terdapat beberapa kaveat yang perlu diingat. Mereka biasanya hanya berkesan jika ia seimbang. Pokok yang seimbang ialah pokok yang di dalamnyaperbezaan antara ketinggian subpokok mana-mana nod dalam pokok adalah paling banyak satu. Mari lihat contoh yang mungkin membantu menjelaskan peraturan. Mari bayangkan tatasusunan bermula sebagai boleh disusun.

Jika anda cuba menjalankan algoritma pepohon carian binari pada pepohon ini, ia akan berprestasi sama seperti ia hanya berulang melalui tatasusunan sehingga nilai yang dikehendaki ditemui. Kuasa carian binari terletak pada keupayaan untuk menapis nilai yang tidak diingini dengan cepat. Apabila pokok tidak seimbang, ia tidak akan memberikan manfaat yang sama seperti pokok yang seimbang.

Adalah sangat penting untuk memeriksa data yang digunakan oleh pengguna semasa membuat pepohon carian binari. Anda boleh menyepadukan rutin seperti rawak tatasusunan sebelum melaksanakan pepohon carian binari untuk integer mengimbanginya.

Contoh pengiraan carian binari

Kita perlu menentukan jenis pokok yang akan terhasil jika 25 dimasukkan ke dalam pepohon carian binari berikut:

10

/

/

5 15

/ /

/ /

2 12 20

Apabila memasukkan x ke dalam pokok T yang belum mengandungi x, kunci x sentiasa diletakkan di dalam daun baru. Sehubungan dengan ini, pokok baharu akan kelihatan seperti:

10

/

/

5 15

/ /

/ /

2 12 20

25

Apakah jenis pokok yang anda akan dapat jika anda memasukkan 7 ke dalam pepohon carian binari berikut?

10

/

/

5 15

/ /

/ /

2 12 20

Jawapan:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

Pokok carian binari boleh digunakan untuk menyimpan sebarang objek. Kelebihan menggunakan pepohon carian binari dan bukannya senarai terpaut ialah jika pepohon itu seimbang secara munasabah dan lebih seperti pepohon "penuh" daripada pepohon "linear", penyisipan, carian dan semua operasi pemadaman boleh dilaksanakan untuk dijalankan dalam Masa O(log N).