sd c 10 - · pdf fileby : sri rezeki candra nursari 2 sks. ... 9. avl tree 10. heap dan...

STRUKTUR DATA

By : Sri Rezeki Candra Nursari

2 SKS

Literatur

• Sjukani Moh., (2007), “Struktur Data (Algoritma & Struktur Data 2) dengan C, C++”, Mitra Wacana Media

• Utami Ema. dkk, (2007),”Struktur Data (Konsep & Implementasinya Dalam Bahasa C & Free Pascal di GNU/Linux)”, Graha Ilmu

• Hubbard Jhon, R., Ph.D, (2000), “Schaum’s Outline Of Theory and Problems of Data Structures With C++” McGraw-Hill

• Bambangworawan Paulus., (2004), “Struktur Data Dengan C”, Andi Yogyakarta

Materi1. Data dan Struktur Data2. Array3. Struktur dan Record4. Pointer5. Linked List6. Stack (Tumpukan)7. Queue (Antrian)8. Tree (Pohon)9. AVL Tree10. Heap dan B-Tree11. Sorting12. Search13. Hashing14. Graph

TREE - POHON

Pertemuan 10

2 SKS

Istilah Umum Dalam TREE

1. Tree (pohon) dan Graph (Graf)2. Simpul (Vertex, Node) dan Busur (Edge, Arc)3. Superordinat dan subordinat, father dan son,

parent dan children4. Root (akar) dan Leaf (daun)5. Level (tingkat) dan Depth (kedalaman)6. Degree (derajat) simpul dan degree pohon7. M-ary tree dan binary tree8. Link dan null-link

7a. M-ary Tree

• M atau K menyatakan derajat pohon• Contoh : sebuah simpul pohon M-ary

dimana M=3 digambarkan dengan Linked-List

INFO

Link1 Link2 Link3

7b. Binary Tree

• M atau K menyatakan derajat pohon• Contoh : sebuah simpul pohon Binary Tree /

Pohon Biner dimana M=2 digambarkan dengan Linked-List

INFO

Link1 Link2

Contoh Pohon Biner

A

B C

D E F G

H

8. Link, Null-Link dan Bukan Null-Link

• Link– Pointer yang digunakan untuk menunjuk simpul

subordinat– Untuk contoh pohon biner adalah setiapsimpul

mempynyai 2 link, sehingga jumlah link = n*2• Null-Link

– Link yang bernilai Null, yaitu link yang tidak menunjuk simpul subordinat

• Bukan Null-Link– Link yang menunjuk simpul subordinat atau link yang

menghubungkan dua buah simpul yang biasanya disebut dengan busur

Contoh Soal : M-ary

• Sebuah pohon M-ary dengan 10 buah simpul. Apabila M=3, Hitung berapa jumlah Null-Link nya?

Pohon dengan M = 3Jumlah simpul 10,

maka n = 10

Jumlah Null-Link = n * (M-1) + 1= 10 * (3-1) +1= 10*2+1= 21

A

B CD

E FG

H

J

I

Contoh Soal : Pohon Biner

• Sebuah pohon biner dengan 10 buah simpul. Apabila M=2, Hitung berapa jumlah Null-Link nya?

Pohon dengan M = 2Jumlah simpul 10,

maka n = 10

Jumlah Null-Link = n * (M-1) + 1= 10 * (2-1) +1= 10*1+1= 11

A

BC

D EH

F

IG

J

BINARY TREE – POHON BINER

POHON BINER / BINARY TREE

• Sebuah pohon biner/binary tree adalah merupakan himpunan terbatas yang – Mungkin kosong– Terdiri dari sebuah simpul yang disebut sebagai akar dan

dua buah himpunan lain yang saling asing– Dia humpunan yang saling asing tersebut adalah pohon

biner pada sub pohon kiri (left) dan sub pohon kanan (right)

– Tergolong dalam pohon beraturan, yaitu pohon yang memperhatikan urutan hubungan antara satu simpul dengan simpul lain, dalam hal ini cabang kiri dibedakan dengan cabang kanan

POHON BINER / BINARY TREE

• Merupakan pohon M-ary dimana M=2, yang artinya setiap simpul paling banyak memiliki 2 simpul subordinat yang biasa disebut subordinat kiri (left-child) dan subordinat kanan (right-child)

INFO

Left Right

INFO

Left Right

Father

POHON BINER / BINARY TREE

• Strictly Binary Tree merupakan pohon biner yang semua simpulnya, (kecuali simpul leaf/daun) mempunyai lengkap simpul subordinat kiri dan subordinat kanan

• Sebuah pohon biner strictlybinary tree, apabila mempunyai n buah daun, maka akan mempunyai (2n-1) buah simpul A

B C

D E F G

H I

Jumlah daun/leaf = 5

Jumlah simpul = 2 * n - 1= 2 * 5 - 1= 9

COMPLETE BINARY TREE/FULL BINARY TREE/ ALMOST COMPLETE BINARY TREE

• Complete Binary Tree dengan kedalaman = d, merupakan pohon biner strictly binary treedimana semua daun hanya berada pada level d

• Pada pohon complete binary tree/full binary tree/almost complete binary tree berlaku : – Pada leve k jumlah simpul n=2^k– Untuk pohon dengan kedalaman d, maka jumlah seluruh

simpul n = 2^(d+1)-1– Untuk pohon dengan kedalaman d, maka jumlah simpul

daun n = 2^d

COMPLETE BINARY TREE/FULL BINARY TREE/ ALMOST COMPLETE BINARY TREE

• Pada pohon complete binary tree/full binary tree/almost complete binary tree berlaku : – Untuk pohon dengan kedalaman d, maka jumlah simpul

bukan daun n = (2^d)-1– Bila jumlah seluruh simpul = n, maka kedalaman pohon

adalah d = log2(n+1)-1– Setiap simpul yang berada dibawah level d-1,

mempunyai dua subordinat– Bila pada level d-1 sub pohon kanan ada simpul yang

mempunyai subordinat, maka setiap simpul pada level d-1 subpohon kiri harus mempunyai subordinat kiri dan kanan

COMPLETE BINARY TREE/FULL BINARY TREE/ ALMOST COMPLETE BINARY TREE

Almost Complete Binary Tree dan BukanStrictly Binary Treekarena simpul G hanya punya satu anak

A

B C

D E F G

J KH I L M N

Almost Complete Binary Tree dan Strictly Binary Tree

A

B C

D E F G

J KH I L M N O

COMPLETE BINARY TREE/FULL BINARY TREE/ ALMOST COMPLETE BINARY TREE

Bukan Almost Complete Binary Treekarena simpul C hanya punya satu anak

A

B C

D E F

J KH I

Bukan Almost Complete Binary Tree

A

B C

D E F G

H

Almost Complete Binary Tree dan tapi bukan Strictly Binary Tree

A

B C

D E F G

H I L M

POHON BINER SEIMBANG –BALANCED BINARY TREE (AVL)

POHON BINER SEIMBANG - AVL

• AVL diambil dari nama G.M. Adelson-Velskii dan E.M. Landis, 2 orang ahli matematika Rusia yang pertama kali (1962) memperkenalkan metode untuk membuat pohon biner selalu seimbang

• Pohon Biner Seimbang / Berimbang adalah pohon biner yang ketinggian subpohon kiri dan subpohon kanan untuk setiap simpul superordinat, paling banyak berselisih 1

• Jadi pohon biner complete dan almost complete adalah pohon biner berimbang

• Pohon miring/skewed dengan ketinggian /depth lebih besar dari 1 adalah pohon biner tak seimbang

CONTOH : BALANCED BINARY TREE UNBALANCED BINARY TREE

Unbalanced Binary Tree

A

B C

D E F G

J KH I L M N

Balanced Binary Tree

A

B C

D E F G

J KH I L M N O

PENOMORAN SIMPUL POHON BINER

• Berdasarkan konversi dapat disepakati cara penomoran setiap simpul dalam pohon biner, yaitu:– Bila sebuah simpul bernomor n, maka subordinat kiri

bernomor 2n dan subordiat kanan bernomor 2n+1– Simpul akar, diberi nomor 1

A

B C

1

2 3A

B C

n

2n 2n+1G

H I

5

10 11

PENOMORAN SIMPUL POHON BINER

Level(k)

Maksimum jumlah simpul pada level2^k

Maksimum jumlah seluruh simpul sampai dengan level

2^(k+1)-1

0 1 1

1 2 3

2 4 7

3

4

5

6

7

8

9

10

BINARY TREE/POHON BINER

• Proses Pohon Biner (Binary Tree), adalah 1. Mendeklarasikan struktur simpul2. Inisialisasi3. Pembuatan sebuah simpul4. Pembuatan simpul akar5. Penambahan/melakukan insert simpul

baru kedalam sebuah pohon6. Pembacaan/penelusuran pohon biner

BINARY TREE/POHON BINER

• Proses Pohon Biner (Binary Tree), adalah 1. Deklarasi struktur simpul

2. Inisialisasi

.

BINARY TREE/POHON BINER

• Proses Pohon Biner (Binary Tree), adalah 3. Pembuatan sebuah simpul

BINARY TREE/POHON BINER

• Proses Pohon Biner (Binary Tree), adalah 4. Pembuatan simpul Akar

BINARY TREE/ POHON BINER

• Proses Pohon Biner (Binary Tree), adalah 5. Penambahan

/melakukan insert simpul baru kedalam sebuah pohon

BINARY TREE/POHON BINER

• Proses Pohon Biner (Binary Tree), adalah 6. Pembacaan/pene

lusuran pohon biner