Min Heap, Max Heap, Min Max Heap, Tries,Hashing, Collision

Dalam pertemuan kali ini, kami membahas mengenai Max Heap, Min Heap, Min-Max Heap, Tries dan Hashing . Pertama kita akan membahas Heap Concept , Heap Concept merupakan complete binary tree yang disusun dengan Heap Property . Heap Property terbagi menjadi 2, yaitu Min Heap dan Max Heap. Konsep Min Heap , dimana parent node lebih kecil dari child nodenya, sebaliknya dalam konsep Max Heap parent nodenya lebih besar dari child nodenya.
Min Heap
Di dalam konsep Min Heap, node yang berada dibawahnya atau parent nilainya akan lebih kecil dibandingkan dengan node anaknya. Maka dapat disimpulkan node root merupakan node dengan nilai paling kecil , dan salah satu node dari leaf node merupakan node yang nilainya paling besar .
Contoh:

Insertion dalam Min Heap:
Jika kita akan menginsert sebuah angka, maka kita harus meletakkan node tersebut di tempat setelah terakhir. Lalu, kita cek kondisi dengan parent nya, jika node tersebut lebih besar dari parent nya maka di swap, lakukan cara tersebut sampai root
Contoh:

Deletion dalam Max Heap:
Jika kita akan menghapus suatu node, maka node yang akan menggantikan adalah node yang paling terakhir. Setelah itu cek kondisi dengan child nya, jika node tersebut lebih besar dari child nya maka di swap, lakukan cara tersebut sampai leaf
Contoh:

Max Heap
Konsep Max Heap hanya berbeda sedikit , perbedaannya hanya ada di node paling atas akan memiliki node dengan nilai terbesar dan salah satu node dari leaf node akan memiliki nilai yang terkecil

Min Max Heap
Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya.
Contoh:

Insertion dan Deletion sama seperti Min Heap atau Max Heap namun, pengecekan kondisi hanya dapat dilakukan di level sesama min atau max
Tries Concept
Berasal dari kata reTRIEval yang berarti untuk menyimpan asosiatif array dan jika dalam aplikasinya trie concept ini seperti auto-complete.
Contoh:

Hashing
Menntransformasikan string ke kata yang lebih pendek/key yang merepresentasikan original string-nya. Dengan tujuan untuk mempermudah pencarian.
Contoh:
Nama Key
Kura-kura K
Pecel Goreng P
Nasi Uduk NU
Nasi Putih NP

Hash Table
h[] Value
0 atan
1
2 char
3 define
4 exp
5 float
.
.
25

 Hash Function
⦁ Mid Square , mengambil tengahnya
⦁ Division, jumlah yang dimodulus lalu diambil indexnya
⦁ Folding, dibagi lalu digabung lagi

Collision
Kondisi dimana terdapat 2 value dengan awalan yang sama, maka ada  cara menangani collision ini:

1. Linear Probling, mencari yang setelahnya kosong
h[] value Step
a 0 Anggur 1
b 1 Apel 2
c 2 Carrot 1
d 3 Durian 1
e 4 Belimbing 4
f 5 Fuji 1
g 7 Grape 1

2.Chaining, sesuai abjad(Linked List)
h[] value
0 anggur->apel
1 belimbing
2 carrot
3 durian
4
5 fuji
6 grape

Red Black Tree dan 2-3 Tree

Pada pertemuan Collaborative Class kali ini, kami membahas mengenai Red Black Tree dan juga 2-3 Tree . Pertama kami membahas mengenai Red Black Tree .  Red Black Tree merupakan salah satu dari Binary Search Tree (BST) karena masih menggunakan konsep yang sama dengan BST yaitu sebelah kanan dari node merupakan nilai node yang lebih besar dan sebaliknya . Dinamakan Red Black Tree karena node yang ada dalam Tree ini hanya berwarna merah dan hitam.  Ada beberapa syarat atau ketentuan dari Red Black Tree ini :
⦁ Root harus berwarna hitam
⦁ Node yang baru dimasukkan akan berwarna merah
⦁ Jika node merah bertemu dengan node merah maka harus diubah , dengan cara :
1. Jika uncle dari node tersebut berwarna merah , maka parent dan uncle harus di recolor menjadi warna hitam
2. Jika uncle dari node tersebut berwarna hitam, maka node tersebut harus di rotate dengan sistem Single atau Double rotation, jika diperlukan maka akan di recolor
⦁ Tree dihitung berdasarkan node hitamnya saja, dan merah diabaikan dalam penghitungan
⦁ Tree dikatakan seimbang, jika setiap node dihitung akan menghasilkan angka yang sama
Contoh:

Insertion dalam Red Black Tree:
⦁ Node yang NULL atau tidak ada dianggap BLACK

Deletion dalam Red Black Tree:
⦁ Jika node tersebut merupakan leaf, maka dapat langsung dihapus
⦁ Jika node tersebut memiliki 1 anak , maka anaknya akan menggantikan node yang akan dihapus
⦁ Jika node tersebut memiliki 2 anak, maka anak kiri yang paling kanan akan menggantikan node yang akan dihapus
Jika terlah melakukan 1 dari ketiga kondisi diatas, maka kita harus mengecek lagi jika ada ketidak seimbangan di tree tersebut. Di dalam deletion pada red black tree memungkinan terjadi violation berkali kali, tetapi jika di insertion, jika ada violation hanya akan ada 1 kali saja.
Contoh:

Setelah kita membahas Red Black Tree, selanjutnya kita akan membahas 2-3 Tree. 2-3 Tree bukan merupakan Binary Tree melainkan jenis dari B-Tree karena 2-3 Tree dapat memiliki 3 anak .
⦁ Jika 1 node memiliki 1 value maka node tersebut HARUS memiliki 2 anak
⦁ Jika 1 node memiliki 2 value maka node tersebut HARUS memiliki 3 anak
Berbeda dengan tree kemarin, 2-3 Tree bertumbuh ke atas bukan kebawah, jadi leaf yang sudah ada tidak akan memiliki child lagi .
Contoh :

Insertion pada 2-3 Tree:
Insertion dapat ditambahkan pad node mulai dari leaf, jika leaf penuh maka value yang berada pada value tengah akan dilempar keatas.
Contoh:

Deletion pada 2-3 Tree

Data Structure - AVL Tree

Data Structure

Pada pertemuan ini, kami membahas Balanced Binary Search Tree. Balanced Binary Search Tree adalah sebuah BST yang diminimalisasi height atau levelnya , untuk memudahkan pencarian dan menghemat waktu saat mencari node yang dicari . Balanced Binary Search Tree terdapat 2 macam (dalam matkul ini), yaitu AVL dan Red Black Tree . Pada pertemuan ini, kami hanya membahas AVL dan kami kedatangan Guest Lecture, Selvakumar Manickam, Senior Lecture of University Science of Malaysia .

AVL

AVL merupakan Balanced Binary Search Tree pertama yang ada . AVL merupakan sebuah singkatan dari penemu Balanced Binary Search Tree ini .

Contoh:

Note:

·         h-n merupakan height dari tree tersebut ke n

·         b-n merupakan balanced tree tersebut , dimana kita dapat menghitung dengan cara :

Height anak kiri – Height anak kanan

Hasilnya hanya ada 3 kemungkinan , yaitu -1, 0, 1

Jika hasilnya:

-1: Maka tree tersebut lebih berat ke kiri, tetapi masih balanced

 0: Maka tree tersebut balanced

 1: Maka tree tersebut lebih berat ke kanan, tetapi masih balanced

Dalam AVL tree terdapat 2 jenis , yaitu :

1.       Single Rotation

Contoh :

Right-Right

Left-Left

2.       Double Rotation

Contoh:

Operation dalam AVL ada 3 , yaitu Insertion,Deletion, dan Searching . tetapi searching sudah termasuk dalam 2 operation lainnya . Sekarang kita akan membahas mengenai Insertion.

Insertion dalam AVL tree sama seperti BST, namun setiap stepnya kita harus mengecek dan menghitung kembali height dan balanced factornya . Jika balanced factornya tidak memenuhi persyaratan maka disebut violation. Setiap ada violation maka kita harus membuat tree tersebut itu blanced kembali .

Contoh:

Deletion

Dalam sesi Guest Lecture, kami membahas materi yang saya pernah tulis di blog ini, silahkan cek ya. Sesi 1 Sesi 4 Sesi 5 .