Tugas

Heaps and Tries Heap merupakan struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap dapat diimplementasikan dengan menggunakan linked-list, tetapi lebih mudah untuk menggunakan array. Heap dibagi menjadi dua macam yaitu : -Max Heap yang dimana node rootnya memiliki nilai paling besar di antara semua childrennya. contoh max heap : -Min Heap yaitu node rootnya memiliki nilai paling kecil di antara semua childrennya. contoh min heap : insertion and deletion in Heap deletion di heap merupakan penghapusan pada simpul root. Jika itu max heap maka yang dihapus adalah node yang mempunyai nilai paling besar. Sedangkan deletion di min heap adalah penghapusan node yang memiliki nilai paling kecil. untuk insertion dalam heap, yaitu dengan : 1. menambahkan elemen baru di akhir array 2. lalu membandingkan nilai node tersebut dengan nilai parent, jika mereka salah urutan tukar mereka. Tries adalah dtruktur data yang digunakan untuk menyimpan a...

AVL TREE AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Ketinggian subtree kosong adalah 0. Tinggi daun adalah 1. Ketinggian simpul internal adalah ketinggian maksimum anak-anaknya ditambah 1. Faktor keseimbangan semua node di pohon AVL harus paling banyak 1.  Operasi pada AVL : - insertion  insert node baru pada bst, dimana node baru diposisikan sebagai leaf. Setelah itu, dilakukan penyeimbangan pada path dari node yang baru diinsert. - deletion node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Selain itu, terdapat single rotation dan double rotation. Single rotation merupakan rotasi sekali left ke left atau right ke right. Sedangkan double rotation merupakan dua kali rotasi dengan left-right ataupun sebaliknya.

Binary Search Tree Binary Search Tree adalah salah satu struktur data yang membantu pencarian, sorting lebih cepat. Serta penyisipan dan penghapusan yang mudah. Unruk node BST, bagian sub tree kiri  x berisi elemen yang lebih kecil daripada yang disimpan dalam x. Unuk baagian sub tree kanan x berisi elemen yang lebih besar daripada yang disimpan di dalam x. Operasi-operasi yang dapat digunakan di dalam BST - Create : Membentuk binary tree - Clear : Mengosongkan binary tree - Insert : Memasukkan sebuah node ke dalam tree - Find : Mencari suatu node - Update : Memperbarui isi dari node Insert BST  = Penyisipan sebuah node baru, didahului dengan operasi pencarian posisi yang sesuai. Dalam hal ini, node baru tersebut akan menjadi leaf. Delete BST = Operasi delete memiliki 3 kemungkinan : -   Delete terhadap node tanpa anak/child (leaf/daun) : node dapat langsung dihapus -       Delete terhadap node dengan satu anak/child : m...

Hashing and Hash Tables, Trees & Binary Tree   Hashing and Hash Table Tabel hash adalah tabel tempat kita menyimpan string asli. Indeks tabel adalah kunci hash, sementara nilainya adalah string asli. Ukuran tabel hash biasanya beberapa kali lipat lebih rendah dari jumlah total string yang mungkin Jadi, beberapa string mungkin memiliki kunci yang sama. Contoh : kita mempunyai 3 string dengan isi "nama","jurusan",dan "idsiswa" dengan size 20. Maka, fungsi hash yang akan kita gunakan adalah mengubah karakter pertama dari setiap string menjadi angka antara 0..19. h[ ] Value 0 idsiswa 1 2 jurusan 3 4 nama sampai size 19 maka, idsiswa disimpan di h[0] karena i terdapat di index 0. jurusan disimpan di h[2] karena j terdapat di index 2, dan seterusnya. Fungsi Hash yang biasa digunakan :  1. Division Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah j...

Stack dan Queue Stack adalah struktur data penting yang menyimpan elemen-elemennya secara teratur. Data disimpan di Last In First Out(LIFO). Stack bisa diimplementasikan dengan menggunakan array atau linked list. Operasi-operasi pada stack dengan Single Linked List : Push = yaitu memasukkan elemen baru ke dalam stack         Contoh penggunaan operasi Push :  void pushHead(char name[]){ current = (struct book *)malloc(sizeof book); strcpy(current->studentname, name); current->next = current->prev = NULL; if(head==NULL){ head=tail=current; }else{ head->prev=current; current->next=head; head=current; } Pop  =  yaitu menghapus elemen teratas dari stack         Contoh penggunaan operasi Pop :  void popHead(){ if(head==NULL){ printf("No Data"); }else if(head==tail){ current=head; head=tail=NULL; free(current); }else{ current=head; head=head->next; head->prev=NULL; fre...