Perbedaan Antara Pohon Biner Lengkap dan Pohon Biner Penuh

Pohon Biner Lengkap vs Pohon Biner Penuh

Pohon biner adalah pohon di mana setiap simpul memiliki satu atau dua anak. Dalam pohon biner, sebuah simpul tidak dapat memiliki lebih dari dua anak. Dalam pohon biner, anak-anak dinamai sebagai anak "kiri" dan "kanan". Node anak berisi referensi ke induknya. Pohon biner lengkap adalah pohon biner di mana setiap tingkat pohon biner terisi penuh kecuali tingkat terakhir. Pada 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 Binary Tree 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 daun (l) dan jumlah node internal (i) terkait dengan cara khusus sehingga jika Anda tahu 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

- Total jumlah 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 1 daun:

- Total Jumlah 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 diisi sepenuhnya kecuali tingkat terakhir. Juga, di level terakhir, node harus dilampirkan mulai dari posisi paling kiri. Pohon biner lengkap dengan ketinggian h memenuhi syarat-syarat berikut:

- Dari simpul akar, level di atas level terakhir mewakili pohon biner penuh dengan ketinggian h-1

- Satu atau lebih node di level terakhir mungkin memiliki 0 atau 1 anak

- Jika a, b adalah dua node pada level di atas level terakhir, maka a memiliki lebih banyak anak daripada b jika dan hanya jika a terletak di kiri b

Apa perbedaan antara Pohon Biner Lengkap dan Pohon Biner Lengkap?

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 diisi penuh kecuali tingkat terakhir. Beberapa struktur data khusus seperti tumpukan harus pohon biner lengkap sementara mereka tidak perlu pohon biner penuh. Dalam pohon biner penuh, jika Anda tahu jumlah total node atau jumlah daun atau jumlah internal node, Anda dapat menemukan dua lainnya dengan sangat mudah. Tetapi pohon biner yang lengkap tidak memiliki properti khusus yang menghubungkan tiga atribut ini.