Perbedaan lain antara pohon-B dan pohon biner adalah bahwa pohon-B harus memiliki semua simpul anaknya pada tingkat yang sama sedangkan pohon biner tidak memiliki kendala seperti itu. Pohon biner dapat memiliki maksimum 2 subtree atau node sedangkan di B-tree dapat memiliki M no dari subtree atau node di mana M adalah urutan B-tree.
Grafik perbandingan
| Dasar untuk perbandingan | B-tree | Pohon biner |
|---|---|---|
| Kendala penting | Sebuah node dapat memiliki jumlah M child node maksimal (di mana M adalah urutan pohon). | Sebuah node dapat memiliki maksimal 2 jumlah subtree. |
| Bekas | Ini digunakan ketika data disimpan pada disk. | Ini digunakan ketika catatan dan data disimpan dalam RAM. |
| Tinggi pohon | log M N (di mana m adalah urutan pohon M-way) | log 2 N |
| Aplikasi | Struktur pengindeksan kode data dalam banyak DBMS. | Pengoptimalan kode, pengodean Huffman, dll. |
Definisi B-tree
B-tree adalah pohon M-way seimbang dan juga dikenal sebagai pohon sortir seimbang. Ini mirip dengan pohon pencarian biner di mana node diatur berdasarkan inorder traversal. Kompleksitas ruang B-tree adalah O (n). Penyisipan dan kompleksitas waktu penghapusan adalah O (log n).
Ada kondisi tertentu yang harus benar untuk pohon-B:
- Tinggi pohon harus seminimal mungkin.
- Di atas dedaunan pohon, seharusnya tidak ada sub pohon kosong.
- Daun pohon harus berada pada tingkat yang sama.
- Semua node harus memiliki jumlah anak paling sedikit kecuali meninggalkan node.
Properti B-tree of order M
- Setiap simpul dapat memiliki jumlah M maksimum anak-anak dan jumlah minimum M / 2 anak-anak atau jumlah dari 2 hingga maksimum.
- Setiap simpul memiliki satu kunci kurang dari anak-anak dengan kunci M-1 maksimum.
- Susunan tombol berada dalam urutan tertentu dalam node. Semua kunci pada subtree yang ada di sebelah kiri kunci adalah pendahulu kunci, dan yang ada di kanan kunci disebut penerus.
- Pada saat penyisipan simpul penuh, pohon terbagi menjadi dua bagian, dan kunci dengan nilai median dimasukkan pada simpul induk.
- Operasi penggabungan terjadi ketika node dihapus.
Definisi pohon biner
Binary tree adalah struktur pohon yang dapat memiliki paling banyak dua pointer untuk simpul anaknya. Ini berarti bahwa derajat tertinggi yang dimiliki sebuah simpul adalah 2 dan bisa juga ada simpul nol atau satu derajat.
Ada varian tertentu dari pohon biner seperti pohon biner ketat, pohon biner lengkap, pohon biner diperpanjang, dll.
- Pohon biner ketat adalah pohon di mana setiap node non-terminal harus memiliki subtree kiri dan subtree kanan.
- Sebuah pohon disebut pohon Biner Lengkap ketika memenuhi syarat memiliki 2 i node pada setiap level di mana i adalah level.
- Biner berulir adalah pohon biner yang terdiri dari 0 no node atau 2 jumlah node.
Teknik Traversal
Tree traversal adalah salah satu operasi yang paling sering dilakukan pada struktur data pohon di mana setiap node mengunjungi tepat sekali secara sistematis.
- Inorder- Dalam traversal pohon ini subtree kiri dikunjungi secara rekursif kemudian root node dikunjungi dan subtree kanan terakhir dikunjungi.
- Preorer- Dalam pohon ini melintasi simpul akar dikunjungi pada pertama kemudian ke kiri dan ke kanan lagi.
- Postorder- Teknik ini mengunjungi subtree kiri kemudian subtree kanan dan pada root node terakhir.
Perbedaan Kunci Antara B-tree dan Binary tree
- Dalam B-tree, jumlah maksimum simpul anak yang dapat dimiliki simpul non-terminal adalah M di mana M adalah urutan B-tree. Di sisi lain, pohon Binary dapat memiliki paling banyak dua sub pohon atau simpul anak.
- B-tree digunakan ketika data disimpan dalam disk sedangkan pohon biner digunakan ketika data disimpan dalam memori cepat seperti RAM.
- Area aplikasi lain untuk B-tree adalah struktur data pengindeksan kode dalam DBMS, sebaliknya, Binary tree digunakan dalam optimasi kode, huffman coding, dll.
- Ketinggian maksimum pohon-B adalah log M N (M adalah urutan pohon). Sebaliknya, tinggi maksimum pohon biner adalah log 2 N (N adalah jumlah node dan basis adalah 2 karena untuk biner).
Kesimpulan
B-tree digunakan lebih dari pohon pencarian biner dan biner alasan utama di balik ini adalah hirarki memori di mana CPU terhubung ke cache dengan saluran bandwidth tinggi sementara CPU terhubung ke disk melalui saluran bandwidth rendah. Pohon biner digunakan ketika catatan disimpan dalam RAM (kecil dan cepat) dan B-pohon digunakan ketika catatan disimpan dalam disk (besar dan lambat). Jadi, penggunaan B-tree sebagai pengganti Binary tree secara signifikan mengurangi waktu akses karena faktor percabangan yang tinggi dan berkurangnya tinggi pohon.
