TREE

GENERAL TREE

Definisi Pohon (Tree)
Struktur pohon merupakan kumpulan elemen yang salah satu elemennya disebut akar dan sisa elemenya terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama lainnya yang disebut cabang.

Simpul / node adalah elemen pohon yang berisi informasi atau data dan penunjuk percabangan.

Node root (akar) adalah node yang berada di pangkal tree.

Node leaf (daun) adalah node yang berada paling ujung pada piramida tree.

BINARY TREE, REPRESENTASI DARI BINARY TREE DAN TRAVERSAL

Binary Tree

Pohon biner (Binary tree) bisa didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau mempunyai akar dan subpohon yang saling terpisah yang disebut dengan subpohon kiri (left subtree) dan sub pohon kanan (right tree).

Karakteristik pohon biner yaitu: 

• Setiap simpul paling banyak hanya mempunyai dua buah anak 
• Derajat tertinggi dari simpul dalam pohon biner adalah dua 
• Banyaknya simpul maksimum pada tingkat 2^n.
• Dalam pohon biner dimungkinkan tidak mempunyai simpul.

Representasi dari Binary Tree

Algoritma untuk merubah General Tree menjadi Binary tree:

• Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang menghubungkan parent dengan child-nya kecuali edge yang paling kiri.
• Rotasi 45 derajat sedemikian sehingga dibedakan subtree kiri dan kanan.

Contoh:

Algoritma untuk merubah Forest menjadi Binary tree: 

• Insert edge-edge yang menghubungkan sibling (saudara) kemudian delete semua edge yang menghubungkan parent dengan child-nya kecuali edge yang paling kiri 
• Tree-tree yang lain dihitung sebagai satu level

Contoh:

 

Traversal

Traversal pohon biner adalah proses mendatangi setiap simpul dari pohon secara sistematik masing-masing satu kali dimana pada setiap simpul yang dikunjungi dilakukan suatu proses pengolahan data.

Ada 3 cara traversal: 

• Traversal postorder (LRS)

Proses pertama kali bergerak kearah subpohon bagian kiri, selanjutnya subpohon sebelah kanan dan terakhir simpul (simpul root) 

• Traversal inorder (LSR)

Proses dimulai dari subpohon sebelah kiri selanjutnya simpul root dan selanjutnya subpohon sebelah kanan 

• Traversal preorder (SLR)

Proses dimulai dari simpul root kearah subpohon kiri, selanjutnya bergerak ke subpohon kanan

S= proses mengunjungi simpul
L= bergerak kearah subpohon bagian kiri
R= bergerak kearah subpohon bagian kanan

BALANCING BINARY SEARCH TREE

Suatu Binary Search Tree dari himpunan N record (N1,N2,N3....Nn) adalah suatu binary tree yang setiap vertex-nya (sebut Ri) ditempati oleh Ni untuk i=1,2,3....N

Vertex-vertex dari Binary Tree tsb. Diatur sedemikian rupa sehingga untuk Ri harus memenuhi syarat sbb: 

1. Jika Rj= left (Ri) maka Nj<Ni 
2. Jika Rj= right (Ri) maka Nj>Ni

Contoh : Diketahui key dari 7 record (K, M, L, N, P, O, Q)

Binary Search Tree dari 7 key diatas dapat dibentuk :

HEIGHT DAN BOUND BALANCED TREE

BALANCED TREE

Suatu Binary Tree dimana untuk setiap Root Ri berlaku struktur subtree kiri = struktur subtree kanan.

Contoh:

HEIGHT BALANCED TREE

Suatu Tree dimana untuk setiap Root Ri berlaku height dari subtree kanan dan height dari subtree kiri beda paling banyak satu

Height Balanced tree belum tentu Balanced Tree tapi Balanced Tree sudah pasti height balanced tree.

Terima Kasih, semoga bermanfaat