Senin, 30 Maret 2020

Rangkuman Semester 2 Data Struct



Ringkasan Data Struct

Single Linked List
Linked List atau senarai berantai adalah struktur data yang dibangun dari satu atau lebih node yang menempati lokasi memori secara dinamis dan disusun saling sambung – menyambung. Single Linked List adalah kumpulan dari node yang saling berhubungan dengan node lain melalui sebuah pointer(next).
Macam – macam pointer yang terdapat dalam single linked list:
  • Head : elemen yang berada pada posisi pertama dalam suatu linked list
  • Tail : elemen yang berada pada posisi terakhir dalam suatu linked lis
  •  Curr : elemen yang berada pada linked list dan pointer ini bisa pindah - pindah
  • Next

Memory allocation dynamic
JIka memerlukan untuk mengalokasikan memori secara dinamis(dalam runtime) dapat menggunakan malloc di C/ C++
Rumus:
                Curr = (struct data*)malloc(sizeof(struct data));
Keterangan : data di warnai merah artinya bisa dinamai apa aja

Single linked list ketika belum ada data (ketika head == NULL)
curr ->angka = data; (misalkan diketahui int angka)
head = curr;
tail = curr;
tail ->next = NULL

Single linked list insert menambah data di bagian belakang
tail -> next = curr;
curr -> tail;
tail -> next = NULL;

Single linked list insert menambah data  di bagian depan
curr -> next = head;
head = curr;

Single linked list insert menambah data di tengah
x -> next = curr;
curr -> next = y;
x = head;
while(x -> next -> angka > curr ->angka){
      x = x -> next;
}
y = x -> next;
x -> next = curr;
curr -> next = y;
Keterangan : x dan y adalah pointer baru

Single Linked List delete depan
if(head ->angka==x){
               curr = head;
               head = head->next;
               free(curr);
}
Ket : angka = deretan dari banyak angka , x = nilai yang dihapus

Single Linked List delete tengah
If(tail->angka==x){
              curr = head;
              while(curr->next!=tail){
                   curr= curr->next;
             }
             free(tail);
             tail=curr;
             tail->next = NULL;
}
Ket : angka = deretan dari banyak angka , x = nilai yang dihapus

Single Linked List delete belakang
curr = head;
while(curr->next->score!=x){
     curr = curr->next;
}
temp = curr->next;
curr->next=temp->next;
free(temp);
Ket : angka = deretan dari banyak angka , x = nilai yang dihapus


Double Linked List
Double linked list adalah linked list dengan node yang memiliki data dan dua buah pointer(next dan prev) yang menunjuk ke node sebelum dan node sesudah.
Macam – macam pointer yang terdapat dalam double linked list :
  • Head : elemen yang berada pada posisi pertama dalam suatu linked list
  • Tail : elemen yang berada pada posisi terakhir dalam suatu linked list
  • Curr : elemen yang berada pada linked list dan pointer ini bisa pindah - pindah
  • Next
  • Prev

Contoh syntax untuk double linked list (dari kelas LAB)





Stack & Queue
Stack
Stack(tumpukan) artinya data yang pertama kali masuk, maka data tersebut paling akhir keluar.
Contoh : tumpukan piring.
Stack dapat diimplementasikan menggunakan array (ada batasannya) dan linked list(tidak ada batasan/ unlimited).
Elemen – elemen yang ada di stack dapat ditambahkan dan dihapus hanya dari satu ujung yaitu bagian atas.
Data disimpan dengan cara Last In First Out (LIFO).
Macam – macam stack operations :
  •  Push(x) : memasukkan data ke dalam stack.
  • Pop() : menghapus elemen yang terletak pada posisi paling atas dati sebuah tumpukan.
  • Top() :  mengembalikan(return) data teratas dari tumpukan.

Infix, Postfix, dan Prefix Notation
  • Prefix   : Operator yang di tulis sebelum operan ( operator operand operand)
  • Contoh : * 4 10
  • Infix     : Operator yang ditulis antara operan ( operand operator operand)
  • Contoh: 4 * 10
  • Postfix : Operator yang ditulis setelah operan (operand operand operator)
  • Contoh : 4 10 *

Queue
Queue(urutan) artinya data yang pertama kali masuk maka data tersebut akan pertama kali keluar.
Queue dapat diimplementasikan dengan menggunakan array atau linked list.
Elemen – elemen dalam queue ditambahkan di satu ujung yang disebut bagian belakang dan dihapus dari ujung lain yang disebut depan.
Data yang disimpan dengan cara First in First Out (FIFO).
Macam – macam queue operations:
  • Push(x)     : menambahkan item x ke belakang antrian
  • Pop()         : menghapus item dari depan antrian
  • Front()      : mengungkapkan / mengembalikan item paling depan dari antrian.


Depth First Search (DFC)
Depth First Search (DFC) adalah suatu algoritma untuk melintasi atau mencari di pohon atau grafik. DFD dapat diimplementasikan dengan fungsi rekursif atau iterative produce menggunakan stack, hasilnya mungkin memiliki sedikit perbedaan pesanan kunjungan tetapi keduanya benar. Proses pencarian pada algoritma DFC akan dilakukan pada semua anaknya terlebih dahulu, sebelum dilakukan pencarian ke node – node yang selevel.
Deques
Deques adalah suatu daftar/list dimana elemen yang digunakan untuk memasukkan(insert) atau menghapus(delete) di bagian kedua ujungnya yaitu head dan tail.

Priority Queue
Ada 2 aturan umum untuk memproses priority queue adalah:
Elemen dengan prioritas lebih tinggi adalah proses sebelum elemen dengan prioritas lebih rendah.
Dua elemen dengan prioritas yang sama diproses berdasarkan FCFS.

Breadth First Search(BFC)
Breadth First Search adalah metode pencarian yang dilakukan dengan mengunjungi setiap node secara sistematis pada tiap setiap level hingga keadaan tujuan ditemukan. Atau algoritma untuk melintasi atau mencari di pohon atau grafik.


Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.
Hash table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Hash table menggunakan memori penyimpanan utama berbentuk  array dengan tambahan algoritma untuk mempercepat pemrosesan data.
Hash Function adalah suatu fungsi sederhana untuk mendaoatkan nilai hash dari nilai kunci(key value) suatu data.
Ada beberapa hal dalam membuat hash function antara lain :
  • Ukuran array/ table size (m)
  • Key value/ nilai yang di dapat dari data (k)
  • Hash value/ hash index/index yang dituju (h)

Beberapa metode pentuk untuk membangun hash functions antara lain:
  • Mid – Square
  • Metode Mid-Square yaitu teknik hashing di mana kunci unik dihasilkan.

·         Division (most common)
Metode division yaitu Jumlah lokasi memori tersedia dihitung , kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(nilai hashnya). Secara umum rumus division sebagai berikut :
                                                                                h(z) = z mod M
Keterangan:
z          = key/ suatu lokasi  memori yang beralamat h(z)
M        = jumlah lokasi memori yang tersedia pada array

·         Folding
Metode folding terbagi menjadi dua langkah yaitu :
Ø  Bagi nilai kunci menjadi beberapa bagian dimana setiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lainnya.
Ø  Tambahan bagi individu. Yaitu memperoleh jumlah part 1 + part 2 + .. + part n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.

·         Digit Extraction
Metode digit extraction yaitu mendapatkan hash key dengan cara mengambil digit – digit tertentu dari sebuah string untuk dijadikan hash keynya.

·         Rotating Hash
Metode Rotating Hash yaitu mendapatkan hash key maka di lakukan rotasi untuk menggeser digit sehingga menemukan alamat hash key baru.

Dalam penyimpanan data di Hash Table sangat dimungkinkan 1 index menyimpan lebih dari 1 data, hal ini disebut denan Collision. Ada 2 cara untuk menangani collision yaitu :
·         Linear Probing
Mencari slot kosong berikutnya dan letakkan string disana.
·         Chaining
Masukkan string ke dalam slot sebagai chained list(linked list).

Tree  & Binary Tree
Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).
Jenis – jenis binary tree:
·         Perfect binary tree
Adalah binary tree yang setiap level berada pada kedalaman/ depth yang sama.
·         Complete binary tree
Adalah binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodesnya paling panjang ke kiri.
·         Skewed binary tree
Adalah binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
·         Balanced binary tree
Adalah binary tree yang dimana yang setiap leafnya sama jauhnya dari root

Binary Search Tree (BST)
Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Aturan main Binary Search Tree :

  • Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
  • Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Syntax Binary Search Tree







Kamis, 12 Maret 2020

Hashing & Binary Tree


Hashing & Hash Tables
Hashing
Hashing adalah teeknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.

Hash Table
Hash table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Hash table menggunakan memori penyimpanan utama berbentyj array dengan tambahan algoritma untuk mempercepat pemrosesan data.

Hash Function
Hash Function adalah suatu fungsi sederhana untuk mendaoatkan nilai hash dari nilai kunci(key value) suatu data.
Ada beberapa hal dalam membuat hash function antara lain :
·        Ukuran array/ table size (m)
·        Key value/ nilai yang di dapat dari data (k)
·        Hash value/ hash index/index yang dituju (h)
Beberapa metode pentuk untuk membangun hash functions antara lain:
  • Mid – square
  • Division (most common)
  • Folding
  • Digit Extraction
  • Rotating Hash

Mid – square
Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus. Jika terjadi overflow, gunakan tipe data int panjang atau gunakan string sebagai perkalian jika luapan masih terjadi. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.
Contoh:
Nilai
Di kuadratkan
Nilai di ekstraksi
4765
22705225
7052
3725
13875625
8756


Algoritma dalam mid – square
  • Pilih nilai seed. Ini adalah langkah penting karena untuk nilai seed yang sama, urutan nomor acak yang sama dihasilkan.
  • Ambil kuadrat dari nilai seed dan perbarui seed dengan jumlah digit tertentu yang terjadi di square. Catatan: Semakin besar jumlah digit, semakin besar keacakannya.
  • Kembalikan kuncinya.

Division
Jumlah lokasi memori tersedia dihitung , kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(nilai hashnya).
Secara umum rumus division sebagai berikut :
h(z) = z mod M
Keterangan:
z          = key/ suatu lokasi  memori yang beralamat h(z)
M        = jumlah lokasi memori yang tersedia pada array
Contoh:
Ukuran table = 97

COBB
Abjad
Nilai ASCII
C
67
O
79
B
66
B
66
total
278
H(z) = 278 mod 97 = 84

HIKE
Abjad
Nilai ASCII
H
72
I
73
K
75
E
69
total
289
H(z) = 289 mod 97 = 95

ABCD
Abjad
Nilai ASCII
A
65
B
66
C
67
D
68
total
266
H(z) = 278 mod 97 = 72


Folding
Metode lipat berfungsi dalam 2 langkah :
  • Bagi nilai kunci menjadi beberapa bagian dimana setiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lainnya.
  • Tambahan bagi individu. Yaitu memperoleh jumlah part 1 + part  + .. + part n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.


  Contoh:
Key = 6632
Parts = 66 dan 32
Jumlah = 98
Hash value = 98

Digit Extraction
Mendapatkan hash key dengan cara mengambil digit – digit tertentu dari sebuah string
untuk dijadikan hash keynya.
Contoh: terdapat string yaitu 14568, jika kita mengambil digit 1, digit 3, dan digit 5 maka
hash keynya adalah 158.

Rotating Hash
Mendapatkan hash key maka di lakukan rotasi untuk menggeser digit sehingga
menemukan alamat hash key baru.
Contoh :
Hash key = 3456
Hasil rotasi = 6543

Collision
Ada 2 cara untuk menangani collision :
·        Linear Probing
Mencari slot kosong berikutnya dan letakkan string disana.
Code :
void linear_probing(item, h[]) {
hash_key = hash(item);
i = has_key;
while ( strlen(h[i] != 0 ) {
         if ( strcmp(h[i], item) == 0 ) {
              // DUPLICATE ENTRY
         }
         i = (i + 1) % TABLE_SIZE;
         if ( i == hash_key ) {
              // TABLE IS FULL
         }
}
h[i] = item;
}

·        Chaining
Masukkan string ke dalam slot sebagai chained list(linked list).
Code:
void chaining(item, h[]) {
     hash_key = hash(item);
     trail = NULL, lead = h[hash_key];
     while ( lead ) {
     if ( strcmp(lead->item, item) == 0 ) { // DUPLICATE ENTRY }
     trail = lead; lead = lead->next;
     }
     p = malloc new node;
     p->item = item;
     p->next = NULL;
     if ( trail == 0 ) h[hash_key] = p; else trail->next = p;
}


Trees  & Binary Tree

Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).
Istilah – istilah umum dalam tree :
·        Prodecessor : node yang berada diatas node tertentu.
·        Successor : node yang berada di bawah node tertentu.
·        Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
·        Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
·        Parent : predecssor satu level di atas suatu node.
·        Child : successor satu level di bawah suatu node.
·        Sibling : node-node yang memiliki parent yang sama dengan suatu node.
·        Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
·        Size : banyaknya node dalam suatu tree.
·        Height : banyaknya tingkatan/level dalam suatu tree.
·        Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
·        Leaf : node-node dalam tree yang tak memiliki seccessor.
·        Degree : banyaknya child yang dimiliki suatu node.

Jenis – jenis binary tree:
·        Perfect binary tree
Adalah binary tree yang setiap level berada pada kedalaman/ depth yang sama.
·        Complete binary tree
Adalah binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodesnya paling panjang ke kiri.
·        Skewed binary tree
Adalah binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
·        Balanced binary tree
Adalah binary tree yang dimana yang setiap leafnya sama jauhnya dari root

Representation of Binary Tree
  • Implementation using array


        Index on array represents node number
        Index 0 is Root node
        Index Left Child is 2p + 1, where p is parent index
        Index Right Child is 2p + 2
        Index Parent is (p-1)/2
  • Implementation using linked list

         struct node {
int data;
struct node *left;
struct node *right;
struct node *parent;
          };
          struct node *root = NULL;

structure binary tree
struct tnode {
char chr;
struct tnode *left;
struct tnode *right;
};

Insert di binary tree mengunakan C
// C++ program to insert element in binary tree
#include <iostream>
#include <queue>
using namespace std;
  
/* A binary tree node has key, pointer to left child
and a pointer to right child */
struct Node {
    int key;
    struct Node* left, *right;
};
  
/* function to create a new node of tree and r
   eturns pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
  
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
  
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
  
/*function to insert element in binary tree */
void insert(struct Node* temp, int key)
{
    queue<struct Node*> q;
    q.push(temp);
  
    // Do level order traversal until we find
    // an empty place. 
    while (!q.empty()) {
        struct Node* temp = q.front();
        q.pop();
  
        if (!temp->left) {
            temp->left = newNode(key);
            break;
        } else
            q.push(temp->left);
  
        if (!temp->right) {
            temp->right = newNode(key);
            break;
        } else
            q.push(temp->right);
    }
}
  
// Driver code
int main()
{
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
  
    cout << "Inorder traversal before insertion:";
    inorder(root);
  
    int key = 12;
    insert(root, key);
  
    cout << endl;
    cout << "Inorder traversal after insertion:";
    inorder(root);
  
    return 0;
}

Deletion in a Binary Tree
Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom (i.e. the deleted node is replaced by bottom most and rightmost node). This different from BST deletion. Here we do not have any order among elements, so we replace with last element.
Contoh:
Delete 10 in below tree
       10
     /    \        
    20     30
Output :   
       30
     /            
    20    
Delete 20 in below tree
       10
     /    \        
    20     30
            \
            40
Output :   
       10
     /   \            
    40    30  

Algorithm
·        Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.
·        Replace the deepest rightmost node’s data with node to be deleted.
·        Then delete the deepest rightmost node.

Source code in C/C++
// C++ program to delete element in binary tree
#include <bits/stdc++.h>
using namespace std;
  
/* A binary tree node has key, pointer to left 
child and a pointer to right child */
struct Node {
    int key;
    struct Node *left, *right;
};
  
/* function to create a new node of tree and 
return pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
  
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
  
/* function to delete the given deepest node 
(d_node) in binary tree */
void deletDeepest(struct Node* root,
                  struct Node* d_node)
{
    queue<struct Node*> q;
    q.push(root);
  
    // Do level order traversal until last node
    struct Node* temp;
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (temp == d_node) {
            temp = NULL;
            delete (d_node);
            return;
        }
        if (temp->right) {
            if (temp->right == d_node) {
                temp->right = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->right);
        }
  
        if (temp->left) {
            if (temp->left == d_node) {
                temp->left = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->left);
        }
    }
}
  
/* function to delete element in binary tree */
Node* deletion(struct Node* root, int key)
{
    if (root == NULL)
        return NULL;
  
    if (root->left == NULL && root->right == NULL) {
        if (root->key == key)
            return NULL;
        else
            return root;
    }
  
    queue<struct Node*> q;
    q.push(root);
  
    struct Node* temp;
    struct Node* key_node = NULL;
  
    // Do level order traversal to find deepest
    // node(temp) and node to be deleted (key_node)
    while (!q.empty()) {
        temp = q.front();
        q.pop();
  
        if (temp->key == key)
            key_node = temp;
  
        if (temp->left)
            q.push(temp->left);
  
        if (temp->right)
            q.push(temp->right);
    }
  
    if (key_node != NULL) {
        int x = temp->key;
        deletDeepest(root, temp);
        key_node->key = x;
    }
    return root;
}
  
// Driver code
int main()
{
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->left->right = newNode(12);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
  
    cout << "Inorder traversal before deletion : ";
    inorder(root);
  
    int key = 11;
    root = deletion(root, key);
  
    cout << endl;
    cout << "Inorder traversal after deletion : ";
    inorder(root);
  
    return 0;
}


Sumber : 
materi binus
https://www.geeksforgeeks.org/mid-square-hashing/
https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/
https://www.geeksforgeeks.org/deletion-binary-tree/
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
https://zoneblog123.blogspot.com/2018/04/pengertian-tree-binary-tree-beserta.html