Rangkuman Sebelum UAS - David 2301868491
Linked List
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.
Macam - Macam Linked List :
- Circular Single Linked List :Circular atau siklus memiliki arti yaitu tidak berujung. Sehingga dapat kita ketahui bahwa Circular Single Linked List adalah Single Linked List yang dimana Tail (Node Terakhir) dari Linked List tersebut menunjuk(menyimpan alamat) pada Head (Node Pertama) dari Linked Linked List tersebut.
- Double Linked List: Jika kita ketahui Single Linked List adalah Linked List dimana node-nodenya hanya menunjuk(menyimpan alamat) ke 1 arah (ke depan atau belakang) maka di Double Linked List ini node-node yang terdapat di linked list ini menunjuk(menyimpan alamat) pada 2 arah yaitu ke node yang berada di depan dan belakang node tersebut.
Contoh Coding dari Double Linked List :
General :
struct List{
int number;
struct List *Next;
struct List *Prev;
};
- Circular Double Linked List: Circular Double Linked List hampir sama dengan Circular Single Linked List, perbedaannya adalah pada Circular Double Linked List Head (Node Pertama) menunjuk(menyimpan alamat) pada Tail(Node Terakhir) begitu juga Tail, Tail menunjuk pada Head dalam Linked List tersebut sehingga adanya 2 pointer dan Linked List tersebut tidak memiliki ujung.
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.
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.
AVL TREE
AVL Tree adalah self-balancing tree dari BST(Binary Search Tree) dimana kedalaman dari sisi kiri dan sisi kanan harus sama dan maksimal beda 1. Mengapa menggunakan AVL Tree? Karena AVL mempertahankan kecepatan operasinya hampir O(log n) sehingga kecepatannya lebih cepat dibanding dengan BST biasa.
Agar sistem dari AVL tidak merusak BST, maka proses insertion dari AVL akan sama dengan BST namun dalam tiap prosesnya akan terjadi re-balancing jika tree yang ada tidak seimbang.
Proses Insertion :
- Masukkan angka sama seperti insertion di BST
- Cek apakah tree tersebut seimbang
- JIka seimbang(maksimal beda 1 kedalaman) maka proses insertion dilanjutkan, jika tidak maka akan dilakukan rotasi agar tree tersebut seimbang.
Proses Deletion :
- Delete angka sama seperti Deletion di BST
- Cek apakah tree tersebut seimbang
- JIka seimbang(maksimal beda 1 kedalaman) maka proses deletion dilanjutkan, jika tidak maka akan dilakukan rotasi agar tree tersebut seimbang.
- Proses re-balance akan tetap berlanjut sampai semua tree seimbang(re-balance sampai ke root)
Ada 2 jenis rotasi yaitu Single Rotation dan Double Rotation:
- Single Rotation : Single Rotation digunakan saat jika node yang menyebabkan tree tidak seimbang berada pada posisi left-left atau right-right pada subtree(lurus)
- Double Rotation : Double Rotation digunakan saat jika node yang menyebabkan tree tidak seimbang berada pada posisi left-right atau right-left pada subtree(bengkok)
Heap
Heap adalah bagian dari balanced binary tree yang dalam pembuatannya root dari suatu node akan dibandingkan dengan children dari root tersebut lalu diatur sedemikian rupa(diurutkan)
ada 2 macam Heap :
- Min Heap : heap dimana root memiliki nilai lebih kecil atau sama dengan children
 |
| Min Heap |
- Max Heap : heap dimana root memiliki nilai lebih besar atau sama dengan children
 |
| Max Heap |
Insertion :
- Buat Node baru lalu taruh di Heap terakhir
- Bandingkan Node tersebut dengan parent-nya
- Jika Parent lebih besar(Max Heap) atau lebih kecil(Min Heap) maka lakukan swap
- Ulangi langkah 2 dan 3 sampai Heap semua Node terurut
Deletion:
- Hilangkan Node yang di root(selalu di root)
- Taruh Node terakhir dari level terakhir di root
- Bandingkan Node tersebut dengan children-nya
- Jika child lebih besar(Max Heap) atau lebih kecil(Min Heap) maka lakukan swap
- Ulangi langkah 2 dan 3 sampai Heap semua Node terurut
Trie
Trie adalah sebuah search tree yang sangat efisien, data struktur yang terurut yang digunakan untuk menyimpan dynamic set yang biasanya adalah string. Tiap Node di Trie dapat memiliki cabang yang banyak, jika di string maka di setiap Node akan terisi dengan 1 karakter huruf, kita harus menandai Node terakhir sebagai EndWord sehingga program dapat berhenti. Trie ini seringkali kita temukan autofill(search engine).
