bab 9 tree

Struktur Data - Tree 1

TREE (POHON)


Tujuan Pembelajaran

• Di akhir pembelajaran, peserta diharapkan memahami tentang :– Macam-macam jenis pohon (tree)– Mengetahui definisi & konsep pohon biner– Mengetahui representasi dari pohon biner– Mengenal heap, heapsort, & priority queue


Konsep Dasar & Terminologi

Level 0

Level 1

Level 2

Level 3

Node dalam/Internal node

Daun/Leaf

R

S T

X VU W

Y Z

Root/Akar

Gambar 1


Konsep & Terminologi

• Sebuah pohon terdiri atas kumpulan elemen atau node

• Tiap node dapat berisi data dan link (penghubung) ke node lainnya

• Tiap node memiliki satu induk, kecuali node root (akar) yang tidak memiliki induk.

• Tiap node dapat memiliki anak dalam jumlah berapapun.



• Node-node yang berasal dari induk yang sama disebut siblings

• Sebuah node yang tidak memiliki anak dinamakan leaf (daun)

• Secara umum, hubungan induk-anak diistilahkan dengan hubungan the ancestor-descendent



• Sebuah subtree (pohon anak) dari sebuah node adalah tree yang root-nya adalah anak dari node tsb.

• Level dari sebuah node adalah ukuran jarak node tersebut terhadap akar.

• Height (tinggi)/depth dari tree adalah level maksimum dari node yang terdapat di tree tsb.– Pohon kosong (empty tree) memiliki height=0


Konsep Dasar & Terminologi

• Secara umum, setiap node N dapat diurut dari root berdasarkan jalur (path) P.

• Jika path P memiliki n cabang (edge), maka dikatakan node N berada di level n

• Contoh path :– Dari R ke X : R – S – X, n=2, X ada di level 2– Dari R ke Z : R – S – X – Z, n=3, Z ada di

level 3


Pohon Biner (Binary Trees)

• Pada sebuah pohon biner, tiap node memiliki tepat 2 sub-pohon

• Sekelompok node T adalah sebuah binary tree jika :– T adalah pohon kosong– Root dari T memiliki 2 subpohon, TL dan TR,

dimana TL & TR adalah pohon biner


Pohon Biner (Binary Trees)

R

S T

X

W

U VY

Z

Gambar 2


Tipe-tipe Pohon Biner

• Pohon Ekspresi– Tiap node berisi operator atau operan

• Pohon Huffman– Merepresentasikan kode Huffman untuk karakter

yang bisa muncul pada file teks– Kode Huffman menggunakan angka-angka bit yang

berbeda dari ASCII atau Unicode

• Pohon Pencarian Biner (Binary Search Tree)– Semua elemen pada sub-pohon kiri mendahului

semua elemen pada sub-pohon kanan


Pohon Ekspresi

Pohon Ekspresi


Pohon Huffman


Pohon Pencarian Biner


Full Binary Tree

• Sebuah pohon biner penuh adalah pohon biner yang tiap node nya memiliki nol atau dua anak


Perfect Binary Tree

• Sebuah pohon biner dikatakan sempurna (perfect) jika pohon biner tsb merupakan pohon biner penuh dan semua node daun berada di level yang sama.

• Secara rekursif, sebuah pohon biner sempurna jika : – Merupakan pohon biner kosong, atau– Root nya memilik dua sub-pohon yang

sempurna dengan tinggi yang sama


Complete Binary Tree

• Definisi :– Pohon biner level N dikatakan sebuah komplit

jika seluruh node pada level N-1 terisi seluruhnya dan pada level N node yang kosong adalah node kanan.


Complete Binary Tree

H

D K

B F J L

A C E G I

Gambar 4Representasi


Incomplete Binary Tree

Gambar 5 Gambar 6


Kunjungan Pohon (Tree Traversals)

• Kunjungan pohon digunakan untuk menelusuri keberadaan node pada pohon

• Tiga jenis kunjungan pohon :– In-order– Pre-order– Post-order



• Preorder: Visit root node, traverse TL, traverse TR

• Inorder: Traverse TL, visit root node, traverse TR

• Postorder: Traverse TL, Traverse TR, visit root node


Visualisasi Kunjungan Pohon


Representasi Pohon Biner

• Pohon biner dapat direpresentasikan dalam 2 model :

1. Representasi berurutan (sequential representation)

2. Representasi berkait (linked representation)


Representasi Berurutan

H D K B F J L A C E G I

Representasi berurutan dari gambar 4 :

0 1 2 3 4 5 6 7 8 9 10 11

Gambar 7


Akses Elemen

• Posisi node dapat ditentukan berdasarkan rumus berikut :– Anak kiri dari node i berada pada indeks :

2*i+1– Anak kanan dari node i berada pada indeks :

2*i+2


Representasi Berkait


Heap Tree

• Definisi :– Heap tree adalah pohon biner komplit yang

tiap node nya memenuhi heap property.

• Heap Property :

– Nilai pada node > atau >= nilai semua node anaknya


Heap Tree

12

8 3

12

8 12

Node 12 memiliki properti heap

12

8 14

Node 12 tidak memiliki properti heap

Node 12 memiliki properti heap


siftUp• Diberikan sebuah node yang tidak memiliki heap

property. Maka yang bisa dilakukan adalah menukar posisi dengan node anak yang nilainya paling besar.

• Proses ini disebut juga sifting up• Bisa terjadi, node anak yang baru kehilangan heap

property

14

8 12

Blue node has heap property

12

8 14

Blue node does not have heap property


Langkah Membangun Heap (I)• Sebuah pohon yang berisi satu node adalah

heap tree.

• Cara menyusun heap adalah dengan menambahkan satu node tiap saat dengan aturan sbb :– Tambahkan node baru di posisi paling kiri di level

terbawah– Jika level terbawah penuh, buat level baru


Contoh

Add a new node here

Add a new node here

Contoh 1

Contoh 2


Langkah Membangun Heap (II)

• Setiap penambahkan node, mungkin menyebabkan node induk kehilangan heap property.– Solusi sift up

• Proses sift up ini dilakukan berulang kali hingga :– Node berada di posisi yang tepat dalam arti nilai node

tsb masih lebih kecil daripada node induknya, atau– Prosesnya telah sampai pada node root


• ...Dan seterusnya, hapus dan ganti root• Ingat, elemen terakhir array selalu berubah• Ulangi sampai elemen terakhir adalah elemen

pertama & array sudah terurut

22 22 17 19 21 14 15 18 14 11 3 9 25

0 1 2 3 4 5 6 7 8 9 10 11 12

9 22 17 19 22 14 15 18 14 21 3 22 25

0 1 2 3 4 5 6 7 8 9 10 11 12


Red-Black Tree

• Red-black tree adalah binary search tree yang memenuhi properti sbb :– Setiap node adalah red atau black– Node root adalah black– Setiap daun adalah black– Semua anak dari node red adalah black– Setiap jalur (path) dari sebuah node ke daun

berisi node black yang jumlahnya sama


Contoh Red-Black Tree

bab 9 tree

Documents