Binary Search Tree

               Binary Search Tree (BST) adalah sebuah struktur data yang dibuat agar pencarian(searching), pengurutan(sorting), pemasukkan(insertion) dan penghapusan(deleteion) dapat dilakukan lebih cepat dan juga lebih mudah. Binary Search Tree juga seringkali disebut sorted version of Binary Tree atau dapat kita artikan sebagai Binary Tree yang diurutkan. Binary Search Tree biasanya dibuat dengan skema sebagai berikut :  

• subtree atau bagian dari tree atau anak node yang memiliki nilai lebih kecil dibanding nilai yang ada di node atasnya diletakkan di node sebelah kiri
• subtree atau bagian dari tree atau anak node yang memiliki nilai lebih besar dibanding nilai yang ada di node atasnya diletakkan di node sebelah kanan
• *diasumsikan nilai dari node-node berbeda-beda

Operasi-operasi pada Binary Search Tree 

• Searching: Pencarian suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                          berikut:    1. Mulai dari node teratas atau root  

                                             2. Cek apakah node teratas atau root adalah nilai yang dicari(jika iya,                                                         maka program telah selesai, jika tidak lanjutkan ke langkah 3)

                                             3. JIka nilai yang dicari lebih kecil dibanding node atasnya atau root

                                                 maka lakukan pencarian secara recursive ke kiri dan sebaliknya jika

                                                 jIka nilai yang dicari lebih besar dibanding node atasnya atau root 

                                                 maka lakukan pencarian ke kanan secara recursive

• Insertion: Memasukkan suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                     berikut:       1. Mulai dari node teratas atau root  

                                              2. Jika nilai yang ingin dimasukkan lebih kecil dibanding node atasnya                                                      atau root masukkan angka ke subtree sebelah kiri dari root dan

                                                  sebaliknya jika nilai yang ingin dimasukkan lebih besar dibanding

                                                  node atasnya atau root  masukkan angka ke subtree sebelah kanan dari

                                                  root

                                               3. Ulangi sampai nilai yang ingin dimasukkan menemukan tempat

                                                   kosong untuk dapat nilai tersebut tempati

• Deletion: Menghapus suatu nilai pada Binary Search Tree dengan langkah-langkah sebagai                         berikut:        1. Cek node-node yang ada, jika node yang ingin dihapus idak                                                         memiliki subtree atau anak, hapus langsung node tersebut.
                                       2. Jika node yang ingin dihapus memiliki 1 subtree atau anak, hapus                                                langsung node tersebut, lalu sambungkan subtree atau anak node                                                   tersebut dengan node di atasnya atau parent. 

                                                3. Jika node yang ingin dihapus memiliki 2 subtree atau anak, cari anak

                                                    dari node tersebut yang menempati posisi di paling kanan subtree

                                                    bagian kiri lalu tempatkan anak tersebut di node yang ingin dihapus,

                                                    lalu hapus posisi anak tersebut secara recursive.

Hashing Table & Binary Tree

      Hashing adalah proses pengeluaran Output Data dari Input Data yang memiliki panjang berbeda-beda menjadi memiliki panjang yang tetap dan sama. Teknik Hashing ini sangat tidak asing di bidang Blockchain dimana kegunaan dari Hashing ini adalah seperti meengenkripsi suata data yang kita kirim, bedanya dengan enkripsi biasa adalah Hashing tidak dapat menghasilkan suatu dokumen, karena memang Hashing diciptakan untuk melihat integritas dari suatu data. Contoh yang dapat kita lihat adalah NSA(National Security Agency) milik Amerika Serikat yang mematenkan Secure Hash Algorithm yang sampai sekarang masih digunakan di Bitcoin dan lain sebagainya.

             Hashing Table adalah sebuah struktur data yang menyimpan data-data yang ada secara unik, yaitu memberi nilai-nilai index yang berbeda-beda antara 1 data dengan data lainnya. Akses menuju suatu data akan menjadi sangat cepat ketika kita mengetahui nilai index data tersebut. Hashing Table sangatlah cepat tidak peduli seberapa besar data yang ada karena Hashing Table menggunakan teknik Hashing sehingga panjang dari Input maupun Output Data akan selalu sama.

Contoh :

Penyimpanan data:

struct DataItem {
   int data;
   int key;
};

Deklarasi Fungsi Hash:

int hashCode(int key){
   return key % SIZE;
}

Fungsi Searching:

struct DataItem *search(int key) {
     int hashIndex = hashCode(key);
 
      while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
   
       ++hashIndex;
  
      hashIndex %= SIZE;
   }

   return NULL;        
}

Fungsi Insert:

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;        
}

Fungsi Delete :

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;        
}

 

             Binary Tree (Pohon Biner) adalah sebuah pohon di struktur data yang bersifat hirarkis(one to many). Binary Tree dapat juga disebut kumpulan simpul yang memiliki maksimal 2 anak simpul di tiap simpulnya. 

Pertemuan 3 Maret 2020

Linked List:

Seperti yang sudah saya tulis di blog saya sebelumnya Linked List adalah struktur data yang tersusun oleh record-record data yang berurutan maupun tidak berurutan dan tiap-tiap record data tersebut memiliki field yang menyimpan alamat dari record selanjutnya atau sebelumnya. record-record data yang dihubungkan dengan link disebut juga Node. Dalam suatu Linked List memiliki 2 jenis istilah yang penting yaitu Head dan Tail. Head adalah Node pertama dalam suatu Linked List dan Tail adalah Node terakhir dalam suatu Linked List.

Single Linked List :

Single Linked List adalah Linked List yang hanya menunjuk address dari node di depannya atau di belakangnya.

Double Linked List:

Double Linked List adalah Linked List yang menunjuk address dari node di depan dan di belakangnya dan node di depan dan belakangnya juga menyimpan address dari node tersebut.

Perbedaan :
Perbedaan dari Single Linked List dan Double Linked List adalah Double Linked List dapat mengakses data yang tersimpan di node depan dan belakangnya(yang terhubung) sedangkan Single Linked List hanya dapat mengakses node di depan atau di belakangnya(hanya yang ditunjuknya)