Pertemuan Kesembilan Graph dan Minimum Spanning Tree

Graph

Graph adalah sebuah struktur data yang abstrak dimana didalamnya menggunakan fungsi-fungsi graph matematika. Didalam sebuah graph terdapat node dan edges. Edge adalah "tangan" yang dimilliki oleh suatu node.

Ada dua macam graph, yaitu:

Directed Graph



Undirected Graph



Seperti yang dapat dilihat dua graph diatas, Directed graph memiliki panah di edge(s) nya sedangkan di undirected graph lalu karena terdapat panah maka node yang menunjuk disebut sebagai in-degree dan yang ditunjuk sebgai out-degree. Sedangkan undirected graph memiliki degree yaitu adalah jumlah "tangan" dari sebuah node.

Minimum Spanning Tree (MST)

Minimum Spanning Tree adalah graph dimana tidak ada loop terbentuk didalamnya. Tujuan dari penggunaan MST adalah untuk menentukan cost dari jalan yang paling kecil pada suatu graph.
Minimum Spanning Tree dapat ditentukan melalui tiga cara yaitu Prim's Algorithm, Kruskal's Algorithm, dan Djikstra's Algorithm. Berikut adalah cara-cara menentukan MST:














Djikstra Algorithm

Pertemuan Kedelapan Head dan Tries

Heap

Heap adalah suatu Binary Tree lengkap yang menggunakan persyaratan Heap. Di dalam heap terdapat dua tipe heap yaitu Min Heap dan Max Heap. Min Heap adalah sebuah Binary Tree dimana root dari tree tersebut adalah angka terkecil atau memiliki nilai terkecil dibandingkan seluruh node didalam tree tersebut sedangkan Max Heap adalah sebaliknya yaitu Binary Tree dimana root dari tree tersebut adalah angka terbesar dari tree tersebut.

Berikut adalah contoh dari Min Heap dan Max Heap:

Min Heap

Aturan dalam membuat Min Heap:
1. Value dari suatu parent harus lebih kecil dari value anaknya
2. Root dari tree adalah value terkecil yang ada didalam tree
3. Value terbesar terdapat di salah satu node leaf
 

Max Heap

Aturan dalam membuat Max Heap:
1. Value dari suatu parent harus lebih besar dari value anaknya
2. Root dari tree adalah value terbesar yang ada didalam tree
3. Value terkecil terdapat di salah satu node leaf


Min-Max Heap

Min-Max Heap adalah gabungan dari Min Heap dan Max Heap. Karena Min-Max Heap adalah gabungan dari Min dan Max Heap maka aturan dari kedua heap  tersebut disatukan menjadi seperti berikut:

1. Root menggunakan aturan Min Heap.
2. Setiap node yang memiliki height ganjil mengikuti aturan Min Heap.
3. Setiap node yang memiliki height genap mengkuti atuan Max Heap.





Tries

Tries adalah Binary Tree dimana isi dari tersebut adalah kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).

Pertemuan Ketujuh Red Black Tree dan 2-3 Tree

Red Black Tree

Red Black Tree adalah bentuk kembangan dari Binary Search Tree. Red Black Tree seperti namanya didalam tree terdapat dua macam node yaitu node merah dan node hitam. Didalam Red Black Tree terdapat satu nama baru yaitu Uncle. Uncle ini adalah suatu node yang berdada pada baris yang sama dengan parent dari tree tertentu. Red Black Tree juga memiliki beberapa ciri-ciri yang membedakannya dari AVL Tree, yaitu:

- Root selalu berwarna hitam; misal berubah warna menjadi merah tetap dihitamkan
- Node yang baru dimasukkan harus berwarna merah
- Node merah memiliki dua anak yaitu node berwarna hitam
- Memiliki external node yang berwarna hitam

Didalam Red Black Tree terdapat dua proses yang dapat dilakukan, yaitu:

Insertion

 Cara Insert di Red Black Tree mirip seperti pada Binary Search Tree tetapi ada peraturan baru yaitu, jika Parent berwarna merah, anaknya tidak boleh merah.

Berikut adalah cara menyelesaikan masalah jika 2 node merah bertemu:


Caranya pertama adalah melihat uncle dari node tersebut. Jika uncle dari node tersebut berwarna merah maka hitamkan uncle dan parent dari node tersebut. Sedangkan jika unclenya berwarna hitam maka lakukan proses berikut:






Deletion


Cara deletion pada Red Black Tree juga sama seperti BST tetapi karena ada peraturan khusus dari Red Black Tree maka jika terjadi kesalahan harus diubah. Berikut adalah kemungkinan yang mungkin terjadi saat deletion :

- Node yang di delete berwarna merah dan merupakan node leaf. Maka langsung saja hapus node tersebut

- Terjadi double black dimana sibling dari node tersebut berwarna merah. Maka berikut adalah proses yang dilakukan:



- Terjadi double black dimana sibling berwarna hitam. Maka berikut adalh proses yang dilakukan:



- Terjadi double black dimana sibling hitam dan anak dari node sibling berwarana merah. Maka berikut adalah proses yang dilakukan:



2-3 Tree

2-3 Tree adalh BST yang memiliki node yang berbeda. Berikut adalah contoh dari 2-3 Tree:



Didalam 2-3 Tree terdapat beberapa peraturan yang dapat membentuk 2-3 Tree yaitu:
- Root lepas dari aturan
- Jika parent terdapat n value maka anaknya harus berjumlah n+1
- Didalam deletion jika terbentuk jumlah value pada node yang berjumlah ganjil maka node yang memiliki value ditengah akan dilempar ke atas.
- Dan masih banyak lagi.

PERTEMUAN KEENAM BALANCED BINARY SEARCH TREE (pt.1)

Balanced Binary Search Tree adalah BST yang diperpendek dengan tujuan untuk mempermudah pencarian sebuah node dalam tree. Balanced Binary Search Tree berasal dari dua buah metode yaitu AVL Tree dan Red Black Tree.

AVL Tree


AVL Tree adalah tree yang dibuat oleh G.M. Adelson-Veleski dan E.M. Landis pada tahun 1962. AVL Tree digunakan untuk mempermudah pembuatan balanced Balanced Binary Search Tree. Berikut adalah contoh dari sebuah AVL Tree Concept :



Didalam AVL Tree terdapat tiga proses yang dapat dilakukan, yaitu:

Insertion

Sama pada seperti cara insertion pada Binary Search Tree tetapi bentuk dari tree harus tetap balance. 

Single Rotation & Double Rotation

Single Rotation adalah proses dimana hanya terjadi suatu pertukaran node, biasanya proses ini juga disebut sebagai left left case atau right right case. Sedangkan Double Rotation adalah proses dimana terjadi dua kali pertukaran node, biasanya awal dari proses ini disebut left right case atau right left case.

Yang menentukan proses-proses ini adalah jumlah dari balance factor suatu node. Balance factor suatu node dapat ditentukan dari hasil pengurangan height node anak dari suatu node (Height anak yang nilainya lebih besar - nilainya lebih kecil). Jika hasil tersebut lebih dari 1 maka terjadi sebuah kesalahan dan harus dilakukan single atau double rotation tergantung dari dimana kesalahan tersebut dimulai.

Berikut adalah cara melakukan double rotation dan single rotation pada Balanced Binary Search Tree

PERTEMUAN KELIMA BINARY SEARCH TREE

BINARY SEARCH TREE

Apakah itu Binary Search Tree? Binary Search Tree atau BST adalah Binary Tree dimana Tree tersebut dibuat sedemikian rupa sehingga dapat mempermudah pencarian data yang terdapat dalam sebuah Tree. Sesuai dengan post sebelumnya BST hanya memiliki 2 orang "anak" yang biasa disebut sebagai left dan right sesuai dengan posisi masing-masing.

Didalam Binary Search Tree terdapat 3 fungsi yang berkaitan dengan pencarian yang dapat dilakukan yaitu Find/Search, Insertion, dan Delete. Masing-masing fungsi ini memiliki fungsi sesuai dengan namanya Find untuk mencari, Insertion untuk memasukan data baru kedalam tree, dan Delete untuk menghapus data yang sudah ada didalam sebuah Tree. Fungsi Delete ini biasanya sangat terkait dengan fungsi Find/Search karena didalam pemrograman jika kita ingin menghapus suatu data kita harus meminta user untuk memilih data yang ingin dihapus, tapi bagaimana cara mencari data tersebut dan bagaimana jika data tersebut ternyata tidak ada? Disinilah fungsi Find/Search sangat berpengaruh. Fungsi search akan mencari input dari user dan jika tidak ada yang sesuai maka user akan diberitahu bahwa data tersebut tidak ada dan jika ada data tersebut akan dihapus dari Tree.

Berikut adalah cara kerja atau logika dari 3 fungsi diatas:

1.) Find/Search

1. Data dicari dari atas atau dari Root
2. Jika "parent" adalah data yang dicari maka isi dari "parent" akan di return
3. Jika data yang dimasukan lebih kecil dari Root maka data akan dicari ke "left" dari data diatasnya lalu jika benar maka akan di return
4. Jika data yang dimasukan lebih kecil dari "left maka data akan dicari ke "right" dari data diatasnya lalu jika benar maka akan di return
5. Langkah 2,3, dan 4 akan terus diulangi sampai data yang diinput user ditemukan atau semua data sudah di search

2.) Insertion

1. Cek apakah ada node root. Jika belum ada maka node yang akan di insert menjadi root. Apabila ada, bandingkan data yang akan dimasukkan dengan node tersebut.
2. Jika data yang akan di- insert lebih besar dari node tersebut, pindah ke ‘right’.
3. Jika data yang akan di- insert lebih kecil dari node tersebut, pindah ke ‘left’.
4. Ulangi langkah 3 dan 4 hingga node yang akan dipilih/pindah tidak ada.
5. Cek apakah data yang akan dimasukkan lebih besar / lebih kecil dari node tersebut. Jika lebih besar, maka di insert ke node ‘right’. Sebaliknya, jika lebih kecil maka di-insert ke ‘left’

3.) Delete

1. Data dicari dari atas atau dari Root
2. Jika "parent" adalah data yang dicari maka isi dari "parent" akan di delete
3. Jika data yang dimasukan lebih kecil dari Root maka data akan dicari ke "left" dari data diatasnya lalu jika benar maka akan di delete
4. Jika data yang dimasukan lebih kecil dari "left maka data akan dicari ke "right" dari data diatasnya lalu jika benar maka akan di delete
5. Langkah 2,3, dan 4 akan terus diulangi sampai data yang diinput user ditemukan atau semua data sudah di search

Pertemuan Keempat Tree, Binary Tree, dan Expression Tree

TREE



Apakah itu tree? Pohon? Didalam Data Structure tree adalah banyak node yang memiliki hubungan satu dan lainnya tetapi hubungan tersebut adalah hubungan suatu node didalam node lainnya dimana node tersebut memiliki kepala atau yang dapat disebut dengan root. Diantara 2 node terdapat sebuah penghubung berupa sebuah panah atau yang dapat disebut dengan edge. Selain itu juga terdapat node paling bawah atau node yang tidak memiliki node lain dibawahnya yang dapat disebut sebagai leaf.
Selain tree terdapat juga Binary Tree. 





BINARY TREE

Binary Tree adalah tree yang dimana suatu node hanya memiliki maksimal 2 node dibawahnya atau 
dapat disebut node tersebut hanya memiliki maksimal 2 anak. 2 anak ini dapat disebut juga anak kiri dan anak kanan. Binary tree memiliki beberapa tipe yaitu :

• Rooted binary tree
• Full Binary Tree
• Perfect Binary Tree
• Complete Binary Tree
• Infinite Complete Binary Tree
• Balanced Binary Tree
• Degenerated Binary Tree

Pembagian ini dibagi sesuai dengan hubungan dari node orang tua dan node anaknya.
 

 

Pertemuan Kedua Pengajar Tamu

BIG DATA

Apakah itu big data? Big data adalah sebuah istilah dalam sebuah set data yang sangat besar atau kompleks dimana hal tersebut membuat pemroses data traditional tidak memadai. Big data biasanya juga termasuk data set dengan ukuran yang diluar kemampuan software untuk meng-capture, curate, managee, dan memproses diantara waktu yang dapat di tolerir.

RASPBERRY PI

Raspberry pi adalah sebuah single board circuit yang dimodifikasi sedemikian rupa sehingga mudah untuk dibawa oleh penggunanya karena ukurannya sangat kecil dan hanya sebesar kartu identitas penduduk atau kartu kredit. Walaupun kecil raspberry pi dapat digunakan untuk berbagai macam hal seperti gaming, spreadsheet, dan juga memutar video dengan quality yang tinggi. Didalam pengembangannya sudah terbuat 3 tipe raspberry pi yaitu Raspberry pi model A, Raspberry pi model B v1, dan juga Raspberry pi model B v2.