Skip to main content

Posts

AVL Tree Summary

Christophorus Wilson 2301869273 AVL Tree adalah Binary Search Tree yang bentuknya lebih diseimbangkan. Dengan adanya AVL Tree, pencarian suatu data akan membutuhkan waktu yang lebih singkat. Di dalam AVL Tree, terdapat istilah yang disebut balance factor. Balance factor adalah variabel yang berfungsi untuk mengecek apakah suatu bagian di AVL Tree telah seimbang atau belum. Cara mendapatkan balance factor adalah dengan mencari selisih kedalaman antara subtree kiri dan subtree kanan suatu node. Sebuah node dikatakan seimbang apabila balance factornya tidak lebih dari 1. Berikut adalah contoh dari balance factor Insertion Operasi insertion pada AVL Tree dilakukan seperti pada BST biasa, namun akan ditambahkan function untuk menyeimbangkan AVL Tree nya. Dalam menyeimbangkan AVL Tree, terdapat 4 kemungkinan yang dapat terjadi. Misalkan node yang akan diseimbangkan adalah X 1. Node terdalam berada di subtree kiri dari anak kiri node X. 2. Node terdalam berada di subtree k...
Post a Comment
Read more
Recent posts

Summary before Midterm

Christophorus Wilson Sucahyo 2301869273 LINKED LIST Pointer Pointer is used to pass information back and forth between a function and its reference points. Pointer dapat menyimpan alamat memory dan menyimpan sebuah value. Ex. Int *p, a = 10; p = &a; *p=3; Maka di value di variable a akan berubah menjadi 3. Array Kita dapat menginisialisasi elemen untuk disimpan di dalam array, menginput elemen melalui program, atau memasukan elemen. Ex. Inisialisasi elemen Int angka[3] = {3, 2, 1}; Input elemen Int angka[3]; for(int index=0;index<3;index++){ scanf(“%d”, &angka[index]); } Memasukan elemen Int angka1[3] = {3, 2, 1}; Int angka2[3]; for(int i=0;i<3;i++){ angka2[i]=angka1[i]; } Structure Structure adalah tipe data yang dibuat sendiri oleh user yang dapat menyimpan banyak tipe data sekaligus. Ex. Struct mahasiswa{ Int age; Char nama[30]; Char nim[10]; Double gpa; }; mahasiswa y; // artinya sebu...
Post a Comment
Read more

Binary Search Tree

Christophorus Wilson Sucahyo 2301869273 Binary Search Tree (BST) Binary Search Tree adalah struktur data yang memiliki searching dan sorting yang cepat, serta insertion dan deletion yang mudah. Untuk node pada BST, node kiri akan bernilai lebih kecil dari parent nodenya sedangkan node kanan akan bernilai lebih besar dari parent nodenya (dengan asumsi bahwa key nya berbeda)   Pada BST, terdapat 3 basic operations : -           find(x) : mencari key x di dalam BST -           insert(x) : memasukkan key x ke dalam BST -           remove(x) : menghapus key x dari dalam BST Operation : Search ( find(x) ) -           Dimulai dari root -           Jika x lebih kecil dari root, maka cari ...
Post a Comment
Read more

Hashing, Hash Table, and Binary Tree

Christophorus Wilson 2301869273 Hashing Hashing adalah semua method yang digunakan untuk menyimpan dan mengambil key dengan cepat. Di dalam hashing, string diubah menjadi bentuk string yang lebih pendek untuk mewakili string aslinya. Hashing digunakan untuk menjadi index dan mengambil elemen di database karena pencariannya lebih cepat menggunakan hashed key dibandingkan dengan value aslinya. Distribusi hashing ke dalam sebuah array disebut dengan Hash Table dengan menggunakan fungsi yang disebut dengan Hash Function. Hash Table Hash Table adalah array tempat kita menyimpan value asli dari sebuah string. Index dari array tersebut adalah hashed key yang diambil dari value asli string tersebut. Dari gambar diatas dapat dilihat bahwa apple diletakan di index 0 setelah   melewati proses Hash Function. Hash Function Ada beberapa cara untuk mengubah suatu string menjadi sebuah hashed key. à Mid-square à Division (paling sering digunakan) à Folding à Dig...
Post a Comment
Read more

Stack and Queue

Christophorus Wilson 2301869273 Stack vs Queue Keduanya adalah struktur data yang berfungsi untuk menyimpan data secara berurutan. Perbedaannya terdapat pada sifatnya . Sifat dari Stack adalah LIFO (Last In First Out). Analoginya adalah seperti buku yang ditumpuk, buku yang terakhir kali diletakkan (paling atas)   adalah yang pertama kali diambil. Sedangkan sifat dari Queue adalah FIFO (First In First Out). Analoginya seperti mengantri di kasir pada umumnya. Orang yang pertama kali masuk adalah yang pertama kali dilayani. Stack Stack dapat direpresentasikan menggunakan array dan linked list. Pada array, terdapat 2 variabel TOP dan MAX. TOP adalah variabel penanda index paling kanan yang berisi. Jadi apabila variabel TOP = NULL , maka berarti array tersebut kosong. Sedangkan MAX adalah total elemen yang dapat disimpan dalam array tersebut. Sedangkan pada linked list, pointer START digunakan sebagai variabel TOP. Jika TOP = NULL , maka berarti link...
Post a Comment
Read more