Kamis, 11 Juni 2020

Review Final

Nama : Indah Islamiana Sinurat
NIM : 2301906003
Kelas : CB01
Dosen :
  • Ferdinand Ariandy Luwinda (D4522)
  • Henry Chong (D4460)

AVL Tree



Apa itu AVL Tree? AVL Tree adalah sebuah tree yang sejenis dengan BST. AVL Tree memiliki perbedaan level antara node yang berada di atas ataupun di bawahnya dengan perbedaan minimum -1 dan perbedaan maksimum 1. Perbedaan ini berlaku untuk subtree node yang berada di kanan ataupun di kiri AVL Tree.

Apa sih guna AVL Tree? AVL Tree muncul untuk menyeimbangkan Binary Search Tree (BST), dengan adanya AVL Tree, proses pencarian yang akan kita lakukan (dalam bentuk tree) akan berlangsung/terproses lebih cepat dibandingkan dengan menggunakan BST.

AVL Tree terdiri atas deletion dan insertion.

Insertion

Kasus - kasus dimana harus dilakukan rotation pada saat ingin menambahkan suatu node baru/insert new node, yaitu:

vio - 1
Keterangan:
  1. Pada kasus 1 dan kasus 2 akan dilakukan single rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.
  2. Pada kasus 3 dan kasus 4 akan dilakukan double rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.

Single Rotation

vio - 2

Double Rotation

vio - 3

Deletion

Kasus dan cara pada saat ingin melakukan deletion:
  1. Node yang ingin dihapus berada di leaf/berada di node paling bawah tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita hanya tinggal langsung menghapus node yang ingin kita hapus/delete tanpa melakukan pengecekan dan pembetulan letak agar node tersebut seimbang.
  2. Node yang ingin dihapus berada di bagian tengah/bagian awal tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita harus menghapus node yang telah dipilih (yang ingin dihapus). Lalu apabila dia memiliki anak, kita harus mengganti node yang telah kita hapus dengan node yang berada di bawahnya.
Agar tidak bingung, mari kita lihat contoh deletion yang berada di bagian tengah tree...

Yang diinginkan adalah untuk menghapus node 60




(keadaan tree dimana node 60 sudah dihapus dan tree sudah seimbang)

Heap & Tries

Heap

Apa sih heap itu? Heap adalah sebuah binary tree komplit data structure yang memenuhi properti-properti dari heap itu sendiri. Node-node yang merupakan node dari heap terurut dengan urutan tertentu. Heap sendiri memiliki beberapa jenis, apa saja?

  1. Minimum Heap
  2. Maximum Heap
  3. Min-Max Heap
Pada dasarnya semua heap itu sama. Pembedanya hanya ada pada letak urutan node nya.

1. Minimum Heap

Urutan minimum heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling besar/maximum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:

Max Heap Example

Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari minimum heap ini merupakan node yang memiliki nilai terkecil di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya.

Berikut adalah step simulasi dalam menyusunan minimum heap hingga urutannya benar:

enter image description here

Dibawah ini adalah step simulasi untuk insert new node ke dalam minimum heap:

Heaps

Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada minimum heap: 

Deletion in a Binary Tree - GeeksforGeeks

2. Maximum Heap

Pada dasarnya, bentuk dari maximum heap ini hampir sama dengan minimum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan maximum heap ini yakni nilai node yang paling besar berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling kecil/minimum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:

Max Heap Example

Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari maximum heap ini merupakan node yang memiliki nilai terbesar di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya, sama seperti minimum heap.

Berikut adalah step simulasi dalam menyusunan maximum heap hingga urutannya benar:

enter image description here


Dibawah ini adalah step simulasi untuk insert new node ke dalam maximum heap:

Heap Sort | All C programming & Algorithm

Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada maximum heap: 

Sort the following data in descending order using Heap sort 20, 14, 50, 3,  5, 7, 11, 8, 12, 15 Show all the steps. Write an algorithm for heap sort.

3. Min-Max Heap

Pada dasarnya, bentuk dari min-max heap ini hampir sama dengan minimum dan maximum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan min-max heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu adalah nilai maximum, minimum, maximum, minimum, dan seterusnya. Nilai node yang akan terletak di paling bawah dari tree ini tidak dapt kita tentukan secara pasti, bisa jadi nilai paling kecil atau nilai paling besar. Hal ini tergantung pada banyaknya data yang kita peroleh. Bisa kita lihat pada gambar di bawah ini:

Delete-max operation in a min-max heap - Stack Overflow
Pada min-max heap ini, nilainya akan terus bersilangan antara maksimum dan minimum nodenya. Secara keseluruhan bentuk insert dan deletion pada heap ini sama saja dengan minimum dan maximum heap. Namun, kita harus benar-benar teliti pada saat menyusun/menyelesaikan heap ini, karena sedikit tricky dan kita terkadang akan tertukar posisinya.

Tries

Apa itu tries? Tries adalah suatu struktur data tree terurut yang digunakan untuk menyimpan array asosiatif. Kalian pasti tahu auto correct dan auto complete yang ada di keypad android kalian kan? Yang pas kita baru ketik beberapa huruf udah muncul kata yang ingin kita ketik ataupun yang bisa membenarkan kata kita apabila ada typo? Nah itu menggunakan tries ini.

Istilah TRIES berasal dari kata RETRIEVAL.

Fakta-Fakta Tentang Tries
  • Tries adalah tree yang setiap simpulnya mewakili satu kata atau awalan dari sebuah kata.
  • Root mewakili karakter kosong(" ") atau NULL.
Untuk lebih lanjut silahkan di lihat dan cermati gambar Tries dibawah....



Secara umum, penyusunan dari tries cukup simple dan mudah, kalian hanya tinggal melihat huruf pertama dari kata yang ingin kalian masukkan, apabila sudah ada huruf dari awalan kata kalian, maka selanjutnya kalian harus memeriksa huruf selanjutnya. Jika tidak ada lagi huruf yang sama, maka kalian tinggal memasukkan sisa huruf dari kata kalian di bawah huruf terakhir. Cukup simple dan mudah bukan?

Sekian...
Terima kasih ^_^
Sampai ketemu di semester selanjutnya :)


Referensi :

  1. http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html?m=1
  2. https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
  3. https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
  4. Binus Maya Power Point
  5. https://www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/tutorial/
  6. https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
  7. https://www.geeksforgeeks.org/deletion-binary-tree/
  8. https://www.geeksforgeeks.org/insertion-and-deletion-in-heaps/
  9. https://www.slideshare.net/HoangNguyen446/heaps-61679009
  10. https://www.geeksforgeeks.org/trie-insert-and-search/
  11. https://allcprogrammingandalgorithm.wordpress.com/heap-sort/
  12. https://www.ques10.com/p/4168/sort-the-following-data-in-descending-order-usin-1/
  13. https://stackoverflow.com/questions/14332279/delete-max-operation-in-a-min-max-heap

Senin, 11 Mei 2020

Heaps and Tries

Heap & Tries

Heap

Apa sih heap itu? Heap adalah sebuah binary tree komplit data structure yang memenuhi properti-properti dari heap itu sendiri. Node-node yang merupakan node dari heap terurut dengan urutan tertentu. Heap sendiri memiliki beberapa jenis, apa saja?

  1. Minimum Heap
  2. Maximum Heap
  3. Min-Max Heap
Pada dasarnya semua heap itu sama. Pembedanya hanya ada pada letak urutan node nya.

1. Minimum Heap

Urutan minimum heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling besar/maximum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:

Max Heap Example

Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari minimum heap ini merupakan node yang memiliki nilai terkecil di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya.

Berikut adalah step simulasi dalam menyusunan minimum heap hingga urutannya benar:

enter image description here

Dibawah ini adalah step simulasi untuk insert new node ke dalam minimum heap:

Heaps

Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada minimum heap: 

Deletion in a Binary Tree - GeeksforGeeks

2. Maximum Heap

Pada dasarnya, bentuk dari maximum heap ini hampir sama dengan minimum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan maximum heap ini yakni nilai node yang paling besar berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling kecil/minimum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:

Max Heap Example

Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari maximum heap ini merupakan node yang memiliki nilai terbesar di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya, sama seperti minimum heap.

Berikut adalah step simulasi dalam menyusunan maximum heap hingga urutannya benar:

enter image description here


Dibawah ini adalah step simulasi untuk insert new node ke dalam maximum heap:

Heap Sort | All C programming & Algorithm

Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada maximum heap: 

Sort the following data in descending order using Heap sort 20, 14, 50, 3,  5, 7, 11, 8, 12, 15 Show all the steps. Write an algorithm for heap sort.

3. Min-Max Heap

Pada dasarnya, bentuk dari min-max heap ini hampir sama dengan minimum dan maximum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan min-max heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu adalah nilai maximum, minimum, maximum, minimum, dan seterusnya. Nilai node yang akan terletak di paling bawah dari tree ini tidak dapt kita tentukan secara pasti, bisa jadi nilai paling kecil atau nilai paling besar. Hal ini tergantung pada banyaknya data yang kita peroleh. Bisa kita lihat pada gambar di bawah ini:

Delete-max operation in a min-max heap - Stack Overflow
Pada min-max heap ini, nilainya akan terus bersilangan antara maksimum dan minimum nodenya. Secara keseluruhan bentuk insert dan deletion pada heap ini sama saja dengan minimum dan maximum heap. Namun, kita harus benar-benar teliti pada saat menyusun/menyelesaikan heap ini, karena sedikit tricky dan kita terkadang akan tertukar posisinya.

Tries

Apa itu tries? Tries adalah suatu struktur data tree terurut yang digunakan untuk menyimpan array asosiatif. Kalian pasti tahu auto correct dan auto complete yang ada di keypad android kalian kan? Yang pas kita baru ketik beberapa huruf udah muncul kata yang ingin kita ketik ataupun yang bisa membenarkan kata kita apabila ada typo? Nah itu menggunakan tries ini.

Istilah TRIES berasal dari kata RETRIEVAL.

Fakta-Fakta Tentang Tries
  • Tries adalah tree yang setiap simpulnya mewakili satu kata atau awalan dari sebuah kata.
  • Root mewakili karakter kosong(" ") atau NULL.
Untuk lebih lanjut silahkan di lihat dan cermati gambar Tries dibawah....



Secara umum, penyusunan dari tries cukup simple dan mudah, kalian hanya tinggal melihat huruf pertama dari kata yang ingin kalian masukkan, apabila sudah ada huruf dari awalan kata kalian, maka selanjutnya kalian harus memeriksa huruf selanjutnya. Jika tidak ada lagi huruf yang sama, maka kalian tinggal memasukkan sisa huruf dari kata kalian di bawah huruf terakhir. Cukup simple dan mudah bukan?

Sekian...
Terima kasih ^_^



Referensi :

Rabu, 29 April 2020

AVL TREE


Apa itu AVL Tree? AVL Tree adalah sebuah tree yang sejenis dengan BST. AVL Tree memiliki perbedaan level antara node yang berada di atas ataupun di bawahnya dengan perbedaan minimum -1 dan perbedaan maksimum 1. Perbedaan ini berlaku untuk subtree node yang berada di kanan ataupun di kiri AVL Tree.

Apa sih guna AVL Tree? AVL Tree muncul untuk menyeimbangkan Binary Search Tree (BST), dengan adanya AVL Tree, proses pencarian yang akan kita lakukan (dalam bentuk tree) akan berlangsung/terproses lebih cepat dibandingkan dengan menggunakan BST.

AVL Tree terdiri atas deletion dan insertion.

Insertion

Kasus - kasus dimana harus dilakukan rotation pada saat ingin menambahkan suatu node baru/insert new node, yaitu:

vio - 1
Keterangan:
  1. Pada kasus 1 dan kasus 2 akan dilakukan single rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.
  2. Pada kasus 3 dan kasus 4 akan dilakukan double rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.

Single Rotation

vio - 2

Double Rotation

vio - 3

Deletion

Kasus dan cara pada saat ingin melakukan deletion:
  1. Node yang ingin dihapus berada di leaf/berada di node paling bawah tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita hanya tinggal langsung menghapus node yang ingin kita hapus/delete tanpa melakukan pengecekan dan pembetulan letak agar node tersebut seimbang.
  2. Node yang ingin dihapus berada di bagian tengah/bagian awal tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita harus menghapus node yang telah dipilih (yang ingin dihapus). Lalu apabila dia memiliki anak, kita harus mengganti node yang telah kita hapus dengan node yang berada di bawahnya.
Agar tidak bingung, mari kita lihat contoh deletion yang berada di bagian tengah tree...

Yang diinginkan adalah untuk menghapus node 60




(keadaan tree dimana node 60 sudah dihapus dan tree sudah seimbang)



Senin, 06 April 2020

Review (1)

Linked List

Linked list adalah struktur data linier dimana elemen tidak di simpan di lokasi memori yang berdekatan.

1. Circular Single Linked List

Circular single linked list adalah suatu linked list yang tidak memiliki nilai NULL untuk medan sambungnya, node yang ada pada akhir circular single linked list akan berisi pointer yang akan menunjuk kepada node yang ada di awal/node pertama. Circular single linked list juga hanya memiliki pointer.

Hasil gambar untuk circular single linked list adalah

Pada gambar di atas, node paling akhir dari linked list tersebut memiliki pointer yang menunjuk dari dirinya sendiri (node terakhir) ke node awal/node pertama kembali.

2. Doubly Linked List

Doubly linked list adalah salah satu jenis linked list yang memiliki pointer 2 arah dan memiliki struktur data yang saling terkait. Linked list ini memiliki 2 pointer penunjuk, 1 pointer menunjuk ke arah node sebelumnya dan yang 1 lagi ke arah node setelahnya.


Dari gambar di atas, doubly linked list terdapat nilai NULL yang berada pada data terakhir/pada tail yang berguna sebagai pertanda data terakhir yang ada di linked tersebut. Doubly linked list berbeda dengan circular single linked list yang tidak memiliki nilai NULL di dalamnya.

Insertion

Ada 4 cara menambahkan node :
  1. Pada bagian depan Doubly Linked List
  2. Setelah node yang di berikan
  3. Pada akhir Doubly Linked List
  4. Sebelum node di berikan

Deletion

4 kondisi yang harus diperhatikan saat deleting node :
  1. Node yang akan di delete adalah node satu-satunya di linked list
  2. Node yang akan di delete adalah awalan/head
  3. Node yang akan di delete adalah akhiran/tail
  4. Node yang akan di delete bukan head/tail
Kita harus memperhatikan kondisi mana yang diinginkan saat kita ingin melakukan deleting pada Doubly Linked List.

Contoh :


(gambar linked list sebelum dilakukan tahap deleting)


(gambar linked list setelah dilakukan tahap deleting)

3. Circular Doubly Linked List

Umumnya, Circular Doubly Linked List itu sama dengan Circular Single Linked List, bedanya terletak pada total pointer pada setiap node yang ada di Circular Doubly Linked List berjumlah 2 pointer.

Circular doubly linked list
Dari gambar di atas, kita dapat melihat perbedaan antara Circular Doubly Linked List dengan Circular Single Linked List.

Contoh Codingan Deklarasi Node :

struct Node { 
 int data; 
 struct Node* next; // Pointer to next node in Doubly Linked List 
 struct Node* prev; // Pointer to previous node in Doubly Linked List 
};

Contoh Codingan Insertion pada Depan (Head) Doubly Linked List :

void push(struct Node* head_ref, int new_data) 
 /* 1. allocate node */
 struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 

 /* 2. put in the data */
 new_node->data = new_data; 

 /* 3. Make next of new node as head and previous as NULL */
 new_node->next = (*head_ref); 
 new_node->prev = NULL; 

 /* 4. change prev of head node to new node */
 if ((*head_ref) != NULL) 
  (*head_ref)->prev = new_node; 

 /* 5. move the head to point to the new node */
 (*head_ref) = new_node; 
}

Stack and Queue

Stack

Stack merupakan sebuah koleksi objek yang menggunakan LIFO (Last In Last Out). Artinya data yang terakhir kali masuk adalah data yang pertama kali/terlebih dahulu keluar.

Stacks

Istilah-istilah yang ada dalam program stack :

  1. Push : berfungsi untuk menambah elemen pada suatu stack
  2. Pop : berfungsi untuk mengambil/menghapus elemen pada suatu stack
  3. Clear : berfungsi untuk mengosongkan stack
  4. IsEmpty : berfungsi untuk mengecek apakah stack sudah kosong atau belum
  5. IsFull : berfungsi untuk mengecek apakah stack sudah penuh

Queue

Queue dapat diartikan sebagai antrian. . Prinsip yang digunakan pada queue adalah FIFO (First In First Out). Artinya, elemen yang pertama kali dimasukkan ke dalam daftar adalah elemen yang pertama kali akan di hapus dari daftar/keluar dari daftar. Pada queue terdapat satu buah pintu masuk di ujung dan satu buah pintu keluar di ujung yang lain. Oleh sebab itu, queue membutuhkan variabel Head dan Tail.

Queue
Operasi-operasi yang dapat digunakan pada queue :
  1. push() : menambahkan suatu item/elemen pada bagian belakang queue
  2. pop() : menghapus suatu item/elemen pada bagian depan queue
  3. front() : mengungkapkan/mengembalikan item paling depan dari queue
Aplikasi-aplikasi yang menggunakan queue :
  1. Deques
  2. Priority Queues
  3. Breadth First Search

Contoh Coding Push pada Stack:

struct Data
{
    int value;
    struct Data *next,*prev;
}*head,*curr,*tail;

void push(int a)
{
    curr = (struct Data*)malloc(sizeof(struct Data));
    curr->value = a;
    
    if(head==NULL){
        head = tail = curr;
    }
    else{
        tail->next = curr;
        curr->prev = tail;
        tail = curr;
    }
    head->prev = tail->next = NULL;
}


void cetak()
{
    curr = head;
    while(curr!=NULL){
        printf("%d\n",curr->value);
        curr = curr->next;
    }
}

int main()
{
    push(10);
    push(20);
    push(30);
    push(40);
   
    cetak();
   
    return 0;
}

Contoh Coding Queue :

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

int peek() {
   return intArray[front];
}

bool isEmpty() {
   return itemCount == 0;
}

bool isFull() {
   return itemCount == MAX;
}

int size() {
   return itemCount;

void insert(int data) {

   if(!isFull()) {
 
      if(rear == MAX-1) {
         rear = -1;           
      }     

      intArray[++rear] = data;
      itemCount++;
   }
}

int removeData() {
   int data = intArray[front++];
 
   if(front == MAX) {
      front = 0;
   }
 
   itemCount--;
   return data; 
}

int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);

   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5
   // ---------------------
   // queue : 3 5 9 1 12 15
 
   if(isFull()) {
      printf("Queue is full!\n"); 
   }

   // remove one item
   int num = removeData();
 
   printf("Element removed: %d\n",num);
   // front : 1
   // rear  : 5
   // -------------------
   // index : 1 2 3 4  5
   // -------------------
   // queue : 5 9 1 12 15

   // insert more items
   insert(16);

   // front : 1
   // rear  : -1
   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15

   // As queue is full, elements will not be inserted.
   insert(17);
   insert(18);

   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15
   printf("Element at front: %d\n",peek());

   printf("----------------------\n");
   printf("index : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Queue:  ");
 
   while(!isEmpty()) {
      int n = removeData();         
      printf("%d ",n);
   } 
 
   return 0;
}

Hashing and Hash Table, Trees, and Binary Tree

Hashing and Hash Table

Hashing


Hashing adalah suatu teknik yang di gunakan untuk mengidentifikasi objek tertentu dari sekelompok objek yang serupa dengan cara yang unik. Hashing merupakan struktur data penting yang dirancang untuk menggunakan suatu fungsi khusus yang di panggil "The Hash Function" yang digunakan untuk memetakan nilai yang telah diberikan dengan kunci tertentu untuk akses ke elemen yang lebih cepat. Efisiensi dari pemetaan ini tergantung dari efisiensi dari "The Hash Function" yang digunakan. 

Hashing di implementasikan ke dalam 2 langkah, yaitu :

1. Elemen dikonversikan kedalam suatu integer dengan menggunakan "Hash Function". Elemen ini dapat digunakan sebagai suatu index untuk menyimpan elemen asli yang jatuh ke hash table.

2. Elemen ini disimpan di hash table dimana dia bisa diambil dengan cepat menggunakan hashed key.

hash = hashfunc(key)
index = hash%array_size

Pada metode ini, hash tidak tergantung pada ukuran array dan kemudian dia akan dikecilkan menjadi suatu index (angka antara 0 dan array_size - 1) dengan menggunakan operator modulo (%).

Hash Table

Hash table adalah suatu struktur data yang digunakan untuk menyimpan keys/value pairs. Hash table menggunakan suatu hash function (fungsi hash) untuk menghitung suatu index ke dalam suatu array dimana suatu elemennya akan dimasukkan atau dicari.

Hash table adalah sebuah tabel yang berbetuk array dimana di dalamnya kita menyimpan string asli. Indeks dari tabelnya adalah hashed key sementara nilainya adalah nilai dari string asli. 

Ukuran dari hash table biasanya beberapa urutan yang besarannya lebih rendah daripada jumlah total dari string yang memungkinkan. Jadi, beberapa string mungkin akan memiliki kunci hash (hashed key) yang sama.

Operasi dasar yang ada dalam hash table :
  • Search
  • Insert
  • Delete

Deklarasi Data Item yang Akan Digunakan dalam Hash Table :

struct DataItem {
   int data;
   int key;
};

Contoh Coding Search Operation :

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
 
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
   
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;     

}

Contoh Coding Insert Operation :

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;
   item->key = key;   

   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }
 
   hashArray[hashIndex] = item;     

}

Contoh Coding Delete Operation :

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] !=NULL) {
 
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex];
   
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem;
         return temp;
      }
  
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }
 
   return NULL;     

}

Hash Function

Hash function adalah suatu fungsi yang mengubah nomor telepon yang besar menjadi nilai integer praktis yang kecil. Suatu hash function memetakan sejumlah angka atau string yang besar kedalam suatu integer yang kecil yang dapat digunakan sebagai index di dalam hash table.

Hash function yang baik harus memiliki properti sebagai berikut :
  1. Dihitung secara efisien
  2. Harus mendistribusikan kunci(keys) secara seragam (setiap posisi tabel memiliki kemungkinan yang sama untuk setiap kunci)
Ada banyak cara untuk meng-hash suatu string ke dalam suatu key. Berikut ini adalah beberapa method-method penting untuk membangun fungsi hash, yaitu :
  • Mid-square
  • Division (paling umum)
  • Folding
  • Digit Extraction
  • Rotating Hash

Collision

Dalam bahasa indonesia, collision dikenal sebagai tabrakan. Dikarenakan fungsi hash memberikan kita sebuah angka kecil untuk sebuah kunci(key) yang merupakan bilangan integer besar atau string. Ada kemungkinan bahwa dua kunci(key) menghasilkan nilai yang sama.

Ada 2 cara untuk menangani Collision, yaitu :
  1. Linear Probing
  2. Chaining

Linear Probing

Dilakukan dengan mencari slot yang kosong yang terletak setelah slot yang terisi dan menaruh string nya disana. Dia akan mencari terus hingga mendapatkan slot yang kosong.

Chaining

Dilakukan dengan menaruh string di dalam sebuat slot sebagai sebuah chained list(linked list).

Contoh Coding Liner Probing :

struct { ... } node;

node Table[M]; int Free;
/* insert K */
addr = Hash(K);

if (IsEmpty(addr)) Insert(K,addr);
else {
/* see if already stored */

test:
if (Table[addr].key == K) return;
else {
addr = Table[addr].link; goto test;}
/* find free cell */
Free = addr;

do { Free--; if (Free<0) Free=M-1; }
while (!IsEmpty(Free) && Free!=addr);

if (!IsEmpty(Free)) abort;
else {
Insert(K,Free); Table[addr].link = Free;
}

}

Tree and Binary Tree

Tree

Tree merupakan struktur data yang tidak linear yang digunakan untuk merepresentasikan data yang bersifat hirarki antara elemen-elemennya. Definisi tree yaitu kumpulan elemen yang salah satu elemennya disebut root(akar) dan elemen yang lain disebut simpul(node) yang terpecah menjadi sejumlah kumpulan yang tidak saling berhubungan satu dengan yang lain yang disebut sub-tree atau cabang.



Image result for istilah dalam tree

Binary Tree

Tree yang unsurnya paling banyak 2 anak disebut Binary Tree. Karena setiap elemen dalam pohon biner hanya dapat emiliki 2 anak, biasanya anak tersebut akan dinamakan left dan right child.

Node dari Binary Tree berisi dari beberapa bagian, yaitu :
  1. Data
  2. Pointer to left child
  3. Pointer to right child
Node yang tidak memiliki anak disebut leaf.

Jenis-jenis Binary Tree
  • Full Binary Tree
Binary tree yang tiap node-nya(kecuali leaf) memiliki 2 anak dan tiap sub-tree harus mempunyai panjang path yang sama.

  • Complete Binary Tree
Mirip dengan Full Binary Tree, namun setiap sub-tree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

  • Skewed Binary Tree
Binary tree yang semua nodenya (kecuali leaf) memiliki 1 child.

  • Binary Search Tree (BST)
Jenis pohon terurut yang digunakan unruk menyimpan data sehingga memudahkan pencarian kembali data tersebut.


Operasi Pada Tree
  • Create
Digunakan untuk membentuk binary tree baru yang masih kosong.
  • Clear
Digunakan untuk mengosongkan binary tree yang sudah ada.
  • Empty
Diguakan untuk memeriksa apakah binary tree masih kosong.
  • Insert
Digunakan untuk memasukkan sebuah node ke dalam tree.
  • Find
Digunakan untuk mencari root, parent, left child, atau right child dari suatu node dengan syarat tree tidak boleh kosong.
  • Update
Digunakan untuk mengubah isi dari node yang ditunjuk oleh pointer cureent dengan syarat tree tidak boleh kosong.
  • Retrive
Digunakan untuk mengetahui isi dari node yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.
  • Delete Sub
Digunakan untuk menghapus sebuah sub-tree (node beserta seluruh descendant-nya) yang ditunjuk pointer current dengan syarat tree tidak oleh kosong.
  • Characteristic
Digunakan untuk mengetahui karakteristik dari suatu tree (size, height, serta everage length-nya).
  • Traverse
Digunakan untuk mengunjungi seluruh node-node pada tree, masing-masing sekali.

Threaded Binary Tree Example


Image result for threaded binary tree example
Keuntungan
  • Memungkinkan lintasan linear elemen di tree
  • Tranversal linear menghilangkan penggunaan tumpukan yang pada gilirannya akan mengkonsumsi banyak ruang memori dan waktu komputer
  • Memungkinkan untuk menemukan induk dari elemen yang diberikan tanpa menggunakan pointer parent secara eksplisit
  • Karena node berisi pointer ke pendahulu dan penerus di in-order, tree berulir memungkinkan traversal maju dan mundur dari node seperti yang diberikan oleh mode in-order.

Contoh Coding Binary Tree

#include <stdio.h>
#include <stdlib.h>

//inisialisasi struct
struct data{
 int number;
 //pointer untuk menampung percabangan kiri dan kanan
 data *left, *right;
}*root;

//fungsi push untuk menambah data
void push(data **current, int number){
 //jika pointer current kosong maka akan membuat blok data baru
 if((*current)==NULL){
  (*current) = (struct data *)malloc(sizeof data);
  //mengisi data
  (*current)->number=number;
  (*current)->left = (*current)->right = NULL;
 //jika tidak kosong, maka akan dibandingkan apakah angka yang 
 //ingin dimasukkan lebih kecil dari pada root
 //kalau iya, maka belok ke kiri dan lakukan rekursif 
 //terus menerus hingga kosong
 }else if(number < (*current)->number){
  push(&(*current)->left, number);
 //jika lebih besar, belok ke kanan
 }else if(number >= (*current)->number){
  push(&(*current)->right, number);
 }
}

//preOrder : cetak, kiri, kanan
void preOrder(data **current){
 if((*current)!=NULL){
  printf("%d -> ", (*current)->number);
  preOrder(&(*current)->left);
  preOrder(&(*current)->right);
 }
}

//inOrder : kiri, cetak, kanan
void inOrder(data **current){
 if((*current)!=NULL){
  inOrder(&(*current)->left);
  printf("%d -> ", (*current)->number);
  inOrder(&(*current)->right);
 }
}

//postOrder : kiri, kanan, cetak
void postOrder(data **current){
 if((*current)!=NULL){
  postOrder(&(*current)->left);
  postOrder(&(*current)->right);
  printf("%d -> ", (*current)->number);
 }
}

//searching data
void search(data **current, int number){
 //jika pointer current memiliki data
 if((*current)!=NULL){
  //cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
  if(number<(*current)->number){
   search(&(*current)->left,number);
  //jika lebih besar, maka belok ke kanan
  }else if(number>(*current)->number){
   search(&(*current)->right,number);
  //jika sama dengan, maka angka ketemu
  }else{
   printf("Found : %d", (*current)->number);
  }
 //jika tidak ada data lagi (not found)
 }else{
  printf("Not Found.");
 }
}

void main(){
 push(&root, 11);
 push(&root, 22);
 push(&root, 13);
 push(&root, 15);
 push(&root, 9);
 inOrder(&root);
 printf("\n");
 preOrder(&root);
 printf("\n");
 postOrder(&root);
 printf("\n");
 search(&root,91);
 getchar();
}

Binary Search Tree

200px-Binary_search_tree.svg


Binary Search Tree atau BST adalah suatu struktur data binary tree (pohon biner) yang berbasis simpul. binary Search Tree memiliki beberapa properti, seperti :

  • Subtree kiri dari suatu node hanya berisi node-node dengan kunci yang lebih rendah daripada kunci node (node key).
  • Subtree kanan dari suatu node hanya berisi node-node dengan kunci yang lebih besar daripada kunci node (node key).
  • Subtree kiri dan kanan masing-masing juga harus berupa sebuah Binary Search Tree.
*dengan asumsi kunci berbeda.

Binary Search Tree (BST) adalah salah satu struktur data yang mendukung pencarian yang lebih cepat, penyortiran yang cepat, dan penyisipan (insertion) dan penghapusan (deletion) yang lebih mudah. Binary Search Tree (BST) juga dikenal sebagai Sorted Version of Binary Tree.

Basic operation yang ada pada Binary Search Tree (BST), yaitu :
  • Search
  • Insert
  • Deletion
  • Pre-Order Traversal
  • In-Order Traversal
  • Post-Order Traversal
Yang akan dibahas ada 3, yaitu :
  1. Insertion
  2. Searching
  3. Deletion

Contoh Codingan :

struct node* search(struct node* root, int key) 
    // Base Cases: root is null or key is present at root 
    if (root == NULL || root->key == key) 
       return root; 
     
    // Key is greater than root's key 
    if (root->key < key) 
       return search(root->right, key); 
  
    // Key is smaller than root's key 
    return search(root->left, key); 
}

Insertion

Kunci (key) baru akan selalu dimasukkan (di insert) di daun. Kita memulai untuk mencari sebuah kunci (key) dari root/akar sampai menyentuh sebuah leaf node. Sekali sebuah leaf node ditemukan, node baru akan ditambahkan sebagai anak dari leaf node.

Contoh Codingan :

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key) 
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key); 
  
    /* Otherwise, recur down the tree */
    if (key < node->key) 
        node->left  = insert(node->left, key); 
    else if (key > node->key) 
        node->right = insert(node->right, key);    
  
    /* return the (unchanged) node pointer */
    return node; 
}

Deletion

Ada 3 kasus yang harus di pertimbangkan :
  1. Jika kunci (key) berada di leaf, hapus saja node itu.
  2. Jika kunci (key) ada di sebuah node yang tidak memiliki chid, hapus node tersebut dan hubungkan child dengan parent nya.
  3. Jika kunci (key) ada di node yang memiliki 2 children (anak), temukan child yang paling kanan dari sub-tree (simpul P), ganti kuncinya dengan kunci P dan delete P secara rekursif. Atau bisa secara bergantian memilih child paling kiri dari sub-tree kanan.

Contoh Codingan :

/* Given a binary search tree and a key, this function deletes the key 
   and returns the new root */
struct node* deleteNode(struct node* root, int key) 
    // base case 
    if (root == NULL) return root; 
  
    // If the key to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    if (key < root->key) 
        root->left = deleteNode(root->left, key); 
  
    // If the key to be deleted is greater than the root's key, 
    // then it lies in right subtree 
    else if (key > root->key) 
        root->right = deleteNode(root->right, key); 
  
    // if key is same as root's key, then This is the node 
    // to be deleted 
    else
    { 
        // node with only one child or no child 
        if (root->left == NULL) 
        { 
            struct node *temp = root->right; 
            free(root); 
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            struct node *temp = root->left; 
            free(root); 
            return temp; 
        } 
  
        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        struct node* temp = minValueNode(root->right); 
  
        // Copy the inorder successor's content to this node 
        root->key = temp->key; 
  
        // Delete the inorder successor 
        root->right = deleteNode(root->right, temp->key); 
    } 
    return root; 
}

Contoh Coding Deklarasi Awal

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
 
   while(current->data != data){
 
      if(current != NULL) {
         printf("%d ",current->data);
   
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }
   //else go to right tree
         else {                
            current = current->rightChild;
         }
   
         //not found
         if(current == NULL){
            return NULL;
         }
      }   
   }
   
   return current;
}

Contoh Codingan untuk Insert Operation

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
   
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;  
                 
            //insert to the left 
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
   //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Referensi :
  • https://computerscience4lyfe.blogspot.com/2020/02/linked-list.html
  • https://computerscience4lyfe.blogspot.com/2020/03/stack-and-queue.html
  • https://computerscience4lyfe.blogspot.com/2020/03/hashing-and-hash-table-trees-binary-tree.html
  • https://computerscience4lyfe.blogspot.com/2020/03/binary-search-tree.html

Review Final

Nama : Indah Islamiana Sinurat NIM : 2301906003 Kelas : CB01 Dosen : Ferdinand Ariandy Luwinda (D4522) Henry Chong (D4460) AVL T...