Pohon Biner Lengkap vs Pohon Biner Penuh
Pohon biner adalah pohon yang setiap simpulnya memiliki satu atau dua anak. Dalam pohon biner, sebuah simpul tidak boleh memiliki lebih dari dua anak. Dalam pohon biner, anak-anak diberi nama sebagai anak-anak "kiri" dan "kanan". Node anak berisi referensi ke induknya. Pohon biner lengkap adalah pohon biner di mana setiap level pohon biner terisi penuh kecuali level terakhir. Di level yang tidak terisi, node dilampirkan mulai dari posisi paling kiri. Pohon biner penuh adalah pohon di mana setiap simpul di 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 daun memiliki tepat dua anak. Gambar 1 di bawah ini menggambarkan pohon biner penuh. Dalam pohon biner penuh, jumlah node (n), jumlah lave (l) dan jumlah node internal (i) terkait dengan cara khusus sehingga jika Anda mengetahui salah satunya, Anda dapat menentukan dua lainnya nilai sebagai berikut:
1. Jika pohon biner penuh memiliki i node internal:
– Jumlah daun l=i+1
– Jumlah node n=2i+1
2. Jika pohon biner penuh memiliki n node:
– Jumlah simpul internal i=(n-1)/2
– Jumlah daun l=(n+1)/2
3. Jika pohon biner penuh memiliki l daun:
– Jumlah Node n=2l-1
– Jumlah simpul internal i=l-1
Apa itu Pohon Biner Lengkap?
Seperti yang ditunjukkan pada gambar 2, pohon biner lengkap adalah pohon biner di mana setiap level pohon terisi penuh kecuali level terakhir. Juga, di level terakhir, node harus dilampirkan mulai dari posisi paling kiri. Pohon biner lengkap dengan tinggi h memenuhi kondisi berikut:
– Dari simpul akar, level di atas level terakhir mewakili pohon biner penuh dengan tinggi h-1
– Satu atau lebih node di level terakhir mungkin memiliki 0 atau 1 anak
– Jika a, b adalah dua simpul pada level di atas level terakhir, maka a memiliki lebih banyak anak daripada b jika dan hanya jika a terletak di sebelah kiri b
Apa perbedaan antara Pohon Biner Lengkap dan Pohon Biner Penuh?
Pohon biner lengkap dan pohon biner penuh memiliki perbedaan yang jelas. Sementara pohon biner penuh adalah pohon biner di mana setiap node memiliki nol atau dua anak, pohon biner lengkap adalah pohon biner di mana setiap level pohon biner terisi penuh kecuali level terakhir. Beberapa struktur data khusus seperti heaps harus berupa pohon biner lengkap sementara mereka tidak perlu berupa pohon biner penuh. Dalam pohon biner penuh, jika Anda mengetahui jumlah simpul total atau jumlah lave atau jumlah simpul internal, Anda dapat menemukan dua lainnya dengan sangat mudah. Tetapi pohon biner lengkap tidak memiliki properti khusus yang menghubungkan ketiga atribut ini.
