sd c 10 - · pdf fileby : sri rezeki candra nursari 2 sks. ... 9. avl tree 10. heap dan...
TRANSCRIPT
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