Posts

AVL Tree

Image
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. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Operasi: Insertion Insert suatu node pada AVL sama seperti insert node pada BST, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert. Misal T adalah node yang harus diseimbangkan kembali. Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu : Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left) Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right) Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left) Kasus...
Post a Comment
Read more

SUMMARY

Image
Linked List Linked list adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat atau referensi dari record selanjutnya. Ada beberapa operasi dasar yang terdapat pada linked list: Insert: untuk memasukkan data ke dalam linked list pada posisi yang ditunjuk oleh pointer pertama. Find: untuk mencari suatu data dalam linked list. Remove: untuk menghilangkan sebuah simpul dari linked list. Circular Single Linked List  Circular list adalah bentuk lain dari linked list yang memberikan fleksibilitas dalam elemen. Pada circular list, pointer next dari elemen terakhir menunjuk ke elemen pertama dan bukan menunjuk NULL. Double Linked List Double linked list memiliki pointer penunjuk 2 arah, yaitu node sebelum dan node sesudah. Untuk menunjukkan head dari double linked list, maka pointer prev dari elemen pertama menunjuk NULL. Untuk menunjukkan tail dari double linked list, maka pointer dari elemen ter...
Post a Comment
Read more

Binary Search Tree

Binary Search Tree: sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Aturan Binary Search Tree: Setiap anak node sebelah kiri harus lebih kecil nilainya daripada root nodenya. Setiap anak node sebelah kanan harus lebih besar nilainya daripada root nodenya. 3 jenis cara untuk melakukan penelusuran pada Binary Search Tree: Pre Order: Print data, telusur ke kiri, telusur ke kanan In Order: Telusur ke kiri, print data, telusur ke kanan Post Order: Telusur ke kiri, telusur ke kanan, print data Dalam Binary Search Tree, terdapat 3 operasi dasar, yaitu: Find(x) : mencari value x di dalam Binary Search Tree (Search) Insert(x) : memasukkan value baru x ke Binary Search Tree (Push) Remove(x) : menghapus key x dari Binary Search Tree (Delete) Operasi: Search Karena ada syarat di dalam Binary Search Tree, searching di dalam BST menjadi mudah. Misalkan key yang dicari adalah value X. Memu...
Post a Comment
Read more

Hashing, Hash Tables, Trees & Binary Tree

Hashing & Hash Tables Hashing: transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli. Hash Table: sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Ada beberapa fungsi hash yang digunakan, yaitu: Metode pembagian - sisa: metode yang memperkirakan ukuran jumlah item dalam tabel, lalu menggunakannya sebagai pembagi dalam setiap nilai atau kunci asli untuk mengekstrak hasil bagi dan sisa. Sisa tersebut adalah nilai hash. Metode lipat: membagi nilai asli menjadi beberapa bagian, menambahkan bagian - bagian bersama - sama, dan menggunakan 4 digit terakhir sebagai nilai hash. Metode transformasi radix: Jika kunci digital, basis angka dapat diubah menghasilkan urutan digit yang berbeda. Angka urutan tinggi dapat dibuang agar sesuai dengan nilai hash. Metode penata...
Post a Comment
Read more

Stack and Queue

Stack and Queue 1. Stack Stack adalah suatu kumpulan data yang seolah - olah terlihat seperti ada data yang diletakkan di atas data yang lain. Stack menggunakan konsep LIFO (Last In First Out). Struktur data dari sebuah stack harus memiliki minimal 2 variabel, yaitu top dan max . Top untuk menyimpan alamat elemen paling atas, dan max untuk menyimpan jumlah maksimum elemen yang dapat ditampung stack. Stack biasa digunakan untuk mengubah urutan dari data, mengubah notasi infix menjadi postfix, mengubah notasi postfix menjadi infix, mengubah angka desimal menjadi bilangan binary, dan algoritma backtracking. Terdapat 2 operasi dasar pada stack, yaitu: Push: untuk memasukkan sebuah nilai atau data ke dalam stack dengan cara menaikkan posisi top satu level ke atas. Pop: untuk mengeluarkan atau menghapus nilai terakhir dari stack dengan cara menurunkan nilai  top satu level ke bawah. 2. Queue Queue adalah salah satu implementasi dari linked list. Queue adalah ...
Post a Comment
Read more

LINKED LIST

Image
RANGKUMAN  Linked list adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat atau referensi dari record selanjutnya. Ada beberapa operasi dasar yang terdapat pada linked list: Insert: untuk memasukkan data ke dalam linked list pada posisi yang ditunjuk oleh pointer pertama. Find: untuk mencari suatu data dalam linked list. Remove: untuk menghilangkan sebuah simpu dari linked list. Circular Single Linked List Circular list adalah bentuk lain dari linked list yang memberikan fleksibilitas dalam elemen. Pada circular list, pointer next dari elemen terakhir menunjuk ke elemen pertama dan bukan menunjuk NULL. Double Linked List Double linked list memiliki pointer penunjuk 2 arah, yaitu arah node sebelum dan node sesudah. Untuk menunjukkan head dari double linked list, maka pointer prev dari elemen pertama menunjuk NULL. Untuk menunjukkan tail dari double linked lis...
Post a Comment
Read more