Pohon Biner Lengkap vs Pohon Biner Penuh
Pohon biner adalah pohon dimana setiap simpul memiliki satu atau dua anak. Dalam pohon biner, sebuah simpul tidak boleh memiliki lebih dari dua anak. Dalam pohon biner, anak diberi nama sebagai anak "kiri" dan "kanan". Node anak berisi referensi ke induknya. Pohon biner lengkap adalah pohon biner di mana setiap tingkat pohon biner terisi lengkap kecuali tingkat terakhir. Pada tingkat tidak terisi, node dipasang mulai dari posisi paling kiri. Pohon biner penuh adalah pohon di mana setiap simpul pada pohon memiliki dua anak kecuali daun pohon.
Apa itu Pohon Biner Penuh?
Pohon biner penuh adalah pohon biner di mana setiap simpul di pohon memiliki tepat nol atau dua anak. Dengan kata lain, setiap simpul di pohon kecuali daunnya memiliki tepat dua anak. Gambar 1 di bawah ini menggambarkan pohon biner penuh. Dalam pohon biner penuh, jumlah node (n), jumlah laves (l) dan jumlah node internal (i) terkait dengan cara khusus sehingga jika Anda mengetahui salah satu dari mereka, Anda dapat menentukan dua lainnya nilai sebagai berikut:
1. Jika pohon biner penuh memiliki i node internal:
- Jumlah daun l = i + 1
- Jumlah total node n = 2 * i + 1
2. Jika pohon biner penuh memiliki n node:
- Jumlah node internal i = (n-1) / 2
- Jumlah daun l = (n + 1) / 2
3. Jika pohon biner penuh memiliki l daun:
- Jumlah Total node n = 2 * l-1
- Jumlah node internal i = l-1
Apa itu Pohon Biner Lengkap?
Seperti yang ditunjukkan pada gambar 2, pohon biner lengkap adalah pohon biner di mana setiap tingkat pohon terisi lengkap kecuali tingkat terakhir. Selain itu, di level terakhir, node harus dipasang mulai dari posisi paling kiri. Pohon biner lengkap dengan tinggi h memenuhi ketentuan berikut:
- Dari simpul akar, tingkat di atas tingkat terakhir mewakili pohon biner penuh dengan tinggi h-1
- Satu atau lebih node di level terakhir mungkin memiliki 0 atau 1 turunan
- Jika a, b adalah dua node pada level di atas level terakhir, maka a memiliki lebih banyak turunan dari b jika dan hanya jika a terletak di kiri b
Apa perbedaan antara Complete Binary Tree dan Full Binary Tree?
Pohon biner lengkap dan pohon biner penuh memiliki perbedaan yang jelas. Sementara pohon biner penuh adalah pohon biner di mana setiap simpul memiliki nol atau dua anak, pohon biner lengkap adalah pohon biner di mana setiap tingkat pohon biner terisi lengkap kecuali tingkat terakhir. Beberapa struktur data khusus seperti heap harus berupa pohon biner lengkap sementara tidak perlu berupa pohon biner penuh. Dalam pohon biner penuh, jika Anda mengetahui jumlah total node atau jumlah laves atau jumlah node internal, Anda dapat menemukan dua lainnya dengan sangat mudah. Tetapi pohon biner lengkap tidak memiliki properti khusus yang menghubungkan ketiga atribut ini.
