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
Materi 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Data dan Struktur Data Array Struktur dan Record Pointer Linked List Stack (Tumpukan) Queue (Antrian) Tree (Pohon) AVL Tree Heap dan B-Tree Sorting Search Hashing Graph
TREE - POHON Pertemuan 10
2 SKS
Istilah Umum Dalam TREE 1. 2. 3. 4. 5. 6. 7. 8.
Tree (pohon) dan Graph (Graf) Simpul (Vertex, Node) dan Busur (Edge, Arc) Superordinat dan subordinat, father dan son, parent dan children Root (akar) dan Leaf (daun) Level (tingkat) dan Depth (kedalaman) Degree (derajat) simpul dan degree pohon M-ary tree dan binary tree 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 LinkedList 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
E
D
H
F
G
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 = 3 Jumlah simpul 10, maka n = 10
A D B
C H G
E
F J I
Jumlah Null-Link = n * (M-1) + 1 = 10 * (3-1) +1 = 10*2+1 = 21
Contoh Soal : Pohon Biner • Sebuah pohon biner dengan 10 buah simpul. Apabila M=2, Hitung berapa jumlah Null-Link nya? Pohon dengan M = 2 Jumlah simpul 10, maka n = 10
A C B F E
D
H G J
I
Jumlah Null-Link = n * (M-1) + 1 = 10 * (2-1) +1 = 10*1+1 = 11
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 (leftchild) dan subordinat kanan (right-child) INFO Left
Right Father
INFO Left
Right
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 Jumlah daun/leaf = 5 B
C F
E
D H
I
G
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 d1 subpohon kiri harus mempunyai subordinat kiri dan kanan
COMPLETE BINARY TREE/FULL BINARY TREE/ ALMOST COMPLETE BINARY TREE A
A B
E
D H
I
J
B
C F
K L M N
Almost Complete Binary Tree dan Bukan Strictly Binary Tree karena simpul G hanya punya satu anak
E
D
G H
C
I
J
F
K L M N
G O
Almost Complete Binary Tree dan Strictly Binary Tree
COMPLETE BINARY TREE/FULL BINARY TREE/ ALMOST COMPLETE BINARY TREE A A B B
E
E
I
J
F
G
F H
H
C
C D
D
Bukan Almost Complete Binary Tree
K
L M
I
A B
Bukan Almost Complete Binary Tree karena simpul C hanya punya satu anak
D H
C
E
F
Almost Complete Binary Tree dan tapi bukan Strictly Binary Tree G
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 A
A B
E
D H
I
J
B
C F
K L M N
Unbalanced Binary Tree
E
D
G H
C
I
J
F
K L M N
Balanced Binary Tree
G 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 A B 2n
1
n C
2n+1
B
2
C
3 G H 10
5 I
11
PENOMORAN SIMPUL POHON BINER Level (k)
Maksimum jumlah simpul pada level 2^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. 2. 3. 4. 5.
Mendeklarasikan struktur simpul Inisialisasi Pembuatan sebuah simpul Pembuatan simpul akar Penambahan/melakukan insert simpul baru kedalam sebuah pohon 6. 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
