Skip to main content

Posts

Heap dan Tries

Heap and Tries Heap itu pada dasarnya adalah BST (Binary Search Tree) yang memenuhi psayarat dari properti heap. Heap juga dapat dibilang implementasi efisien dari tipe abstrak dengan antrian prioritas. Ada 3 tipe heap, yaitu : Min Heap Dalam min heap, setiap node di atas lebih kecil dari pada childrennya. Contohnya seperti dibawah ini, Untuk insert, urutannya selalu dari kiri baru ke kanan. Sebagai contoh apabila di insert angka 14 maka seperti dibawah ini, Untuk deletion, nilai terakhir dinakkan ke atas dan melakukan heapifi apabila lebih kecil, sebagi contoh apabila root dihapus maka seperti ini, Max Heap Max hepa adalah kebalikan daripada min heap, Jadi node yang diatas lebih besar daripada childrennya, contohnya seperti berikut ini, Untuk insert sama seperti min heap semuanya dimulai dari sebalah kiri, sebagai contoh apabila di insert angka 2 maka jadi seperti, Untuk deletiosn juga sama seperti min heap jadi apabila di ha...

AVL Tree Summary

AVL TREE AVL Tree merupakan Binary Search Tree (BST) yang seimbang sehingga lebih cepat untuk mencarinya dibanding dengan BST. Didalam AVL keseimbangan haruslah sangat diperhatikan tiap node tidak boleh kurang dari -1 dan tidak boleh juga lebih dari 1. Cara menentukan apabila balance atau tidak adalah dengan jumlah bagian terpanjang sebelah kanan - bagian terpanjang sebelah kiri. Berikut adalah Contoh AVL Tree: Diatas adalah contoh AVL Tree yang sempurna karena perbedaan antara yang kanan dengan yang sebelah kiri adalah 0. Di AVL Tree setiap setelah melakukan Insertion atau deletion harus di cek kembali keseimbangan di dalam AVL Tree-nya, Apabila AVL Tree belum seimbang maka ada dua kemungkinan cara untuk menyeimbangkan Tree tersebut. Yang pertama adalah dengan menggunakan Single Rotation Dibawah ini adalah contoh AVL Tree yang tidak seimbang: Karena yang bagian sebelah kiri – bagian sebelah kanan adalah 2 maka AVL Tree di...

SUMMARY

LINKED LIST 1. Circular single Linked list Single linked list adalah satu variabel pointer untuk menyimpan data dengan metode linked list. Data disimpan ke dalam node, setiap node memiliki pointer untuk menunjuk ke node berikutnya. Nah, kalau Circular single linked list itu sama seperti single linked list tetapi setiap node awalnya menyambung dengan node akhir seperti lingkaran, selalu menyambung. Ini adalah ilustrasi perbedaan single linked list (atas) dan circular single linked list(bawah) 2. Doubly linked list Adalah Linked list yang mempunya dua pointer yaitu pointer prev dan next. Pointer prev digunakan untuk menunjukkan ke data sebelumnya dan sebaliknya kalau pointer next menunjukkan ke data selanjutnya Contoh code untuk double linked list : Insert pertama (Dari Depan) Insert dari depan itu adalah penyisipan yang ada di awal, dan pointer head akan pindah ke elemen / data baru, contohnya: Insert Terakhir (Dari Belakang) Insert dar...

Binary Search Tree

Binary Search Tree atau biasanya disingkat menjadi BST itu adalah Struktur data Binary Tree yang mempunyai node dan yang berstruktur yaitu (Subtree kiri dan Subtree kanan harus binary tree): -           Subtree sebelah kiri hanya terdiri dari node yang lebih kecil dari parents dan rootnya -           Subtree sebelah kanan hanya terdiri dari node yang lebih besar dari parents dan rootnya Binary Search Tree juga mempunyai kelebihan yaitu lebih cepat dama mencari, lebih cepat untuk sorting data dan juga lebih cepat dan lebih mudah untuk insert data dan delete data. Berikut adalah contoh dari Binary search tree : Didalam Binary Search Tree kita dapat melakukan Search, Insert dan juga delete: Search: Untuk search dalam Binary Search Tree, pertama-tama harus disamakan dengan root apabila nilainya sama dengan root maka return root-nya. Apabila nilai nya lebih besar dari...

HASHING AND HASH TABLE, TREES AND BINARY TREE

-HASHING AND HASH TABLE, TREES AND BINARY TREE- Hashing adalah sebuah teknik yang dibuat dengan bertujuan untuk membuat nilai kunci unik agar menjadi hasil yang lebih pendek dan kecil. Hashing dibuat menjadi pendek dan kecil agar mudah dicari dan juga dilokasikan. Hash Table adalah Tabel yang dibuat dan diisi oleh kunci hash ( index di hash table) dan juga string aslinya (value di hash table). Hash table memiliki beberapa kelebihan salah satunya adalah agar lebih cepat untuk dicari dan lebih mudah untuk dilokasikan. Hash table juga juga dapat memiliki angka/key hash yang sama tetapi terkadang angka hash yang sama bisa juga menjadi menjadi tubrukan. Biasanya ini diatasi dengan membuat kebijakan untuk hash nya. Contoh: dibawah ini adalah list dari nama mahasiswa yang ada di kelas  Anton, Bella, Deni, Galih, Hasan. dalam hash table yang huruf depannya ‘A’ akan mempunyai index 0, ‘B’  mempunyai index 1, ‘C’ mempunyai index 2, ‘D’ mempunyai index 3 dan seter...