Month: May 2016

Pada pertemuan kali ini Kami belajar tentang Heap, Tries, Dan Hash Table

HEAP

Heap memiliki 3 Jenis:

-Min Heap : Heap yang rootnya memiliki anak terkecil dan jika anaknya ada yang lebih besar akan ditukar dengan root

-Max Heap : Heap yang rootnya memiliki anak terbesar dan jika ada anak yang lebih besar akan ditukar dengan root

-Min-Max Heap : Heap yang rootnya selang seling antara Max heap dan Min heap

TRIES

Tries adalah prefix tree

aplikasi trie:

-auto complete text pada pencarian

-spell checker pada digital dictionary

Contoh TRIES yang mengantung huruf:

1. ALGO
2. API
3. BOM
4. BOS
5. BOSAN
6. BOR

HASHING

Hash Table adalah 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.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Hash Table

Hash yang menggunakan Tabel/Array

Linear Probing

String yang dimasukkan ke array selanjutnya

RED BLACK TREE

Red Black Tree adalah Balanced tree seperti AVL tetapi berbeda terdapat nodes yang berwarna berbeda.

• Semua node mimiliki 2 warna, hitam atau merah
• Semua External node selalu berwarna hitam
• Semua new node berwarna merah
• Root pasti hitam
• Tidak boleh ada node Merah memiliki Anak atau parent Merah

2-3 TREE

dalam bidang computer science, 2-3 Tree adalah salah satu tipe struktur data, dimana setiap node dengan anaknya, memiliki 2 children dan 1 elemen data (2 node) atau 3 children dan 2 elemen data (3 node). perlu diketahui, bahwa 2-3 Tree bukan Binary Tree.

Pada pertemuan kali ini kami membahas Balanced Binary Tree dan kami juga didatangi oleh Dosen Tamu bernama Selvakumar Manickam, Senior Lecture of University Science of Malaysia . Balanced Binari Tree memiliki 2 macam antara lain AVL dan Red-Black Tree, namun pada pertemuan kali ini kami hanya membahas soal AVL.