Graph

Pada sesi kemarin, kami membahas mengenai Graph. Graph yang ada di mata kuliah ini sama seperti matematika diskrit yang ada di semester 1.

Graph terdiri dari vertex dan edges. Vertex digambarkan seperti node atau lingkaran, sedangkan edges digambarkan seperti garis penghubung antara vertex yang satu dengan yang lain.

Minimum Spanning Tree

MST ini bertujuan mencari cost termurah/jarak terpendek. Ada 2 cara ,yaitu Prim dan Kruskal. Prim pada dasarnya memilih 1 titik start lalu mencari titik selanjutnya dengan jarak terpendek. Sedangkan kruskal memilih seluruh jarak terpendek tetapi menghindari adanya looping.

MST ini mudah jika kita menggunakan notepad atau semacamnya.

PRIM:

AB 2

AC 1

AF 4

=> AC 1

----------------

AB 2

AF 4

CB 5

CD 1

CE 2

CF 3

=> CD 1

----------------

AB 2

AF 4

CB 5

CE 2

CF 3

DB 3

DE 2

=> AB 2

----------------

AF 4

CB 5

CE 2

CF 3

DB 3

DE 2

BE 4

=> CE 2

----------------

AF 4

CB 5

CF 3

DB 3

DE 2

BE 4

EF 1

=> EF 1

----------------

AF 4

CB 5

CF 3

DB 3

DE 2

BE 4

=> DE 2 (X)

----------------

AF 4

CB 5

CF 3

DB 3

BE 4

=> CF 3 (X)

----------------

AF 4

CB 5

DB 3

BE 4

=> DB 3 (X)

----------------

AF 4

CB 5

BE 4

.... DST

 

VISITED : A C D B E F

EDGE     : AC CD AB CE EF

 

KRUSKAL:

AC 1

CD 1

EF 1

AB 2

CE 2

DE 2

BD 3

CF 3

AF 4

BE 4

BC 5

 

EDGE     : AC CD EF AB CE

VISITED : A C D F B E

Kurang lebih contoh prim dan kruskal seperti itu. Jika ada pertanyaan bias ditanyakan ya J . Terima kasih

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 .

Data Structure Pertemuan 05

Binary Search Tree

Keuntungan Binary Search Tree dari Binary Tree adalah lebih mudah dicari karena telah diletakkan lebih urut . Dan tujuannya untuk mempercepat pencaarian value dari BST tersebut.

Contoh :

   5
  / \
 3   7
/      \
1   -

Note:
Sisi kanan merupakan nilai lebih besar dari parent nya,
sedangkan Sisi kiri merupakan nilai lebih kecil dari parent nya

Operasi pasa Binary Tree ada 3,yaitu:
1.Search / Find
2.Insert / Push
3.Delete / Remove / Pop

case :           21
  /\
 7  99
/\
3  9
   \
    10


1.Search / Find

Misalkan kita ingin mencari angka 9 . Maka proses dari search(9) adalah :
Pertama kita cek dari rootnya (21) , apakah 9 lebih besar dari 21 atau tidak ? Karena 9 lebih kecil maka kita mengarah ke arah kiri
Lalu, di node kedua(7), kita cek kembali apakah 9 lebih besar dari 7 apa tidak? karena 9 lebih besar, maka kita mengarah ke kanan
Lalu, d node ketiga(9), Kita menemukan angka 9 .

2.Insertion / Push
Tahap insertion sama seperti search , tapi yang berbeda hanyalah pada saat kapan kita akan insert .
Konsep di Insertion ini adalah :
Apakah node itu kosong atau tidak? Kalo kosong kita harus membuat node, kalo tidak kita harus cek dahulu node sebelum dan sesudahnya.

3.Remove / Pop
Tahap remove tetap sama seperti insertion, kita harus search data yang akan di remove.
Konsep di Remove ini adalah:
Kita harus mencari data dengan search, kemudian jika ketemu kita menggunakan syntax pop, lalu setelah kita me-pop node,kita harus mengganti node tersebut dengan node yang memungkinkan.

Data Structure 04

Data Stucture pertemuan 04

Pada pertemuan 4 ini, kami membahas mengenai TREE CONCEPT . Tree Concept ini digunakan pada saat kami mempelajari Data Base nanti, dan contohnya seperti penggunaan Directory .Sesuai namanya Tree berarti Pohon . Maka Tree Concept ini digambarkan seperti membuat pohon :

 

Dalam Tree terdapat istilah-istilah yang perlu diketahui:
1.       Parent

Pada Tree diatas:

-Parent of E : B

-Parent of C : A

2.       Root

Root merupakan akar dari segala node yang ada, dan terdapat di level teratas .

Pada Tree diatas:

Root : A

3.       Edge

Edge merupakan garis yang menghubungkan parent ke child nya

4.       Leaf

Leaf merupakan node yang terbawah , atau bias dibilang node yang tidak mempunyai child lagi

Leaf : K , L , M

5.       Siblings

Siblings merupakan node yang mempunyai parent yang sama

Siblings of F : G , H

Siblings of B : C , D

6.       Degree

Degree merupakan node pada total sub tree

Degree of tree : 4

Degree of C : 3

7.       Height/Depth

Height merupakan maximum degree pada tree tersebut

Height of Tree : 4

8.       Ancestor

Ancestor merupakan nenek moyang dari nodes .

Ancestor of G : C , A

9.       Descendant

Descendant merupakan keturunan dari nodes

Descendant of C : F , G , H , M

Binary Tree hanya mempunyai 2 anak (Left Child & Right Child).

Type of Binary Tree:
1.       Perfect Binary Tree
2.       Complete Binary Tree
3.       Skewed Binary Tree
4.       Balanced Binary Tree

1.       Perfect Binary Tree

Tree yang masing-masing mempunyai 2 anak, dimana kanan dan kiri seimbang

2.       Complete Binary Tree

Tree yang hampir sempurna atau seperti Perfect Binary Tree yang tidak seimbang



3.       Skewed Binary Tree

Tree yang parent-nya hanya mempunyai 1 anak

4.       Balanced Binary Tree

Tree yang jarak dari root ke leaf sama dengan jarak antara kiri dan kanan

PROPERTY BINARY TREE

Rumus :

1.       Menghitung maximum node per level : 2^k (k = level)

2.       Menghitung maximum node per height : 2^h+1 – 1 (h = level)

3.       Menghitung minimum height : 2 log n (n=node) atau cara mudahnya menggambar tree dimana setiap parent mempunyai 2 anak

4.       Menghitung maximum height : n-1 (n=node) atau cara mudahnya menggambar dengan type skewed

REPRESENTATION OF BINARY TREE WITH ARRAY/LINKED LIST

1.       Array

Rumus :

1.       Index Left Child : 2p+1

2.       Index Right Child : 2p+2

3.       Index Parent : (c-1)/2

2.       Linked List

EXPRESSION TREE CONCEPT

Prefix -> Print Left Right                                                                                       

Postfix ->Left Right Print                                                                                       

Infix -> Left Print Right

                                                                                                                                                                

Data Structure Pertemuan 03

Di dalam Struktur data berhubungan dengan Linked List dan di Linked List tersebut terdapat istilah Stack dan Queue . Materi tersebut sudah saya jelaskan di pertemuan kemarin Pertemuan 1 . Nah, sekarang kita kembali lagi ke Linked List. Di dalam Linked List Presentation terdapat Push , Pop , Top/Peek . Mari kita bahas satu persatu.

Push / Enstack / Enqueue

Push adalah suatu representasi dari Linked List untuk menambah node di awal / di akhir . Biasa ita menyebut Push Head untuk diawal , Push Tail untuk diakhir , dan Push Mid untuk di Tengah , tetapi untuk Push Mid biasa di pakai di Double Linked List , karena jika dipakai di Single Linked List akan lebih rumit .

Pop / Destack / Dequeue

Pop adalah suatu representasi dari Linked List untuk menghapus node di awal / di akhir . Biasa ita menyebut Pop Head untuk diawal , Pop Tail untuk diakhir , dan Pop Mid untuk di Tengah.

Top / Peek

Top adalah suatu representasi dari Linked List yang digunakan untuk menunjukan node yang sedang ditunjuk sekarang .

Array Presentation

Seperti array biasa , dimana tempat dipesan langsung 1 blok dan random

Contoh:

N = 5

Top = -1

Top

-1	0	1	2	3	4

Index

Kita bias memakai rumus :

Top + 1 >= 5

Top akan terus berpindah selama Top >=5

Saat Top = 5 , Top akan berhenti , dan menunjukan jika Array sudah penuh

Karena Array ini merupakan representasi dari stack , ada suatu hal yang membuat tidak selamanya data yang terakhir masuk akan pertama keluar . Jika ada suatu hal yang darurat, ada saatnya jika yang pertama masuk akan pertama keluar . Maka dari itu , ada yang namanya Priority Queue

Dan ada yang namanya Circular Queue, terjadi saat Top sudah mencapai akhir dan bisa kembali ke awal . Rumus yang dipakai adalah (Top + 1 % Max).

Application

Terdapat 3 bentuk :

1.Infix , berbentuk seperti matematika biasa

2.Prefix, berbentuk operation operandLeft OperandRight

3.Postfix  , berbentuk operandLeft OperandRight operation

Contoh :

Infix : 4 + 6 * (5-2)/3

Prefix : +4/*6-523

Postfix : 4652-3*/+