Tree, Binary Tree & Expression Tree - 4th meeting

Regina

1901457321

Hari: Rabu, 23/03/2016

Kelas: CD01-CL

Lecturer: Rulyna ( D4689 ) dan Henry Chong ( D4460 )

Tree

Tree merupakan sekumpulan dari 1 node atau beberapa node yang terhubung oleh suatu garis yang disebut edge.

Degree of tree = 3

Degree of C = 2

Height = 3

Parent of C = A

Children of A = B,C,D

Sibling of F = G

Ancestor of F = A,C

Descendant of C = F,G 

• Node yang berada di paling atas disebut Root.
• Garis yang menghubungkan sebuah parent dengan child disebut Edge.
• Node yang tidak memiliki anak disebut Leaf.
• Node yang memiliki parent yang sama disebut Siblings.
• Degree dari suatu node adalah total dari sub tree sebuah node.
• Ketinggian / kedalaman merupakan maximum degree suatu node dalam tree.
• Jika ada garis yang menghubungkan p ke q, maka p = Ancestor dari q dan q = Descendant dari.

Binary Tree

Binary tree adalah tree yang memiliki root/akar yang setiap nodenya memiliki paling banyak 2 anak. Anak yang berada di sebelah kiri disebut left child dan yang sebelah kanan disebut right child.  

Contoh dari Binary Tree

Dari gambar diatas, ada 9 node. Yang menjadi root merupakan node 18. node 9,12,10 dan 23 adalah leaf. Berikut adalah tipe-tipe dari Binary Tree:   

•  Perfect Binary Tree : Binary Tree yang setiap level nya berada di kedalaman yang sama. 

Masing-masing node memiliki anak, 2 anak atau tidak punya sama sekali. Dan tingkatannya/levelnya seimbang sehingga, disebut perfect binary tree.

• Complete Binary Tree

Complete binary tree dimana level/tingkatan binary tree, kecuali yang terakhir, terisi penuh.  Perfect binary tree dapat disebut juga complete binary tree karena tidak perlu ada node di tingkatan paling bawah.

• Skewed Binary Tree

Pada skewed binary tree, setiap node hanya mempunyai 1 anak.

•  Balanced Binary Tree : Jarak root ke leaf sama dengan jarak antara anak kanan dan kiri. 

Property of Binary Tree

·         Jumlah maksimum pada suatu node pada level k adalah 2k. K adalah level yang ingin dicari.

·         Jumlah maksimum suatu node pada ketinggian (h) dari binary tree adalah 2k+1 - 1.

Contoh: maksimum node dari binary tree pada ketinggian ke-3

= 1 + 2 + 4 + 8

= 2⁰ + 2¹ + 2² + 2³

= 2⁴ – 1

= 15

• Tinggi minimum sebuah node (n) dari binay tree adalah ²log(n).
• Tinggi maksimum sebuah node (n) dari binay tree adalah n-1.

Skewed binary tree juga memiliki tinggi maksimum.

Representation of Binary Tree

1.       Implementation using array

Index 0 = root node

Index left child = 2p+1

Index right child = 2p+2

Index parent = (p-1)/2

p.s p = parent index

contoh:

Mencari right child dari C.

Right child C = 2p+2.

P dari C = 2

= 2*2+2

= 4+2

= 6 ß index right child dari C

2.       Implementation using linked list

Expression Tree

Membuat expression tree dengan prefix dan postfix dengan menggunakan rekursif.

• Infix = Left Print Right
• Prefix = Print Left Right
• Postfix = Left Right Print

Contoh:

Infix = (a+b)*((c-d)/e)

Prefix = *+ab/-cde

Postfix = ab+cd-e/*