REVIEW

PENGERTIAN SINGLE & DOUBLE LINKED LIST
Push depan adalah menambahkan data baru ke depan data lama, sedangkan push belakang adalah menambahkan data baru ke belakang data lama. Pop depan adalah menghapus data mulai dari depan/kiri, pop belakang adalah menghapus data mulai dari belakang/kanan.

Single linked list memiliki satu tangan yang pada umumnya hanya bergerak ke kanan, sedangkan double linked list dapat bergerak ke kiri dan kanan.

HASHING

Teknik menyimpan dan mengambil kunci dengan cepat. Stringnya dibuat menjadi lebih pendek. Digunakan untuk mengindeks dan mengambil item dalam database, karena hash lebih pendek dan cepat. Tabel hash adalah pendistribusian kunci dalam array, tempat penyimpanan string asli. Fungsinya/function disebut hash function.

Metode hash string menjadi key:

- mid-square

- division (paling umum digunakan)

- folding

- digit extraction

- rotating hash

//MID - SQUARE

Nilai awal diambil kemudian dikuadratkan, lalu beberapa digit dari tengah diekstrak yang menjadi nilai baru, menghasilkan kunci dengan kecocokan tinggi bila nilai awal besar.

Contoh 3121 - kuadratnya=9740641 - tengahnya=406. Dengan binary 1001010-0101000010-1100001

//DIVISION

Memakai modulus. Nilai asli dibagi dengan jumlah lokasi/tabel yang tersedia.

Contoh nilai asli 12 dan 21, ukuran tabel=11

(12 mod 11)+1 = 1+1 = 2; simpan 12 di lokasi 2. Angka 2 menjadi nilai key.

(21 mod 11)+1 = 10+1 = 11; simpan 21 di lokasi 11.

//FOLDING

Nilai key dibagi menjadi beberapa bagian, tiap bagian punya jumlah digit yang sama dengan alamat relatif, kemudian dilipat (seperti kertas) lalu dijumlah.

Contoh nilai asli 123456, 234561, 321654.

123+654 = 777; simpan 123456 di 777.

234+153 = 387; simpan 234351 di 387.

321+456 = 777; simpan 321456 di 777. Terjadi kolisi dengan 123456.

//DIGIT EXTRACTION

Beberapa digit sebelumnya diekstrak.

Contoh 14568. Ambil digit ke 1 yaitu 1, 3 yaitu 5, dan 5 yaitu 8. Jadi disimpan di 158.

//ROTATING

Nilai asli dibalik lalu menjadi hash code.

Contoh 20021. Hash codenya adalah 12002.

COLLISION merupakan suatu peristiwa dimana 2 atau lebih nilai asli memiliki hash code yang sama. Penyelesainnya adalah dengan cara linear probing dan chaining.

PREFIX, INFIX, POSTFIX
Cara untuk menampilkan tree.

Prefix

1. Cetak isi yang dikunjungi

2. Kunjungi cabang kiri.

3. Kunjungi cabang kanan.

Infix

1. Kunjungi cabang kiri

2. Cetak isi yang dikunjungi

3. Kunjungi cabang kanan

Postfix

1. Kunjungi cabang kiri

2. Kunjungi cabang kanan

3. Cetak isi yang dikunjungi

BINARY SEARCH TREE (BST)
Binary Search Tree (BST) sama seperti binary tree, yaitu masing - masing node maksimal memiliki 2 anak. Yang membedakannya ialah nilai node di kiri harus lebih kecil daripada di kanan.

Kelebihan BST:
1. Lebih mudah dalam melakukan pencarian data. 
2. Proses melihat data lebih mudah.
3. Mudah dalam penyimpanan dalam data bentuk hirarki.

INSERT SINGLE LINKED LIST
void push(struct *tree node, int a){
    if(root==NULL){ //belum pernah terbentuk
        root = newNode(a); //pesan memori malloc
    }
   
    else if(a < node->a && node->left==NULL){ //kalau yang mau diinput lebih kecil daripada sekarang, dan sebelah kirinya kosong
        node->left = newNode(a); //pesen malloc
        node->left->parent = node; //parent di node sekarang
    }
   
    else if(a > node->a && node->right==NULL){ //kalau yang diinput lebih besar daripada sekarang, dan sebelah kanannya kosong
        node->right = newNode(a); //pesen malloc
        node->right->parent = node; //parent di node sekarang yg kanan
    }
   
    else if(a < node->a){ //yang diinput lebih kecil daripada sekarang, tapi kiri kanan tidak kosong
        push(node->left, a); //akan ditaruh di kiri
    }
   
    else{ //yang diinput lebih besar daripada sekarang, kiri kanan tidak kosong
        push(node->right, a); //akan ditaruh di kanan
    }
}

DELETE
//untuk node yang belum memiliki anak, atau node terbawah
 

//node yang mau dihapus hanya memiliki anak kiri, tidak punya anak kanan
 

//node yang mau dihapus hanya memiliki anak kanan
 
//punya anak kanan dan kiri, digantikan oleh anak kiri yang paling besar nilainya. kemudian yg menggantikan dihapus lagi (recursive)



 

SEARCHING

 while(current->data != data){
      if(current != NULL) {
         printf("%d ",current->data); 
         if(current->data > data){  //ke kiri tree
            current = current->leftChild;
         } 
         else {        //ke kanan tree       
            current = current->rightChild;
         }
         if(current == NULL){ //tidak ditemukan
            return NULL;
         }
      }   
   }
   
   return current;