Data Struct Linked List 2

Nama : Dea Claresta Nim : 2301863736 Heap Heap adalah spesial tree, yaitu complete binary tree. Heap ada 2 tipe, max heap, dan min heap. Min heap->node parentnya lebih kecil dr anaknya. Max heap->parentnya lebih besar dari anaknya. Min heap-> angka paling kecil ada di root. angka paling besarnya ada di salah satu leaf. heap bisa menggunakan linked list, tp paling mudah pakai array, dimana arraynya dimulai dari 1, array ke 0 tidak dipakai agar lebih mudah. Hubungan antar parent dengan anak kanan dan kiri dalam array sangat mudah untuk di cari, dengan x adalah array dari node itu sendiri •Parent(x)  = x / 2 •Left-child(x)  = 2 * x •Right-child(x)  = 2 * x + 1 misalnya, node 15, x= 2, parentnya 1, anak kirinya 4, dan anak kanannya 5. Aplikasi heap yaitu dalam  Priority Queue Selection Algorithms (finding min/max element, median, kth-largest element, etc). Dijkstra’s Algorithm (finding shortest path in graph) Prim Algorithm (f...

Nama: Dea Claresta Nim: 2301863736 AVL Tree merupalan self balancing binary search tree. BST digunakan dengan tujuan dari lebih cepatnya suatu node ditemukan, namun BST memiliki worst case, dimana proses penginputan data yg berurut akan membuat penempatan Node yang sebaris dan tidak bercabang,sehingga proses pencarian datanya sama saja dengan linked list  yaitu dengan membandingkan setiap node dari awal sampai ketemu. Oleh sebab itu, digunakan lah metode AVL, yaitu balancingnya BST, sehingga setiap node hanya akan memiliki balence faktor maksimal 1 yang didapat dari pengurangan height kedua anaknya. Dimana setiap leaf(node yang tidak memiliki anak ) akan memiliki height sebesar satu, dan node-node keatasnya akan memiliki height yang semakin besar. Jika setelah penginputan terbentuk balence factor yang lebih besar dari 1, maka akan dilakukan rotasi. Untuk rotasi ini sendiri, ada 4 macam( LL, RR, LR, RL). dimana rotasi ini dilihat dari 2 langkah terjadi imbalace menuju sumber t...