Selasa, 10 Maret 2020

Hash Table and Binary Trees


Ø  Hash table
            Jadi, apa itu hash table? hash table merupakan sebuah fungsi dalam struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Keunggulan dari struktur hash table ini yaitu memiliki waktu pengaksesan data yang cepat. Namun kekurangannya ialah sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (collision).Maka dari itu perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam table agar angka – angka hash tidak saling bertabrakan (collision). Berikut hal – hal yang dapat dilakukan untuk menghindari collision :
           
·         Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :
1.      Linear Probing
Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1) mod m.
2.      Quadratic Probing
Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.
3.      Double hashing
Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri.
Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.
·         Open hashing (Separate Chaining)

Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.
Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.

Ø  Binary tree
Lalu, apa itu binary tree? Binary tree merupakan sebuah fungsi pada data structure (sama seperti hash table) namun memiliki konsep yang berbeda. Seperti Namanya, binary tree merupakan salat Satu bentuk Struktur Data tidak linier 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 tak saling berhubungan Satu sama lainnya (disebut subtree). Berikut merupakan macam – macam pengoperasian binary tree :
1.      Create 
     Membentuk binary tree baru yang masih kosong
2.      Clear 
     Mengosongkan binary tree yang sudah ada
3.       Empty 
     Function untuk memeriksa apakah binary tree masih kosong Insert Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert : sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong
4.      Find 
     Mencari root, parent, left child, atau right child dari suatu node. (tree tidak boleh kosong).
5.      Update 
     Mengubah isi dari node yang ditunjuk oleh pointer curret
(Tree tidak boleh kosong)
6.      Retrieve 
     Mengetahui isi dari node yang ditunjuk oleh pointer current
(Tree tidak boleh kosong)
7.      DeleteSub 
     Menghapus sebuah subtree (node beserta seluruh descendantnya)
yang ditunjuk current. Tree tidak boleh kosong. Setelah itu, pointer current dakan berpindah ke parent dari node yang dihapus.
8.      Characteristic 
     Mengetahui karakteristik dari suatu tree, yakni: size, height, serta average length. Tree tidak boleh kosong.
9.      Traverse 
     Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linear yang
tersimpan dalam tree. Ada tiga cara traverse,yaitu PreOrder, InOrder, dan PostOrder.
Berikut langkah – langkah dalam membaut traverse :
1)      PreOrder : 
cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child
2)       InOrder : 
kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right C
3)      PostOrder : 
kunjungi Left Child, kunjungi Right Child cetak isi node yang dikunjungi.


Diposting oleh di Tidak ada komentar:

Selasa, 03 Maret 2020

Double Linked List II


Summary Double Linked List Pertemuan 2
(Tambah pop serta push Mid)

                Menurut pengertian dari materi power point binus, double linked list merupakan linked list dengan dua tautan, dimana tautan yang pertama bereferensi pada data selanjutnya sedangkan tautan selanjutnya bereferensi pada tautan sebelumnya. Pada double linked list (referensi ppt bimay) terdapat 2 fungsi, yaitu insert dan delete. Insert dan delete dapat juga kita sebut dengan istilah push dan pop, dimana push berarti insert dan pop berarti delete.Istilah tersebut juga saya dapatkan dari dosen kelas besar CA-01 yang disampaikan oleh bapak fidelson. Push dan pop sendiri masing - masing memiliki tipe yang akan saya jelaskan beserta codenya.
1)      Push
Fungsi push berfungsi untuk menambah nilai node (data) dari barisan paling awal dan akhir.
·         PushHead
Merupakan fungsi push yang bertujuan menambah data melalui barisan awal.Contoh pengimplementasian ialah sebagai berikut:
Jika kita memiliki input data yaitu 1 2 3 4, maka output yang akan dihasilkan oleh pushhead ini adalah  4 3 2 1.
Contoh code :
                void pushhead(int x){
                curr = (struct data*)malloc(sizeof(struct data));
                curr->x = x;
                if(head==NULL){
                                head = tail = curr;
                }else{
                                curr->next = head;
                                head->prev = curr;
                                head->curr;
                }
                head->prev = NULL;
                tail->next=NULL;
}
·         PushMid
Merupakan fungsi push yang bertujuan menambah data melalui barisan tengan. Contoh pengimplementasiannya ialah sebagai berikut :
                Jika kita memiliki data yaitu 1 2 3 4 5 dan kita ingin menginput nilai 3 maka outputnya adalah 1 2 3 3 4 5.
                Contoh codenya

Void PushMid(int age, char name[]){
                if(head==NULL){
                                //pushHead
                                pushHead(age,name);
                }else if(age < head->age){
                                //pushHead
                                pushHead(age,name);
                }else if(age > tail->age){
                                pushTail(age,name);
                }else{
                                current = (struct human *)malloc(sizeof human);
                                strcpy(current->name, name);
                                current->age = age;
                                current->next = current->prev = NULL;
                               
                                struct human *temp=head;
                                while(temp!=NULL && temp->age < current->age){
                                                temp=temp->next;
                                }
                                current->prev=temp->prev;
                                current->next=temp;
                                temp->prev->next=current;
                                temp->prev=current;
                }
}                             

·         PushTail
Merupakan fungsi push yang bertujuan menambah data melalui barisan akhir. Contoh pengimplementasiannya ialah sebagai berikut :
Jika kita memiliki input data 1 2 3 4, maka output yang akan dihasilkan oleh pushtail adalah 1 2 3 4.
Contoh code :
                void pushhead(int x){
                curr = (struct data*)malloc(sizeof(struct data));
                curr->x = x;
                if(head==NULL){
                                head = tail = curr;
                }else{
                                curr->prev = tail;
                                tail->prev = curr;
                                tail->curr;
                }
                head->prev = NULL;
                tail->next=NULL;
}
2)      Pop
Fungsi pop merupakan kebalikan dari fungsi push yang dimana fungsi ini bertujuan untuk menghapus suatu nilai atau data. Pop memiliki 3 tipe yaitu Pophead dan Poptail.
·         PopHead
Merupakan fungsi yang dimana fungsi tersebut akan menghapus suatu nilai atau data melalui barisan paling depan.
Contoh Code:
                void pophead(){
                                If(head!==NULL){
                                                If(head==tail){
                                                                free(head);
                                                                head=NULL;
                                                }else{
                                                                curr = head;
                                                                head = head -> next;
                                                                free(curr);
                                                                head->prev = NULL;
                                }
                }
}
·         PopMid
Merupakan fungsi pop yang dimana berfungsi untuk menghapus suatu nilai data melalui tengah.
Berikut contoh codenya :

void popMid(int age){
                int temu=0;
                if(head==NULL){
                                printf("No Data\n");
                }else{
                                current=head;
                                while(current!=NULL){
                                                if(current->age==age){
                                                                temu=1;
                                                                break;
                                                }
                                                current=current->next;
                                }
                                if(temu==1){
                                                if(current==head){
                                                popHead();
                                                }else if(current==tail){
                                                popTail();
                                                }else{
                                                current->prev->next=current->next;
                                                current->next->prev=current->prev;
                                                                free(current);
                                                }
                                }else{
                                                printf("Data Not Found\n");
                                }
                }
}

                                                               
·         Poptail
Merupakan fungsi pop yang dimana fungsi tersebut akan menghapus suatu nilai atau data dari barisan yang paling belakang.
Contoh code:
                void pophead(){
                                If(head!==NULL){
                                                If(head==tail){
                                                                free(head);
                                                                head=NULL;
                                                }else{
                                                                curr = tail->prev;
                                                                free(tail);
                                                                tail = curr;
                                                                tail->next = NULL;
                                }
                }
}
Stack(tumpukan) sendiri merupakan fungsi yang penting dalam penggunaan data struktur yang berfungsi untuk menyimpan elemen secara teratur dengan konsep LIFO(Last In First Out). Sedangkan Queue adalah prinsip antrian yang sama seperti stack namun memiliki konsep yang berbeda yaitu FIFO(First In First Out).


                Demikian review pertemuan yang dapat saya buat, Terima kasih.



Referensi :
Ø  Materi Binus Maya
Ø  https://socs.binus.ac.id/2017/03/15/doubly-linked-list/

Diposting oleh di Tidak ada komentar:
Langganan: Komentar (Atom)