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
HEAP & B-TREE Pertemuan 11
2 SKS
Heap Sort Seperti metode struktur organisasi, nilai ditukarkan dari root ke level yang paling rendah
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 23 17 6
5
14 13
7
12
10
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 23
i=5 17
13 i=5
6
5
14
7
12
10
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 23
i=4 17 7
5
i=4
6
14 13
12
10
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 23
i=3 17 7
5
13
6
i=3
14
12
10
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 23
i=2 17 7
5
13
6
14
i=2
12
10
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 23
i=1
i=1
17 7
5
14 13
6
12
10
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 17 13 7
5
14 12
6
23
10
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 14 13 7
5
10 12
17
23
6
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 13 12 7
14
10 5
17
23
6
1
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 12 7 1
14
10 5
17
23
6
13
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 10 7 1
14
6 5
17
23
12
13
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 7 5 1
14
6 10
17
23
12
13
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 6 5 7
14
1 10
17
23
12
13
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 1 5 7
14
6 10
17
23
12
13
Heap Sort -Max/Descending A: [ 23,17,14,6,13,10,1,5,7, 12] 1 5 7
14
6 10
17
23
12
13
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 8 17 6
5
14 13
7
12
10
1
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 8
i=5 17
13 i=5
6
5
14
7
12
10
1
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 8
i=4 17 i=4
5
6
14 12
7
13
10
1
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 8
i=3 17 5
6
14 12
7
13
10
i=3 1
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 8
i=2 17 5
6
i=2 12
7
13
1 10
14
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 8
i=1
i=1
5 17
6
1 12
7
13
10
14
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 1 5 17
6
8 12
7
13
10
14
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 5 12 17
6
8 13
7
1
10
14
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 5 12 17
6
8 13
7
1
10
14
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 7 12 17
6
8 13
5
1
10
14
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 7 12 17
6
8 13
5
1
10
14
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 8 12 17
6
14 13
5
1
10
7
Heap Sort-Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 10 12 17
6
14 13
5
1
8
7
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 12 13 17
6
14 10
5
1
8
7
Heap Sort-Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 13 17 12
6
14 10
5
1
8
7
Heap Sort -Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 14 17 12
6
13 10
5
1
8
7
Heap Sort-Min/Ascending A: [ 8,17,14,6,13,10,1,5,7, 12] 17 14 12
6
13 10
5
1
8
7
HEAP TREE Heap adalah tree yang mempunyai persamaan sebagai berikut:
R[i] < r[2i] dan R[i] < r[2i+1]
Heap Tree disebut juga Complete Binary Tree, jika suatu node mempunyai child, maka jumlah childnya harus selalu dua Minimum Heap, apabila parentnya lebih kecil daripada kedua childnya Maksimum Heap, apabila parentnya lebih besar daripada kedua childnya
HEAP TREE
Contoh HEAP TREE MINIMUM HEAP TREE 9
12
22
25
55
Contoh HEAP TREE MAKSIMUM HEAP TREE 9
63
22
25
55
HEAP-TREE • Operasi dalam Heap Tree) 1. Penambahan/melakukan insert simpul 2. Penghapusan/melakukan Delete simpul
HEAP-TREE • Operasi dalam Heap Tree) 1. Penambahan/melakukan insert simpul
Insertion • Insert 2 (Percolate Up)
-1
0
1
43 65
3
5 58
40
42
8 2
4
-1 0 1 43 5 3 8 65 58 40 42 4 2 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14
Insertion • Insert 2 (Percolate Up)
-1
0
1
43 65
2
5 58
40
42
8 3
4
-1 0 1 43 5 2 3 8 65 58 40 42 4 3 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14
Insertion • Insert 14 13 21 24 65
16 19
31 26
32
14
68
Insertion • Insert 14 13 21 24 65
16 19
14 26
32
31
68
Insertion • Insert 14 13 14 24 65
16 19
21 26
32
31
68
HEAP-TREE • Operasi dalam Heap Tree) 2. Penghapusan/melakukan Delete simpul
Delete Minimum • Percolate Down
-1
0
1
43 65
3
3 58
40
42
2
4
-1 0 1 43 3 3 2 65 58 40 42 4 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14
Delete Minimum 4 0
1
43 65
3
3 58
40
2
42
4 0 1 43 3 3 2 65 58 40 42 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14
Delete Minimum: Completed 0 3
1
43 65
3
4 58
40
2
42
0 3 1 43 4 3 2 65 58 40 42 0
1
2
3
4
5
6
7
8
9
10 11 12 13 14
Delete Min (Alternative) 13 14 19 65
16 19
21 26
32
31
68
Delete Min (Alternative) • Percolate Down 14 19 65
16 19
21 26
32
31
68
Delete Min (Alternative) 14 16 19 65
19
21 26
32
31
68
Delete Min (Alternative) 14 19
16 19
21 65
26
32
31
68
Delete Min (Alternative) 14 19 26 65
16 19
21 32
31
68
Delete Min (Alternative) 14 19 26 65
16 21
31
32
19
68
B-TREE B-Tree adalah tree yang setiap nodenya dapat berisi lebih daripada satu elemen
Jumlah elemen dalam 1 node tergantung kepada order B-Tree tersebut Jumlah minimum elemen dalam setiap node (kecuali ROOT) adalah d, dan jumlah maksimum elemen di ROOT adalah satu dan jumlah maksimumnya adalah 2d Jumlah minimum child suatu node di dalam BTree adalah 0, dan jumlah maksimumnya adalah jumlah elemen +1
B-TREE • Operasi dalam Pohon B (B- Tree) 1. Penambahan/melakukan insert simpul 2. Penghapusan/melakukan Delete simpul
B-TREE • Operasi dalam Pohon B (B- Tree) 1.
Insert Apabila node/simpul belum penuh (jumlah elemen < 2d), maka elemen dapat langsung diinsert Jika node/simpul sudah penuh, maka lakukan NODE SPLIT dengan langkah sebagai berikut
Split node/simpul menjadi 2 25 37 40 Akan menginsert elemen 27 Letakkan d elemen terkecil di node/simpul kiri Letakkan d elemen terkecil di node/simpul kanan Letakkan elemen tengah ke node/simpul parentnya
B-TREE • Operasi dalam Pohon B (B- Tree) 2.
Delete
Jika target node/simpul yang akan dihapus berisi elemen lebih dari d, maka target elemen dapat langsung dihapus, tanpa harus di regenerate
Contoh : Split node/simpul 10 Root 5 6 7 15 16 18 delete 6 5 7 15 16 18
Jika target node/simpul yang akan dihapus berisi d node/simpul, penghapusan akan menyebabkan underflow, maka regenerate dilakukan dengan meminjam elemen yang berada di node/sim;ul kiri atau kanan (yang memiliki elemen lebih dari d). Parent/separator akan berubah
Contoh : Split node/simpul 10 20 5 7 9 15 16 9 20 5 7 10 15 16 25 26
Root 25 26 delete 15 Root
B-TREE • Operasi dalam Pohon B (B- Tree) 2.
Delete
Jika node/simpul kiri maupun kanan yang akan dilakukan peminjaman ternyata mempunyai elemen kurang dari d, jika dilakukan peminjaman node/simpul tersebut akan terjadi underflow, maka regenerate akan dilakukan dengan menggabung node/simpul yang akan dihapus dengan node/simpul kiri yang akan dihapus dengan node/simpul di kiri/kanan
Contoh : Split node/simpul 9 20 5 715 16 25 27 delete 15 20 5 7 9 16 25 27
Root Root
B-TREE
B-TREE
B-TREE
B-TREE
