AVL Tree

            Jadi, apa itu AVL Tree? AVL Tree merupakan bentuk yang lebih advance atau terusan dari Binary Search Tree yang memiliki batas toleransi tinggi maksimal 1 antara subtree kiri dan subtree kanan dengan tujuan untuk menyeimbangkan serta mempermudah dalam pengoperasian Binary Search Tree. Dengan AVL Tree, waktu pencarian suatu data serta bentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga sebuah tree tetap seimbang meskipun telah disisipi nodes, maka perlu dilakukan pemeriksaan node baru dengan root. Jika node pertama memiliki balance factor lebih dari satu, maka perlu dilakukan penyetaraan. Ada dua jenis penyetaraan yang dapat dilakukan, yaitu single serta double rotation.

·               Single Rotation

Kapan kita harus menggunakan single rotation? Pada dasarnya kita akan menggunakan single rotation jika kondisi AVL Tree searah. Berikut contoh pengimplementasiannya :

·              Double Rotation

Pada beberapa soal di AVL tree umumnya dapat diselesaikan  hanya  dengan  cara  single rotation, seperti pada contoh diatas.  Tetapi ada beberapa soal yang tidak bisa diselesaikan jika kita hanya menggunakan single rotation.  Berarti kita harus  menggunakan  teknik double rotation untuk menyelesaikan masalah imbalance pada tree Berikut contoh pengimplementasiannya :

 Sekian rangkuman saya mengenai dua operasi pada metode insert di AVL Tree, Terimakasih.

Rangkuman

Pengertian single serta double linked list

            Single linked list merupakan linked list yang memiliki satu tautan saja. Sedangkan 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 single maupun 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. Perbedaan diantara mereka adalah hadirnya fungsi pop mid dan push mid yang mana mewajibkan linked list harus memiliki 2 tautan.

            Fungsi push sendiri berfungsi untuk menambah nilai node (data) dari barisan paling awal, tengah dan akhir. Berikut macam – macam fungsi push pada linked list.

·         Push head

Merupakan fungsi push yang bertujuan menambah data melalui barisan awal.

·         Push Mid(double linked list)

Merupakan fungsi push yang bertujuan menambah data melalui barisan tengah

·         Push tail

Merupakan fungsi push yang bertujuan menambah data dari barisan belakang

Merupakan kebalikan dari fungsi push, fungsi pop sendiri berfungsi untuk menghapus nilai node (data) dari barisan paling awal, tengah dan akhir. Berikut macam – macam fungsi pop pada linked list.

·         Pop head

Merupakan fungsi pop yang bertujuan menghapus data melalui barisan awal.

·         Pop Mid(double linked list)

Merupakan fungsi pop yang bertujuan menghapus data melalui barisan tengah

·         Pop tail

Merupakan fungsi pop yang bertujuan menghapus data dari barisan belakang

Pengertian 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.

Pengertian Binary Search Tree

Lalu, apa itu binary search tree? Binary search tree merupakan sebuah fungsi pada data structure (sama seperti hash table) namun memiliki konsep yang berbeda. Seperti Namanya, binary search 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). 

            Contoh Code :

               while(current->data != data){

                if(current != NULL) {

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

                if(current->data > data){  

                  current = current->leftChild;

                 }

                 else {       

                    current = current->rightChild;

                 }

                 if(current == NULL){

                    return NULL;

                           }

                      }  

                 }

  

               return current;

            

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.

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/