Pertemuan 4 - Introduction to Tree, Binary Tree And Expression Tree

Introduction to Tree,
Binary Tree And Expression Tree

KONSEP TREE

Tree yaitu kumpulan dari satu atau beberapa node.

        Dari contoh gambar di atas, dapat disimpulkan :

ü  Degree dari tree =3

ü  Heigth =3

ü  Degree dari C =2

ü  Parent dari C = A

ü  Children dari A = B, C, D

ü  Sibling dari F = G

ü  Ancestor dari F = C, A

ü  Descendant dari C = F,G

• Node (simpul) yang paling atas disebut root (akar). 
• Garis yang menghubungkan parent (orang tua) ke child (anak) adalah edge.
• Node yang tidak memiliki chlid disebut leaf (daun).
• Node yang memiliki parent yang sama disebut sibling (saudara).
• Degree (derajad) dari sebuah node adalah total sub tree dari node tersebut.
• Height / depth (tinggi) adalah derajad maksimum dari node dalam tree tersebut.
• Jika ada garis yang menghubungkan p ke q, maka p disebut ancestor (nenek moyang) dari q, dan q adalah descendant(keturunan) dari p.

Beberapa jenis tree :
ü  Unary Tree (memiliki paling banyak 1 anak)
ü  Binary Tree (memiliki paling banyak 2 anak)
ü  Ternary Tree (memiliki banyak anak, lebih dari 2)

KONSEP BINARY TREE

Binary Tree adalah struktur data tree berakar di mana setiap node memiliki paling banyak dua anak. Kedua anak biasanya dibedakan sebagai anak kiri dan anak kanan.Node yang tidak memiliki setiap anak disebut daun.

     

      Sebuah sampel dari binary tree dari 9       node, berakar pada simpul yang berisi 18.

             Daun adalah node yang

             mengandung 9, 12, 10 dan 23.

TIPE – TIPE BINARY TREE

1.   




Perfect Binary Tree adalah sebuah pohon biner di mana setiap tingkat adalah pada kedalaman yang sama. Sesuai dengan namanya perfect yang berarti sempurna, memiliki bentuk yang sempurna.

2  Complete Binary Tree Sebuah pohon biner sempurna adalah sebuah pohon dengan biner yang lengkap. yang dimaksud lengkap yaitu memiliki jumlah node yang pas sampai pada node terakhir.

  

3.Skewed Binary Tree adalah pohon biner dimana setiap node memiliki paling banyak satu anak. Tree ini termasuk tree yang bentuknya berantakan, sehingga tak heran orang-orang menyebutnya juga sebagai unbalanced tree, karena bentuknya yang lebih menjorok ke satu sisi (kanan/kiri)

4. Balanced Binary Tree adalah pohon biner di mana tidak ada daun jauh lebih jauh dari akar daripada daun lainnya (skema balancing yang berbeda memungkinkan definisi yang berbeda dari "lebih jauh").

PROPERTY OF BINARY TREE

Jumlah maksimum node pada pohon biner dari ketinggian h adalah 2^h+1 - 1.

             node maksimum pohon biner tinggi 3
          = 1 + 2 + 4 + 8
          = 2⁰ + 2¹+ 2² + 2³
          = 2⁴-1
          = 15

   Tinggi minimum dari pohon biner dari n simpul adalah ²log(n).

   Tinggi maksimum pohon biner dari n simpul adalah n - 1.

     Skewed Binary Tree

     memiliki ketinggian maksimum

REPRESENT ATION OF BINARY TREE

 ü  Indeks pada array mewakili nomor simpul

ü  Indeks 0 adalah simpul Root

ü  Index Left Child adalah 2p + 1, di mana p adalah indeks induk

ü  Index Right Child adalah 2p + 2

ü  Induk Indeks adalah (p-1) / 2

EXPRESSION TREE CONCEPT

       Prefix  : *+ab/-cde

    

       Postfix : ab+cd-e/*

   

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

PERBEDAAN BINARY TREE DAN TREE

     Perlu diketahui bahwa binary tree dan tree itu berbeda, karena dalam membuat tree kita dapat membuat anak nya secara asal dengan menempatkan nya di kanan atau di kiri sesuai dengan yang kita mau, tetapi di binary tree ada sebuah aturan dimana jika nilai node yang akan di masukkan lebih kecil dari pada root maka akan di posisikan di kiri root, dan jika lebih besar maka akan di posisikan di kanan root, dan proses tersebut berlaku untuk setiap data yang akan di masukan ke dalam binary tree.

Pengecekan yang dilakukan binary tree di mulai selalu dari kiri, jadi kalau data di kiri sudah habis, maka dia baru pindah ke kanan.