Rangkuman Akhir DS

Rangkuman Akhir DS

Rangkuman Akhir (Data Structure)

Nama : Bimo Dewangga Setiawan 

NIM : 2301911773

Kelas : CB01

Dosen: Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)

1. Linked List
ATURAN LINKED LIST

Linked list mempunyai aturan:
1.      Data harus memiliki hubungan dengan yang lain.
2.      Data yang terhubung tidak boleh bercabang.


PERANCANGAN LINKED LIST

1.      Single Linked List
Tahapan pertama ialah membuat struct (karena setiap node akan berbentuk struct) Dan memiliki satu buah fungsi pointer juga bertype struct yang akan menghubungkan setiap node .

2.      Double Linked List
Lain Halnya dengan single List, double Linked List adalah suatu linked list yang mempunyai 2 penunjuk ke data sebelumnya dan berikutnya, memiliki 2 buah pointer, setiap node akan terhubung dengan pointer kanan dan kiri.

2. Stack&Queue

PENGERTIAN STACK & QUEUE

1. Stack

• Stack adalah linear data structure yang elemennya hanya dapat di insert dan di delete dari satu sisi, yang disebut top. 

• Stack sendiri memiliki konsep yang mirip dengan tumpukan piring, dimana jika kita ingin meletakkan piring, maka kita akan meletakan piring di paling atas (insert), serta ketika ingin mencuci piring tersebut, maka piring yang kita ambil adalah piring paling atas juga (delete).
• Prinsip yang dipakai dalam stack adalah LIFO (Last In First Out), artinya elemen yang dimasukkan terakhir adalah yang dikeluarkan pertama.
• Fungsi insert dalam stack dinamakan push operation, sedangkan fungsi delete dalam stack dinamakan pop operation.

2. Queue

• Queue adalah linear data structure yang elemennya hanya dapat di-insert dari satu sisi yang disebut rear dan hanya dapat di delete dari satu sisi juga yang disebut front.

sumber : https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/

• Konse queue mirip dengan konsep orang mengantri, dimana orang baru akan mengantri di urutan paling belakang (insert) dan yang akan dilayani dahulu adalah orang yang paling depan (delete).
• Prinsip yang dipakai dalam queue adalah prinsip FIFO (First In First Out), dimana elemen yang dimasukkan pertama akan dikeluarkan pertama juga.
• Fungsi insert dalam queuedinamakan enqueue operation, sedangkan fungsi delete dalam stack dinamakan dequeue operation.

sumber : https://www.hackerearth.com/practice/notes/stacks-and-queues/

• Kelemahan queue adalah ketika pointer left sudah mencapai elemen maximal, maka elemen sebelumnya yang di delete akan kosong (left to right). Sehingga diperlukan Circular Queue, dimana ketika pointer right/rear telah mencapai MAX, maka pointer right akan berlaku sebagai index 0 kembali, Sehingga menghasilkan bentuk siklus/circular.

• Pengaplikasian queue antara lain pada:
• Deques
• Priority Queues
• Breadth-First-Search (BFS)

3.TREES & BINARY TREE

• Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many).
• Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

• Istilah umum dalam tree :
1. Predecessor : node yang berada diatas node tertentu
2. Successor : node yang berada di bawah node tertentu
3. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
4. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama
5. Parent : Predecessor level di atas suatu node
6. Child : successor satu level di bawah suatu node
7. Sibling : node-node yang memiliki parent yang sama dengan suatu node
8. Subtree : bagian dari tree yang berupa suatu node beserta descendant nya dan memiliki semua karakteristik dari tree tersebut
9. Size : banyaknya node dalam suatu tree
10. Height : banyaknya tingkatan/level dalam suatu tree
11. Root : satu-satunya node khusus dalam tree yang tak punya predecessor
12. Leaf : node-node dalam tree yang tak memiliki successor
13. Degree : banyaknya child yang dimiliki suatu node

• Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.

leaf = 2, 5, 11, 4

• Tipe-tipe binary tree :
• Perfect binary tree : pohon biner yang semua node leafnya berada pada kedalaman yang sama dari node root.

Depth = 4

• Complete binary tree : Mirip dengan perfect binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

• Skewed binary tree : binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

• Implementasi binary tree menggunakan array

• Index di array menggambarkan nomor node
• Index 0 adalah root node
• Index left child adalah 2p+1, p adalah index parent
• Index right child adalah 2p+2
• Index parent adalah (p-1)/2

• Implementasi binary tree dengan linked list
• struct node {
    int data;
    struct node *left;
    struct node *right;
    struct node *parent;
  };
  struct node *root = NULL;

                    

• Expression tree concept
• Misal :

                     

• Prefix  : *+ab/-cde
• Postfix      : ab+cd-e/*
• Infix          : (a+b) * ((c-d)/e)

4. BST
Binary Search Tree (BST) sama seperti binary tree, yaitu masing - masing node maksimal memiliki 2 anak. Yang membedakannya ialah nilai node di kiri harus lebih kecil daripada di kanan.

Kelebihan BST:
1. Lebih mudah dalam melakukan pencarian data. 
2. Proses melihat data lebih mudah.
3. Mudah dalam penyimpanan dalam data bentuk hirarki.

SEARCHING

 while(current->data != data){
      if(current != NULL) {
         printf("%d ",current->data); 
         if(current->data > data){  //ke kiri tree
            current = current->leftChild;
         } 
         else {        //ke kanan tree       
            current = current->rightChild;
         }
         if(current == NULL){ //tidak ditemukan
            return NULL;
         }
      }   
   }
    

return current;


INSERT SINGLE LINKED LIST
void push(struct *tree node, int a){
    if(root==NULL){ //belum pernah terbentuk
        root = newNode(a); //pesan memori malloc
    }

    else if(a < node->a && node->left==NULL){ //kalau yang mau diinput lebih kecil daripada sekarang, dan sebelah kirinya kosong
        node->left = newNode(a); //pesen malloc
        node->left->parent = node; //parent di node sekarang
    }

    else if(a > node->a && node->right==NULL){ //kalau yang diinput lebih besar daripada sekarang, dan sebelah kanannya kosong
        node->right = newNode(a); //pesen malloc
        node->right->parent = node; //parent di node sekarang yg kanan
    }

    else if(a < node->a){ //yang diinput lebih kecil daripada sekarang, tapi kiri kanan tidak kosong
        push(node->left, a); //akan ditaruh di kiri
    }

    else{ //yang diinput lebih besar daripada sekarang, kiri kanan tidak kosong
        push(node->right, a); //akan ditaruh di kanan
    }
}

DELETE
//untuk node yang belum memiliki anak, atau node terbawah
 

//node yang mau dihapus hanya memiliki anak kiri, tidak punya anak kanan
 

//node yang mau dihapus hanya memiliki anak kanan
 
//punya anak kanan dan kiri, digantikan oleh anak kiri yang paling besar nilainya. kemudian yg menggantikan dihapus lagi (recursive)






5. Avl Tree

A. Pengertian

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Selain itu terdapat 2 proses penyeimbangan pada AVL Tree yaitu dengan cara Single rotation dan Double rotation.

B. Single Rotation

Single rotation adalah rotasi yang di lakukan hanya sekali agar sebuah tree AVL cara ini dapat menyelesaikan kasus luar.
Double rotation adalah rotasi yang dilakukan lebih dari sekali dan sedangkan cara ini untuk menyelesaikan kasus dalam.

Cara menentukan Height dan Balance Factor :Note :

Height :

– Jika node (root) tidak memiliki subtree heightnya = 0

– Jika node adalah leaf, height =  1

– Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :

-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

AVL Tree Operations : Insertion

Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.

AVL Tree Operations : Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

6. Heaps and Tries

Heap merupakan struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap dapat diimplementasikan dengan menggunakan linked-list, tetapi lebih mudah untuk menggunakan array. Heap dibagi menjadi dua macam yaitu :

-Max Heap
yang dimana node rootnya memiliki nilai paling besar di antara semua childrennya.
contoh max heap :

-Min Heap
yaitu node rootnya memiliki nilai paling kecil di antara semua childrennya.
contoh min heap :

insertion and deletion in Heap

deletion di heap merupakan penghapusan pada simpul root. Jika itu max heap maka yang dihapus adalah node yang mempunyai nilai paling besar. Sedangkan deletion di min heap adalah penghapusan node yang memiliki nilai paling kecil.

untuk insertion dalam heap, yaitu dengan :

1. menambahkan elemen baru di akhir array

2. lalu membandingkan nilai node tersebut dengan nilai parent, jika mereka salah urutan tukar mereka.

Tries adalah dtruktur data yang digunakan untuk menyimpan array asosiatif. tries adalah struktur data yang simpulnya menyimpan huruf-huruf alfabet. 

Sekian Rangkuman dari blog saya, semua sumber ini sudah saya tulis di setiap post. Terimakasih Pak..