My first Magazine pemrograman-kompetitif-dasar | Page 102

9 Perkenalan Graf
Perfect Binary Tree
Suatu binary tree yang seluruh node -nya memiliki 2 anak, kecuali tingkat paling bawah yang
tidak memiliki anak, disebut dengan perfect binary Tree. Bila banyaknya node adalah N, maka
ketinggian dari pohon tersebut adalah O(log N).
Gambar 9.8: Contoh perfect binary tree.
Complete Binary Tree
Complete binary tree adalah binary tree yang mana semua posisi node di setiap kedala-
mannya terisi, kecuali mungkin pada kedalaman terbawah, dan posisi node -nya terisi dengan
urutan kiri ke kanan. Sama seperti perfect binary Tree, bila banyaknya node adalah N, maka
ketinggiannya adalah O(log N). Contoh dari complete binary tree dapat dilihat pada gambar 9.9,
sementara kedua tree pada gambar 9.10 bukanlah termasuk complete binary tree.
Gambar 9.9: Contoh complete binary tree.
(a)
(b)
Gambar 9.10: Contoh tree yang bukan complete binary tree. Tree (a) bukanlah complete binary
tree sebab elemen di tingkat paling bawah tidak berisi dari kiri ke kanan (terdapat
lubang). Tree (b) juga bukan complete binary tree, sebab terdapat node tanpa 2
anak pada tingkat bukan paling bawah.
II Sekilas Info JJ
Complete binary tree dimanfaatkan pada struktur data binary heap . Struktur data ini akan
kita pelajari pada bab Struktur Data NonLinear.
92