bab 10 tree_lanjutan
TRANSCRIPT
Tree Lanjutan
Kunjungan Pohon (Tree Traversal)
• Tree traversal adalah bagaimana mengunjungi node-node pada pohon biner
• 3 Cara Kunjungan Pohon :– Pre-order– In-order– Post-order
Pre-Order Traversal
• Pre-order traversal1. Cetak data pada root
2. Secara rekursif mencetak seluruh data pada subpohon kiri
3. Secara rekursif mencetak seluruh data pada subpohon kanan
In-Order Traversal
• In-order traversal1.Secara rekursif mencetak seluruh data pada
subpohon kiri
2.Cetak data pada root
3.Secara rekursif mencetak seluruh data pada subpohon kanan
Post-order Traversal
• Post-order traversal1.Secara rekursif mencetak seluruh data pada
subpohon kiri
2.Secara rekursif mencetak seluruh data pada subpohon kanan
3.Cetak data pada root
Contoh : Pohon Ekspresi
Pre-Order, Post-Order, In-Order
• Pre-order :– Node, left, right– Ekspresi Prefix : ++a*bc*+*defg
• Post-order :– Node, left, right– Ekspresi Postfix : abc*+de*f+g*+
• In-order :– Node, left, right– Ekspresi Infix : a+b*c+d*e+f*g
Algoritma Preorder
Algoritma Postorder
Algoritma Inorder
Binary Search Tree
• Properti Binary Search Tree :– Untuk setiap node X, semua elemen di
subpohon kirinya bernilai lebih kecil dari nilai X dan semua elemen di subpohon kanannya bernilai lebih besar dari nilai X.
Contoh
Binary Search Tree Bukan Binary Search Tree
Pencarian pada BST
• Jika mencari elemen bernilai 15, maka akan langsung ditemukan.
• Jika mencari elemen bernilai < 15, maka kita cari di subpohon kiri.
• Jika mencari elemen bernilai > 15, maka kita cari di subpohon kanan.
Inorder traversal thd BST
• Mencetak semua elemen pada BST
Inorder: 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20
findMin/ findMax
• findMin : mengembalikan node dengan elemen terkecil pada BST
• Pencarian dimulai dari root dan bergerak ke kiri terus sepanjang subpohon kiri dan berhenti pada elemen terakhir.
• Proses serupa terhadap metode findMax
Insert• Dimulai dengan
penelusuran dari root untuk mencari posisi yang tepat.
• Jika elemen X ditemukan (berarti X sudah ada di BST), maka tidak perlu melakukan aksi apapun.
• Jika tidak, maka letakkan X sebagai node terakhir pada jalur penelusuran
• Time complexity = O(height of the tree)
Delete
• Saat akan menghapus sebuah node, kita juga harus memikirkan seluruh node anak dari node tsb.– Hal penting adalah agar pohon setelah
dihapus tetap merupakan BST.
DeleteTerdapat 3 kasus pada penghapusan :
(1) Node yang dihapus adalah daun– Langsung dihapus
(2) Node yang dihapus hanya punya 1 anak– Arahkan pointer (buat cabang baru) dari induk node
langsung ke anaknya
Delete (Kasus 2)
Delete(3) Node yang dihapus punya 2 anak
– Ganti nilai dari node yang dihapus dengan nilai terkecil dari subpohon kanannya
– Delete element terkecil
Delete (Kasus 3)
– Proses penghapusan dapat menyebabkan terulangnya 3 kasus di atas.
AVL Tree
• AVL Properti :– Sebuah node memiliki AVL property jika height (tinggi) subpohon kiri & subpohon kanan node tsb sama atau berbeda 1.
– Height (tinggi) pohon adalah jarak dari root menuju daun terbawah yang dimiliki pohon tsb
• AVL Tree adalah pohon yang setiap node nya memiliki AVL property
AVL Tree