Summary Binary Search Tree

Binary Search Tree  adalah struktur data pohon biner berbasis simpul yang memiliki properti berikut:

•          Subtree kiri dari sebuah node hanya berisi node dengan kunci lebih rendah dari kunci node.
•          Subtree kanan sebuah node hanya berisi node dengan kunci lebih besar dari kunci node.
•          Subtree kiri dan kanan masing-masing juga harus berupa pohon pencarian biner.

Cara mengubah array menjadi binary search tree :

#include<stdio.h>

#include<stdlib.h>

 

struct TNode

{

    int data;

    struct TNode* left;

    struct TNode* right;

};

 

struct TNode* newNode(int data);

struct TNode* sortedArrayToBST(int arr[], int start, int end)

{

    /* Base Case */

    if (start > end)

      return NULL;

 

    int mid = (start + end)/2;

    struct TNode *root = newNode(arr[mid]);

 

    root->left =  sortedArrayToBST(arr, start, mid-1);

    root->right = sortedArrayToBST(arr, mid+1, end);

 

    return root;

}

struct TNode* newNode(int data)

{

    struct TNode* node = (struct TNode*)

                         malloc(sizeof(struct TNode));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

 

    return node;

}

 

void preOrder(struct TNode* node)

{

    if (node == NULL)

        return;

    printf("%d ", node->data);

    preOrder(node->left);

    preOrder(node->right);

}

int main()

{

    int arr[] = {1, 2, 3, 4, 5, 6, 7};

    int n = sizeof(arr)/sizeof(arr[0]);

 

    struct TNode *root = sortedArrayToBST(arr, 0, n-1);

    printf("PreOrder Traversal of constructed BST ");

    preOrder(root);

 

    return 0;

}

Operasi yang dapat dilakukan dalam binary serach tree :

• -         Insert  => memasukkan data kedalam binary search tree
• -          Delete => menghapus node data dari binary tree
• -          Search => mencari data tersebut
• -          Print  => memperlihatkan data yang sudah disimpan

Apakah kegunaan binary search tree ?

Untuk mempermudah mengakses dan menyimpan data. Contohnya :

Ok, langsung saja kecontohnya. Misal kita memiliki urutan angka yang dimasukkan kedalam data dengan urutan sebagai berikut : 4 2 7 1 3 . Bagaimana binary tree nya akan terbentuk ? Binary tree nya akan berbentuk seperti berikut :

       4

       / \

      2   7

     / \

    1   3

Aturan saat “insert” kedalam binary tree ini adalah dengan membandingkan data yang akan dimasukkan dengan kondisi root saat itu. Ok, mari kita telaah ! angka pertama yang akan menjadi “root” adalah 4, maka angka tersebut akan menjadi paling atas. Lalu berikut nya 2, nah disini kita akan membandingkan 2 dengan 4, 2 lebih kecil dibanding 4, maka dia akan diletakkan dikir. Lalu 7, karena 7 lebih besar dari 4, maka 7 diletakkan disebelah kanan. Lalu 1, 1 lebih kecil dibandingkan 4 maka akan masuk ke sebelah kiri, namun karena sebelah kiri sudah memiliki “root” yaitu 2, maka 1 akan dibandingkan kembali dengan 2, karena 1 lebih kecil dibandingkan dengan 2, maka 1 diletakkan disebelah kiri dari 2. Begitu juga berlaku dengan 3.

Dari, penjelasan diatas, dapat disimpukan bahwa binary tree saat “insert” data mengurutkan datanya terlebih dahulu. Lalu apa hubungannya dengan pertanyaan “Apa kegunaan binary tree dalam pemrograman ? ”. Kita ambil kasus simple saja, kita diminta untuk menangani deretan angka yang tidak berurutan, lalu diminta untuk menentukan manakah angka yang terbesar, dengan mudah kita akan langsung mengambil data yang paling kanan sampai tidak memiliki cabang lagi. Kenapa bisa seperti itu ? karena otomatis angka yang memiliki posisi paling kanan dan sudah tidak memiliki cabang dialah angka yang paling besar.

refrensi :

https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/

https://www.geeksforgeeks.org/binary-search-tree-data-structure/#construction

Hash Table dan Binary Tree

1. Hash table

hash table adalah salah satu jenis struktur data yang menerapkan konsep penggunaan suatu fungsi
sebagai pemetaan nilai kunci yang unik dari value suatu data menjadi suatu indeks yang merupakan lokasi dari data tersebut. Hash table digunakan untuk mempercepat proses akses data. Contohnya, bila terdapat data yang ingin di simpan dalan suatu array :
data :
- Andre # 15
- William # 28
- Mona # 20
dan data tersebut dibuatkan hash function f(x) = (jumlah ASCII nama)%10, dimana x merupakan string nama. maka Mona yang berumur 20 akan disimpan didalam array dengan indeks bernomor 5.
sehingga jika ingin dilakukan akses data mona maka tidak perlu dilakukan lienar search dan dapat langsung mengakses array indeks kelima.

fungsi hash pada blockchain digunakan dalam kriptografi. hasing sangat cepat dan tepat sehingga sangat ideal untuk kriptografi dan masih digunakan sampai sekarang.

kode untuk menyimpan :

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

struct node{
int age;
char name[100];
node *next;
};

struct hash{
node *head;
node *tail;
};

int getIndex(char input[]){
int sum = 0;
for(int i=0; input[i]!='\0'; i++){
sum = sum + input[i];
}
sum = sum%10;
return sum;
}

void push(node **head, node **tail, int umur, char nama[]){
node *temp = (node*)malloc(sizeof(struct node));
strcpy(temp->name, nama);
temp->age = umur;
if(*head == NULL){
*head = temp;
*tail = temp;
}else{
(*tail)->next = temp;
*tail = temp;
}
(*tail)->next = NULL;
}

void displayList(struct node *curr){
while(curr!=NULL){
printf("%s#%d-->", curr->name, curr->age);
curr = curr->next;
}
printf("NULL\n");
return;
}

int main(){
int umur;
char nama[100];
hash array_hash[10];
//initialize all head ans tail = NULL;
for(int i=0; i<10; i++){
array_hash[i].head = NULL;
array_hash[i].tail = NULL;
}

do{
system("cls");
for(int i=0; i<10; i++){
printf("%d| ", i);
displayList(array_hash[i].head);
}
printf("\n");

printf("insert nama ==> ");
scanf("%[^\n]", nama);getchar();
printf("insert umur ==> ");
scanf("%d", &umur);getchar();
int index = getIndex(nama);
printf("masuk index %d\n", index);
push(&array_hash[index].head, &array_hash[index].tail, umur, nama);

//displaying array_hash content


}while(true);

}




2. Binary Tree

binary tree atau pohon biner merupakan jenis struktur data yang menimpan data dalam bentuk hirearki. Setiap data dinamakan node, setiap node memiliki anak cabang kiri dan anak cabang kanan. Node paling pertama dinamakan Root dan node paling terakhir dinamakan Leaf. Operasi yang dapat dilakukan dalam suatu pohon biner adalah :
- insert : memasukknan data pada cabang kosong
- remove : menghapus suatu cabang tertentu
- create : membuat cabang baru


Sumber :
https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/
https://www.geeksforgeeks.org/hashing-data-structure/

Summary Stack and Queue

Stack merupakan jenis data structure yang menyimpan data secara linear dengan penerapan konsep LIFO (Last In First Out), artinya data yang terkahir masuk merupakan data yang pertama kali dikeluarkan. Stack dapat diibaratkan dengan tumpukan piring dimana piring yang terakhir kali ditambahkan merupakan piring yang pertama kali diambil dari tumpukan tersebut. Implementasi stack dapat berupa linked list, array of struct, atau array. Jenis operasi yang dapat dilakukan pada suatu stack :
- pop (menghapus data paling terakhir ditambahkan)
- push (menambahkan data kedalam stack)

Queue merupakan jenis data structure yang menyimpan data secara linear dengan penerapan konsep FIFO (First In First Out), artinya data yang pertama dimasukkan merupakan data yang terakhir kali dikeluarkan. Queue dapat diibaratkan seperti sebuah antrian. Orang yang pertama kali masuk ke dalam antrian merupakan orang yang pertama keluar dari antrian tersebut. Implementasi queue dapat berupa linked list, array of struct, atau array. Jenis operasi yang dapat dilakukan pada suatu queue :
- pop (menghapus data paling pertama ditambahkan)
- push (menambahkan data pada akhir queue)

sumber :
- https://www.geeksforgeeks.org/stack-data-structure/#operations
- https://www.geeksforgeeks.org/queue-data-structure/

Summary Linked List

by William Kurnia Mulyadi Putra/2301887521

1. Pengenalan Linked List

   Berdasrkan yang telah saya pelajari saya dapat menyimpulkan bahwa linked list suatu metode yang digunakan untuk menggantikan array agar menjadi lebih hemat memory. Linked list pada bahasa C dapat dibuat menggunakan struct{};

2. Perbedaan Linked List dengan Array

    keunggulan linked list dengan array :

• Linked list merupakan dynamic programming, artinya memory yang diperlukan sesuai dengan yang digunakan, sehingga linked list lebih hemat memory. 
• Memory yang diperlukan dapat dialokasikan pada saat program sedang berjalan, sedangkan memory yang diperlukan oleh array perlu dialokasikan sebelum program dicompile.

    kelemahan linked list terhadap array :

• kita tidak dapat melakukan random access pada saat menggunakan linked list, misanya :

tertdapat program :

#include <stdio.h>

int main (){

     int array[5] = {1,2,3,4,5};

//jika ingin mengubah array pada index kedua maka dapat dilakukan random //acces

Array[2] = 0;

//sehingga anggota array berubah menjadi {1,2,0,4,5};

         

   Tetapi dalam menggunakan linked list, kita harus mengkases anggota dimulai dari anggota terawal dan mengkases satu demi satu sampai mendapatkan anggota tujuan.

3. Cara Membuat Linked List Menggunakan Bahasa C

   Dalam bahasa C linked list dibuat dengan cara membuat sebuah struct{}; . Pada umumnya struktur linked list terdiri atas dua :

-         data yang disimpan linked list

-         pointer ke listnode selanjutnya

dalam bentuk kode ;

#include <stdio.h>

struct node {

   //data node

   node *next_node;

};

Setiap individu struct pada suatu linked list dinamakan node. Node terdepan pada suatu linked list diberikan nama head, sedangkan node terbelakang pada suatu linked list dinamakan tail. Hal – hal yang dapat dilakukan pada suatu linked list adalah menambahkan data dan menghapus data.

Cara memasukkan data di linked list terbagi menjadi 3 cara :

-         memasukkan data pada awal linked list

sebagai contoh, terdapat kode seperti berikut :

#include<stdio.h>

struct node {

          int data;

          node *next;

};

int main (){

int input;

          struct node *head = NULL;

          struct node *tail  = NULL;

         

printf("Inset data ==> ");

          scanf("%d", &input);getchar();

push_head(&head, input, &tail);

          return 0;

}

Maka untuk melakukan penambahan data pada head linked list :

void push_head (struct node **head, int value, struct node **tail){

          node *temp = (node*)malloc(sizeof(struct node));

          temp->data = value;

          if(*head == NULL){

                   temp->next = NULL;

                   *head = temp;

                   *tail = temp;

          }else{

                   temp->next = *head;

                   *head = temp;

          }

         

}

-         memasukkan data pada akhir linked list

sebagai contoh, terdapat kode seperti berikut :

#include<stdio.h>

struct node {

          int data;

          node *next;

};

int main (){

int input;

          struct node *head = NULL;

          struct node *tail  = NULL;

         

printf("Inset data ==> ");

scanf("%d", &input);getchar();

push_tail(&head, input, &tail);

          return 0;

}

Maka untuk melakukan penambahan data pada tail linked list :

void push_tail(struct node **head, int value, struct node **tail){

          node *temp = (node*)malloc(sizeof(struct node));

          temp->data = value;

          if(*head == NULL){

                   temp->next = NULL;

                   *head = temp;

                   *tail = temp;

          }else{

                   node *prev =  *tail;

                   temp->next = NULL;

                   prev->next = temp;

                   *tail = temp;

          }       

}

Cara menghapus data pada suatu linked list :

Sebagai contoh, terdapat kode seperti berikut :

#include<stdio.h>

struct node {

          int data;

          node *next;

};

Terdapat linked list berisis 1à2à3à4à5àNULL.

Maka kode untuk menampilkan isi linked list pada console adalah :

void display(struct node *current){

          if(current == NULL){

                   printf("Empty list\n");

          }else{

                   while(current!=NULL){

                             printf("%d-->", current->data);

                             current = current->next;

                   }

                   printf("[NULL]\n");

          }

         

}

Maka output yang ditampilkan pada console adalah :

1-->2-->3-->4-->5-->[NULL]

4. Jenis-Jenis Linked List

terdapat 4 jenis linked list yaitu :

- singly linked list -> merupakan linked list dimana setiap node hanya terhubung dengan node selanjutnya dan node terakhir memiliki pointer NULL.

- doubly linked list -> merupakan linked list dimana setiap node hanya terhubung dengan node selanjutnya dan node sebelumnya. Node terakhir memiliki pointer NULL.

-circular linked list -> merupakan linked list dimana setiap node hanya terhubung dengan node selanjutnya dan node terakhir memiliki pointer yang menunjuk ke node pertama.

-circular doubly linked list -> merupakan linked list dimana setiap node hanya terhubung dengan node selanjutnya dan node sebelumnya. Node terakhir memiliki pointer yang menunjuk ke node pertama.

sumber :

- https://www.geeksforgeeks.org/data-structures/linked-list/

-https://www.youtube.com/watch?v=njTh_OwMljA&t=189s