rangkuman DS semester 2
Penambahan node di AVL Tree
Head dan Tries
Heap adalah suatu Binary Tree lengkap yang menggunakan persyaratan Heap. Di dalam heap terdapat dua tipe heap yaitu Min Heap dan Max Heap. Min Heap adalah sebuah Binary Tree dimana root dari tree tersebut adalah angka terkecil atau memiliki nilai terkecil dibandingkan seluruh node didalam tree tersebut sedangkan Max Heap adalah sebaliknya yaitu Binary Tree dimana root dari tree tersebut adalah angka terbesar dari tree tersebut.
Berikut adalah contoh dari Min Heap dan Max Heap:
Min Heap
Aturan dalam membuat Min Heap:
1. Value dari suatu parent harus lebih kecil dari value anaknya
2. Root dari tree adalah value terkecil yang ada didalam tree
3. Value terbesar terdapat di salah satu node leaf
Max Heap
Aturan dalam membuat Max Heap:
1. Value dari suatu parent harus lebih besar dari value anaknya
2. Root dari tree adalah value terbesar yang ada didalam tree
3. Value terkecil terdapat di salah satu node leaf
Min-Max Heap
Min-Max Heap adalah gabungan dari Min Heap dan Max Heap. Karena Min-Max Heap adalah gabungan dari Min dan Max Heap maka aturan dari kedua heap tersebut disatukan menjadi seperti berikut:
1. Root menggunakan aturan Min Heap.
2. Setiap node yang memiliki height ganjil mengikuti aturan Min Heap.
3. Setiap node yang memiliki height genap mengkuti atuan Max Heap.
Tries
Tries adalah Binary Tree dimana isi dari tersebut adalah kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).
2-3 Tree adalah salah satu jenis struktur data dimana setiap node dengan anaknya, memiliki 2 children dan 1 elemen data (2 node) atau 3 children dan 2 elemen data (3 node).
Sifat-Sifat 2-3 Tree
- Setiap non-leaf terdapat 2-node atau 3-node. Sebuah 2-node berisi satu elemen data dan memiliki 2 children. Untuk yang 3-node berisi 2 elemen data dan memiliki 3 children
- Semua leaf berada di level yang sama (level bawah/bottom level).
- Semua data yang disimpan akan diurutkan
- Misalkan A adalah data yang tersimpan di 2-node. Subtree kiri harus berisi data yang nilainya lebih kecil dari A. Subtree tengah harus berisi data yang nilainya lebih besar dari A.
- Misalkan A dan B adalah data yang tersimpan di 3-node. Subtree kiri harus berisi data yang nilainya kurang dari A. Subtree tengah berisi nilai antara A dan B, dan subtree kanan berisi nilai yang lebih dari B.
Setelah mengetahui apa itu 2-3 Tree, sekarang yang akan kitta bahas ialah bagaimana cara mengoperasikannya, seperti melakukan search, insert data kedalam tree, dan delete data dari tree.
- Search
Searching di dalamstruktur data 2-3 Tree konsepnya sama seperti pada Binary Search Tree (BST), sehingga hanya perlu membandingkan data yang dicari dengan data yang ada pada node. Misal K adalah node yang dicari dan N adalah node yang akan dibandingkan dengan tree, maka jika K lebih kecil dari N, operasi searching berlanjut ke subtree kiri N namun jika K lebih besar dari N, maka operasi searching berlanjut ke subtree kanan N. Ini terjadi terus-menerus sampai K = N (K ditemukan).
- Insert
Misalkan kita akan memasukkan data baru.
- Anggap node yang di insert adalah key
- Key akan ditempatkan pada leaf. a) jika leaf adalah 2-node, maka key dimasukan kedalam leaf sehingga leaf tersebut menjadi 3-node. b) jika leaf adalah 3-node, maka ambil nilai tengah dari A, B, dan key (A adalah data-1 pada leaf, dan B adalah data-2 pada leaf) dan push nilai tengah tersebut pada parentnya
- Jika pada saat aturan kedua parentnya bukanlah 2-node, melainkan 3-node, tentukan kembali nilai tengah lalu push kembali ke parentnya
- Jika pada saat aturan ke 2 dan 3 tidak bisa dilakukan karena parent sampai ke rootnya adalah 3-node, maka tentukan kembali nilai tengah, kemudian nilai tengah tersebut akan dibuat root baru.
Berikut merupakan contoh insert yang pertama.
Ketika insert node 45, kita akan mencari posisi yang tepat untuk 45, pada leaf di sebelah kanan 30. karena leaf tersebut merupakan 2-node, maka sesuai aturan ke 2a, 45 langsung diletakan pada leaf sehingga leaf membentuk 3-node.
Contoh yang kedua, kita akan memasukkan node 75. 
Ketika kita insert node 75, maka kita akan membandingkan nilai 75-80-90. Nilai yang berada di tengah antara ketiga nilai tersebut akan didorong naik menuju parentnya. seperti gambar di bawah ini.
Karena saat ini parent 70 berubah dari 2-node menjadi 3-node, maka ia harus memiliki 3 anak, sehingga 75 dan 90 kita pisahkan menjadi 2 anak. Jadilah seperti berikut ini.
Kemudian kita contohkan lagi dengan memasukkan node 24. 
Insert 24, posisi yang tepat adalah di antara node 20 dan 30, karena 24>20 dan 24<30. namun leaf pada posisi tengah dari 20 dan 30 adalah 3-node, maka kita tentukan nilai tengah, yaitu 24, lalu push 24 ke parentnya.
Akan tetapi parentnya juga merupakan 3-node (dengan data 20 dan 30), maka kita ikuti aturan ke-3, sehingga kita tentukan lagi nilai tengahnya, yaitu 24, lalu push 24 ke parentnya (parent dari parent) lagi. Parent tersebut merupakan 2-node dengan data 50, sehingga kita dapat langsung memasukan nilainya pada parent. Prosesnya adalah sebagai berikut.
Karena parentnya telah berubah menjadi 3-node, maka harus memiliki 3 anak. Yang harus dilakukan pisahkan 3-node sebelumnya menjadi 2 bagian. seperti pada gambar diatas.
Lalu contoh insert terakhir adalah dengan menambahkan node 95. Posisi yang tepat adalah leaf pada sebelah kanan 80, namun leaf tersebut adalah 3-node, sehingga kita harus menentukan nilai tengahnya, yaitu 95. lalu push pada parentnya
Ternyata setelah disisipkan, parentnya adalah 3-node lagi, maka kita tentukan nilai tengahnya lagi, yaitu 80, kemudian push pada parent dari parent nya kembali.
Parentnya merupakan 3-node, dan parentnya adalah root, sehingga tidak mungkin kita push ke parent dari parentnya lagi, karena root tidak memiliki parent, maka kita lakukan aturan ke-4. kita tentukan nilai tengahnya, yaitu 50, dan 50 tersebut kita jadikan root baru (2-node)
50 menjadi root 2-node, karena root berbentuk 2-node, maka harus memiliki 2 anak, maka kita pisahkan node-node yang ada dibawahnya menjadi demikian.
Aturan yang berlaku di dalam deletion :
- Misal node yang dihapus adalah key
- Delete sama seperti BST, yaitu digantikan oleh leafnya
- Jika leaf 3-node, maka ambil salah satu data untuk menggantikan key, seperti BST, terbesar dari subtree kiri atau terkecil dari subtree kanan
- Jika leaf 2-node, maka :
- Jika parent dari leaf adalah 3-node, maka ambil satu data dari parent. kemudian kita perhatikan kembali siblingnya. a) jika sibling 3-node, maka ambil satu data kemudian push pada parent, agar parent kembali menjadi 3-node, b) jika sibling 2-node, maka biarkan parent menjadi 2-node, dan satukan node tersebut dengan siblingnya.
- Jika parent dari leaf adalah 2-node, kita perhatikan siblingnya. a) jika sibling 3-node, ambil satu data dari parent dan push satu nilai dari sibling ke parent. b) jika sibling 2-node, maka satukan sibling dengan parent.
Kita akan menghapus 23, karena 23 adalah leaf, dan merupakan 3-node, maka hapus saja langsung. dan biarkan leaf berubah dari 3-node menjadi 2-node menjadi seperti berikut.
Contoh yang kedua, kita akan menghapus 50, maka digantikan oleh anak kiri terbesar yaitu 40, karena 40 merupakan leaf 2 node, maka kita mengikuti aturan ke-4 yang pertama (karena parent dari 40 adalah 3-node). Dipindahkan seperti berikut, dan akan membuat kekosongan di leaf tempat 40 tadi.
40 menggantikan 50, lalu ambil salah satu dari parent, yaitu 30 (karena node yang kosong disebelah kanan, maka kita ambil yang terbesar dari 20 dan 30). karena siblingnya merupakan 2-node, maka kita ikuti aturan ke-4 pertama yang b. Dipindahkan seperti berikut, dan akan membuat kekosongan di leaf tempat 40 tadi.
Parent dibiarkan menjadi 2 node, dan kita satukan 30 dengan
siblingnya yaitu disebelah kanan 25, karena tidak mungkin di kiri 15,dan
diantara 15 dan 25 karena 30 lebih besar dari keduanya, sehingga
diletakan paling kanan. Jadilah demiikian.
Disjoint Set
// A C# program to implement // Disjoint Set Data Structure. using System; class DisjointUnionSets { int[] rank, parent; int n; // Constructor public DisjointUnionSets(int n) { rank = new int[n]; parent = new int[n]; this.n = n; makeSet(); } // Creates n sets with single item in each public void makeSet() { for (int i = 0; i < n; i++) { // Initially, all elements are in // their own set. parent[i] = i; } } // Returns representative of x's set public int find(int x) { // Finds the representative of the set // that x is an element of if (parent[x] != x) { // if x is not the parent of itself // Then x is not the representative of // his set, parent[x] = find(parent[x]); // so we recursively call Find on its parent // and move i's node directly under the // representative of this set } return parent[x]; } // Unites the set that includes x and // the set that includes x public void union(int x, int y) { // Find representatives of two sets int xRoot = find(x), yRoot = find(y); // Elements are in the same set, // no need to unite anything. if (xRoot == yRoot) return; // If x's rank is less than y's rank if (rank[xRoot] < rank[yRoot]) // Then move x under y so that depth // of tree remains less parent[xRoot] = yRoot; // Else if y's rank is less than x's rank else if (rank[yRoot] < rank[xRoot]) // Then move y under x so that depth of // tree remains less parent[yRoot] = xRoot; else // if ranks are the same { // Then move y under x (doesn't matter // which one goes where) parent[yRoot] = xRoot; // And increment the result tree's // rank by 1 rank[xRoot] = rank[xRoot] + 1; } } } // Driver code class GFG { public static void Main(String[] args) { // Let there be 5 persons with ids as // 0, 1, 2, 3 and 4 int n = 5; DisjointUnionSets dus = new DisjointUnionSets(n); // 0 is a friend of 2 dus.union(0, 2); // 4 is a friend of 2 dus.union(4, 2); // 3 is a friend of 1 dus.union(3, 1); // Check if 4 is a friend of 0 if (dus.find(4) == dus.find(0)) Console.WriteLine("Yes"); else Console.WriteLine("No"); // Check if 1 is a friend of 0 if (dus.find(1) == dus.find(0)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }
GRAPH
Graph merupakan struktur data yang menyerupai Tree. Jika kita
memandang tree dan graph secara matematis, maka kita akan menemukan
bahwa tree merupakan bentuk khusus dari graph. Namun karena perbedaan
metode implementasi dari graph dan tree, maka kedua kasus ini
dipisahkan. Implementasi tree dalam pemrograman lebih menyerupai
implementasi linked list, stack, dan queue.
Hal terlihat dari penggunaan pointer untuk membentuk struktur dari data
yang ada. Implementasi graph dalam pemrograman tidak menggunakan pointer
untuk membentuk struktur graph.
Graph direpresentasikan menggunakan elemen-elemen berikut:
- Daftar node
Node yang ada di dalam graph dikumpulkan dalam satu daftar yang memiliki index, agar masingmasing
node dapat mudah diakses. Daftar ini dapat diimplementasikan menggunakan array,
atau linked list. Contoh:
class Node{
…
}
class Graph{
Node daftarNode[];
} - Kumpulan edge
Setiap edge menggambarkan hubungan antara dua node yang dihubungkan oleh edge tersebut.
Dua buah node yang terhubung oleh sebuah edge merupakan node-node yang bertetangga.
Ketetanggaan antar node digambarkan di dalam sebuah matriks, yang disebut matriks
ketetanggaan (adjacency matrix).
Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri.
Masalah-masalah Graph
Masalah path minimum (Shortest path problem):
mencari route dengan jarak terpendek dalam suatu jaringan transportasi.
Masalah aliran maksimum (maximum flow problem):
menghitung volume aliran BBM dari suatu reservoir ke suatu titik tujuan melalui jaringan pipa.
Masalah pencariah dalam graph (graph searching problem):
mencari langkah-langkah terbaik dalam program permainan catur komputer.
Masalah pengurutan topologis (topological ordering problem):
menentukan urutan pengambilan mata-mata kuliah yang saling berkaitan dalam hubungan prasyarat (prerequisite).
Masalah jaringan tugas (Task Network Problem):
membuat penjadwalan pengerjaan suatu proyek yang memungkinkan waktu penyelesaian tersingkat.
Masalah pencarian pohon rentang minimum (Minimum Spanning Tree Problem):
mencari rentangan kabel listrik yang totalnya adalah minimal untuk menghubungkan sejumlah kota.
Travelling Salesperson Problem:
tukang pos mencari lintasan terpendek melalui semua alamat penerima pos
tanpa harus mendatangi suatu tempat lebih dari satu kali.
Four-color problem:
dalam menggambar peta, memberikan warna yang berbeda pada setiap propinsi yang saling bersebelahan.
Definisi
Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi
(edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan
keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan
notasi matematis
G = (V, E)
V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan-pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x, y}.
Suatu graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E.
Digraph & Undigraph
Graph Berarah (directed graph atau digraph): jika sisi-sisi pada
graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu saja, yaitu
dari x ke y tapi tidak dari y ke x; verteks x disebut origin dan vertex
y disebut terminus dari sisi tersebut. Secara grafis maka penggambaran
arah sisi-sisi digraph dinyatakan dengan anak panah yang mengarah ke
verteks terminus, secara notasional sisi graph berarah ditulis sebagai
vektor dengan (x, y).
graph di samping ini adalah suatu contoh Digraph G = {V, E}
dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
dan E = {( (A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H),
(C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I),
(I,J), (I,M), (J,K), (J,M), (L,K), (L,M)}.
Graph Tak Berarah (undirected graph atau undigraph): setiap sisi {x,
y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis
sisi pada undigraph tidak memiliki mata panah dan secara notasional
menggunakan kurung kurawal.
graph di samping ini adalah suatu contoh Undigraph G = {V, E}
dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
dan E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H},
{C,I}, {D,E}, {D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I},
{I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}.
Dalam masalah-masalah graph undigraph bisa dipandang sebagai suatu
digraph dengan mengganti setiap sisi tak berarahnya dengan dua sisi
untuk masing-masing arah yang berlawanan.
Undigraph di atas tersebut bisa dipandang sebagai Digraph G = {V, E}
dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
dan E = { (A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H),
(C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I),
(I,J), (I,M), (J,K), (J,M), (L,K), (L,M), (B,A), (C,A), (D,A), (F,A),
(C,B), (H,B), (E,C), (G,C), (H,C), (I,C), (E,D), (F,D), (G,D), (K,D),
(L,D), (F,E), (I,G), (K,G), (I,H), (J,I), (M,I), (K,J), (M,J), (K,L),
(M,L)}
Selain itu, berdasarkan definisi ini maka struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear atupun hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis. Sementara kita telah ketahui bahwa struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked list adalah digraph, linear 2-way linked list bisa disebut undigraph.
CONTOH CODING :
HASIL CODING :
Comments
Post a Comment