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 penting | Node 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 pokok | log M N (di mana m adalah susunan pokok M-way) | log 2 N |
| Permohonan | Struktur 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
- 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.
- B-pohon digunakan apabila data disimpan dalam cakera manakala pokok binari digunakan apabila data disimpan dalam memori pantas seperti RAM.
- Satu lagi bidang aplikasi untuk B-tree ialah struktur data pengindeksan kod dalam DBMS, sebaliknya, pokok binari digunakan dalam pengoptimuman kod, pengekodan huffman, dll.
- 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.
