Disyorkan, 2024

Pilihan Editor

Perbezaan Antara B-pokok dan pokok Perduaan

B-pokok dan pokok binari adalah jenis struktur data bukan linear. Walaupun istilah itu seakan sama tetapi berbeza dalam semua aspek. Pokok binari digunakan apabila rekod atau data disimpan dalam RAM bukan cakera kerana kelajuan akses RAM lebih tinggi daripada cakera. Sebaliknya, B-tree digunakan apabila data disimpan dalam cakera ia mengurangkan masa akses dengan mengurangkan ketinggian pokok dan meningkatkan cawangan di nod.

Satu lagi perbezaan di antara pokok B dan pokok binari adalah bahawa B-tree mesti mempunyai semua nod anaknya pada tahap yang sama manakala pokok binari tidak mempunyai kekangan tersebut. Pokok binari boleh mempunyai maksimum 2 subtrees atau nod sedangkan dalam B-tree boleh mempunyai M tidak subtrees atau nodes di mana M adalah susunan B-tree.

Carta Perbandingan

Asas untuk perbandingan
B-pokok
Pokok binary
Kekangan yang pentingNode boleh mempunyai bilangan maksima nod kanak-kanak (di mana M adalah susunan pokok).Node boleh mempunyai maksima 2 bilangan subtrees.
Digunakan
Ia digunakan apabila data disimpan pada cakera.Ia digunakan apabila rekod dan data disimpan dalam RAM.
Ketinggian pokoklog M N (di mana m adalah susunan pokok M-way)log 2 N
PermohonanStruktur data pengindeksan kod dalam banyak DBMS.Pengoptimuman kod, pengekodan Huffman, dll.

Definisi B-tree

Pokok B adalah pokok M-way yang seimbang dan juga dikenali sebagai pokok semulajadi seimbang. Ia sama dengan pokok carian binari di mana nod-molekinya diorganisasikan atas dasar inorder traversal. Kerumitan ruang pokok B ialah O (n). Kerumitan dan kerumitan masa pemadaman adalah O (log n).

Terdapat syarat-syarat tertentu yang mesti benar untuk pokok B:

  • Ketinggian pokok mesti terletak sekurang-kurangnya mungkin.
  • Di atas daun pokok itu, tidak ada mana-mana pokok kosong.
  • Daun pokok mesti datang pada tahap yang sama.
  • Semua nod harus mempunyai bilangan anak yang paling sedikit kecuali meninggalkan nod.

Sifat-sifat pokok B-order M

  • Setiap nod boleh mempunyai bilangan anak M maksimum dan bilangan anak M / 2 minimum atau mana-mana nombor dari 2 hingga maksimum.
  • Setiap nod mempunyai satu kunci kurang daripada kanak-kanak dengan kekunci M-1 maksimum.
  • Susunan kekunci adalah dalam beberapa susunan khusus dalam nod. Semua kekunci dalam subtree yang terdapat di sebelah kiri kekunci adalah pendahulu kunci, dan yang hadir di sebelah kanan kekunci dipanggil pengganti.
  • Pada masa memasukkan nod penuh, pokok itu berpecah kepada dua bahagian, dan kunci dengan nilai median dimasukkan pada nod induk.
  • Penggabungan operasi berlaku apabila nod dihapuskan.

Takrifan pokok binari

Pokok binari adalah struktur pokok yang boleh mempunyai paling banyak dua petunjuk untuk nod anaknya. Ini bermakna bahawa ijazah tertinggi nod boleh mempunyai adalah 2 dan boleh ada sifar atau nada satu darjah juga.

Terdapat beberapa jenis pokok perduaan seperti pokok binari yang ketat, pokok binari yang lengkap, pokok binari yang dilanjutkan, dan lain-lain.

  • Pokok binari yang ketat adalah pokok di mana setiap nod bukan terminal mesti meninggalkan subtree dan subtree kanan.
  • Pokok dipanggil pokok binari lengkap apabila ia memenuhi syarat mempunyai 2 nod di setiap peringkat di mana saya adalah tahap.
  • Binari yang diulirkan adalah pokok binari yang terdiri daripada 0 tidak ada nod atau 2 bilangan nod.

Teknik Traversal

Traversal pokok adalah salah satu operasi paling kerap dilakukan pada struktur data pokok di mana setiap node dilawati sekali sekali secara sistematik.

  • Inorder - Dalam pokok ini, subtree kiri dilawati secara rekursif kemudian nod akar dilawati dan subtree kanan yang terakhir dikunjungi.
  • Preorer- Dalam pokok ini, traversal nod akar dikunjungi pada subtree pertama dan kiri dan pada subtree kanan yang terakhir.
  • Postorder- Teknik ini melawat kiri subtree kemudian subtree kanan dan nod root terakhir.

Perbezaan Utama Antara B-pohon dan pokok Perduaan

  1. Dalam B-tree, bilangan maksimum nod kanak-kanak yang nod bukan terminal adalah M di mana M ialah susunan B-tree. Sebaliknya, pokok perduaan boleh mempunyai paling banyak dua subtrees atau nod kanak-kanak.
  2. B-pohon digunakan apabila data disimpan dalam cakera manakala pokok binari digunakan apabila data disimpan dalam memori pantas seperti RAM.
  3. Satu lagi bidang aplikasi untuk B-tree ialah struktur data pengindeksan kod dalam DBMS, sebaliknya, pokok binari digunakan dalam pengoptimuman kod, pengekodan huffman, dll.
  4. Ketinggian maksimum pokok B adalah log M N (M adalah urutan pokok). Sebaliknya, ketinggian maksimum pokok perdu adalah log 2 N (N adalah bilangan nod dan pangkalan adalah 2 kerana ia adalah untuk binari).

Kesimpulannya

Pohon B-digunakan di atas pokok carian perduaan dan binari sebab utama di sebalik ini ialah hierarki memori di mana CPU disambungkan ke cache dengan saluran jalur lebar yang tinggi manakala CPU disambungkan ke cakera melalui saluran lebar jalur rendah. Pokok binari digunakan apabila rekod disimpan dalam RAM (kecil dan cepat) dan B-pohon digunakan apabila rekod disimpan dalam cakera (besar dan perlahan). Jadi, penggunaan B-tree bukannya pokok binari dengan ketara mengurangkan masa akses kerana faktor cawangan yang tinggi dan ketinggian pokok yang berkurangan.

Top