Perbezaan antara pokok binari dan pokok carian binari

Apa itu pokok binari?

Pokok binari adalah struktur data hierarki di mana setiap nod mempunyai sifar, satu, atau paling banyak, dua anak. Setiap nod mengandungi penunjuk "kiri", penunjuk "kanan", dan elemen data. Penunjuk "root" mewakili nod paling atas di dalam pokok. Setiap nod dalam struktur data disambungkan secara langsung kepada bilangan nod sewenang -wenang di kedua -dua belah pihak, yang disebut sebagai kanak -kanak. Penunjuk null mewakili pokok binari. Tidak ada perintah tertentu bagaimana nod akan dianjurkan di pokok binari. Nod tanpa nod kanak -kanak dipanggil nod daun, atau nod luaran.

Secara ringkas, ia mentakrifkan fungsi pelabelan yang teratur pada nod, yang seterusnya memberikan nilai rawak kepada setiap nod. Apa sahaja yang mempunyai dua anak dan satu nod induk adalah pokok binari. Pokok binari digunakan untuk menyimpan maklumat yang membentuk hierarki seperti sistem fail di komputer peribadi anda. Tidak seperti array, pokok tidak mempunyai had atas bilangan nod kerana ia dihubungkan menggunakan petunjuk, seperti senarai yang dipautkan. Fungsi utama pokok binari termasuk mewakili data hierarki, senarai data penyortiran, menyediakan operasi sisipan/padam yang cekap, dll. Nod pokok diwakili menggunakan struktur dalam c.

Apakah pokok carian binari?

Pokok carian binari adalah sejenis struktur data pokok binari di mana nod disusun mengikut urutan, oleh itu juga dipanggil sebagai "memerintahkan pokok binari". Ini adalah struktur data berasaskan nod yang menyediakan cara yang cekap dan cepat untuk menyusun, mengambil, mencari data. Untuk setiap nod, unsur -unsur di subtree kiri mestilah kurang daripada atau sama dengan kunci dalam nod induknya (LP). Tidak semestinya ada kunci pendua. Secara ringkas, ia adalah jenis struktur data pokok binari yang istimewa yang menyimpan dan menguruskan item dalam ingatan yang cekap.

Ia membolehkan akses maklumat, penyisipan dan penyingkiran data yang cepat, ditambah pula dengan ia boleh digunakan untuk melaksanakan jadual carian yang membolehkan mencari item dengan kunci unik mereka, seperti mencari nombor telefon seseorang dengan nama. Kekunci unik disusun dengan cara yang teratur, supaya pencarian dan operasi dinamik lain dapat dilakukan dengan menggunakan carian binari. Ia menyokong tiga operasi utama: mencari elemen, penyisipan elemen, dan penghapusan elemen. Pokok carian binari membolehkan pengambilan semula unsur -unsur yang disimpan di dalam pokok kerana setiap kekunci nod secara menyeluruh dibandingkan dengan nod akar, yang membuang separuh pokok.

Perbezaan antara pokok binari dan pokok carian binari

1. Definisi pokok binari dan pokok carian binari - Pokok binari adalah struktur data hierarki di mana kanak -kanak boleh mempunyai sifar, satu, atau maksimum dua nod kanak -kanak; Setiap nod mengandungi penunjuk kiri, penunjuk kanan dan elemen data. Tidak ada perintah tertentu bagaimana nod harus dianjurkan di dalam pokok itu. Pokok carian binari, sebaliknya, adalah pokok binari yang diperintahkan di mana terdapat perintah relatif bagaimana nod harus dianjurkan.
2. Struktur dari Pokok binari dan pokok carian binari- Nod paling atas di dalam pokok mewakili penunjuk akar di pokok binari, dan kiri dan petunjuk kanan mewakili pokok yang lebih kecil di kedua -dua belah pihak. Ini adalah bentuk pokok khusus yang mewakili data dalam struktur pokok. Pokok carian binari, sebaliknya, adalah sejenis pokok binari di mana semua nod di subtree kiri kurang daripada atau sama dengan nilai nod akar dan subtree kanan lebih besar daripada atau sama dengan nilai nod akar.
3. Operasi dari Pokok binari dan pokok carian binari- Pokok binari boleh menjadi apa sahaja yang mempunyai dua anak dan satu ibu bapa. Operasi biasa yang boleh dilakukan pada pokok binari adalah penyisipan, penghapusan, dan traversal. Pokok carian binari lebih banyak pokok binari yang disusun yang membolehkan pencarian, penyisipan, dan penghapusan yang cepat dan efisien. Tidak seperti pokok binari, pokok carian binari menyimpan kunci mereka disusun, jadi carian biasanya melaksanakan pencarian binari untuk operasi.
4. Jenis dari Pokok binari dan pokok carian binari- Terdapat pelbagai jenis pokok binari, yang biasa ialah "pokok binari penuh", "pokok binari lengkap", "pokok binari sempurna", dan "pokok binari yang dilanjutkan". Beberapa jenis pokok carian binari yang biasa termasuk pokok T, pokok avl, pokok splay, pokok tango, pokok merah-hitam dan lain-lain.

Pokok binari vs. Pokok carian binari: carta perbandingan

Ringkasan pokok binari dan pokok carian binari

Walaupun kedua -duanya mensimulasikan struktur pokok hierarki yang mewakili koleksi nod dengan setiap nod yang mewakili nilai, mereka agak berbeza antara satu sama lain dari segi cara mereka dapat dilaksanakan dan digunakan. Pokok binari mengikuti satu peraturan mudah bahawa setiap nod induk tidak mempunyai lebih daripada dua nod kanak.