5 – Tree and Binary Tree – 2101651786 – Rio Rafelino

Binary Tree (BT) telah dijelaskan pada pertemuan keempat dan pada hari ini kami belajar mengenai Binary Search Tree(BST). Perbedaan yang mendasar dari BT dan BST adalah kumpulan data pada BST sudah sorted alias sudah urut. 

Metode pengurutan data pada BST:

1. Data angka pertama yang masuk akan jadi root.

2. Data kedua, ketiga, keempat, dst yang masuk akan jadi right chilld atau left child dengan rule dimana jika angka yang masuk lebih besar maka akan menyabang ke kanan, dan jika angka yang masuk lebih kecil maka akan menyabang ke kiri.

Tujuan dari Binary Search Tree ini adalah agar pencarian data makin mudah. Jadi prinsipnya, jika data yang dicari lebih besar maka tinggal turun ke cabang kanan dan jika data yang dicari lebih kecil maka turun ke cabang kiri.

Operasi" pada Binary Search Tree:

1. Find

2. Insert

urut-urutan insert data adalah sebagai berikut: (lebih besar ke kanan, lebih kecil ke kiri)

3. Delete

Kalo pada sistem delete, jika node yang perlu dihapus memiliki descendant maka node tsb akan di replace dengan node dari descendant yang memenuhi syarat. dalam hal ini 35 memenuhi syarat untuk menggantikan 37 karena dia lebih besar dari 30 sehingga pas ditempatkan sebelah kanan 30, dan dia lebih besar dari 32 serta lebih kecil dari 45

4- Introduction to Tree, Binary Tree, and Expression Tree - 2101651786 - RIo Rafelino

Sebelum belajar lebih lanjut mengenai tree, mari belajar istilah istilah penting dalam konsep tree,
1. Node = bulatan / titik/ tempat" yang berisi data, node paling atas disebut dengan root
2. Edge = garis yang mengubungkan parent dengan child
3. Leaf = node yang tidak mempunyai children
4. Sibling = 2 node yang memiliki parent yang sama
5. Degree = level (A di degree 1, B dan C di degree 2)
6. Depth/Height = kedalam dari tree, degree tertinggi, dalam gambar, depth=3
7. Ancestor dan Descendant = jika ada 2 atau lebih node yang saling berhubungan melalui edge, maka semua node yang diatas merupakan ancestor dari node dibawahnya, begitu berlaku sebaliknya.

Konsep Binary Tree = Pohon yang dimulai dari akar tunggal dimana setiap node paling bnyak memiliki 2 children, yang dibagi jadi left child dan right child

Tipe" Binary Tree:
1. Perfect Binary Tree
ada binary tree sempurna, kalau manusia baru tidak ada yang sempurna WKWK. Binary Tree mencapai kesempurnaanya jika tiap node memiliki 2 children, gak ada yang satu anak cukup atau tidak mau punnya anak sama sekali (selalu pakai pengaman) *canda pak, biar apalinnya asik

2. Complete Binary Tree
Complete binary tree adalah binary tree yang tiap tingkat terisi penuh kecuali yang terakhir, jadi binary tree lengkap karena dia pnya segalanya, leaf pun harus ada.

3. Skewed Binary Tree
binary tree yang tiap nodenya punya satu children.

4. Balanced binary Tree
bisa apa aja asal perbedaan kedalaman antara 2 subtree pada suatu node tidak lebih dari 1

3 - Implementation of Linked List II - Rio Rafelino - 2101651786

STACK
Konsep stack ini sendiri dapat dipahami jika kita menganalogikan tumpukan data seperti koin yang dimasukan ke coin holder, jadi data yang masuk terakhir akan diambil pertama, LIFO (last in first out). Jadi data ditumpuk dan diambil dari data pada posisi top (paling atas).

Jadi konsep stack ini merupakan struktur data linear seperti array dan linked list.

Dalam stack ada 3 operasi penting yaitu:
1. Push : menambahkan data ke top
2. Pop : menghapus data dari top
3. Top : menngembalikan data ke data top

ada beberapa cara penulisan aritmatika dalam dunia coding:
1. Prefix evaluation (reverse polish notation)
penulisan operator sebelum operand
2. Postfix evaluation(polish notation)
penulisan operator setelah operand
3. Infix evaluation
penulisan operator diantara operand

QUQUE
ini juga merupakan linked list yang berupa deretan linear data. dimana dalam quque ini kita akan mengambil data dari TOP dan memasukkan data dari BOTTOM, persis dah seperti ANTRIAN BCA, jadi prinsipnya FIFO (First In First Out).

BINARY TREE
Susunan data yang disusun seperti pohon, bermula dari akar, kemudian nyabang" dan seterusnya. Bentuknya seperti ini:

Ada 2 metode pencarian data dalam binary tree seperti yang dulu udah pernah dipelajari di Discrete Math semester 1

misalnya soalnya seperti binary tree dibawah:

Yang pertama, DFS (Depth First Search), prinsip dari metode ini adalah backward after nabrak :D
jadi dalam metode ini, komputer akan mencari melalui cabang kiri dulu, lalu turun ke cabang selnajutnya, jika udah gak ada cabang kiri lagi, maka naik, kemudian ke cabang kanan.
jadi algoritmanya pencariannya: A-B-D-B-A-C-E-C-F

kemudian yang kedua, BFS (Breath First Search), prinsip dari metode ini adalah mencari pada level 1 (A) kemudian ke level 2 (B,C) kemudian ke level 3 (D,E,F) dst.

LOGO FOOTER GDSC BINUS

2 - Implementation of Linked List - Rio Rafelino - 2101651786

Pada intinya linked list itu merupakan list yang data yang tiap list nya ditandai dengan pointer yang mengarah ke list selanjutnya.

jika dalam konsep array, 

misal char array[100], 

maka array tersebut akan membooking 100 alamat memori setelahnya,  hal ini menyebabkan dis efisiensi memori karena belum tentu semua dari 100 alamat memori tersebut terpakai.

untuk lebih mengefektifkan memori, maka diciptakan konsep linked list, dimana setelah list pertama dibuat, jika dikemudian saat butuh list selanjutnya, maka tinggal ditandai dengan pointer yang menghubungkan ke alamat memori list pertama.

penandaan linked list pertama diberi *head, kemudian bisa ditambahkan lanjutannya spt pd gambar dibawah ini...

bisa juga dihapus seperti gambar dibwah ini...

dalam konsep linked list, dikenal istilah circular single linked list dimana node terakhir diberi pointer yang mengarah ke node pertama.

dalam hal ini keuntungannya adalah tidak ada node berisi NULL

semua yang telah dijelaskan diatas adalah konsep dari Single Linked List dimana hanya head yg didefinisikan

Pada Double Linked List, head dan tail didefinisikan, selain itu konsep logika insert deletenya sama.

1 - Array and Linked List - Rio Rafelino - 2101651786

Pada pertemuan hari ini kami mereview dan mempelajari beberapa hal baru mengenai Data Structures

Data Structures adalah kumpulan data yang bisa berbentuk array, struct, linked list, queque, stacks, binary trees dan disimpan dalam memori komputer, bersifat dynamic storing..

1. Array: sebuah kumpulan dari elemen data yang bertipe sama (homogen), masing- masing elemen disimpan dalam indeks, dan index nya bermula dari 0

berikut gambar contoh mengenai array yang saya buat sendiri

array bisa berbentuk one dimensional array, two dimensional array, dan multi dimensional array..

contoh two dimensional array:

int nomorkursi[100][20]

(angka 100 menunjukan sumbu y, angka 20 sebagai sumbu x)

2. Pointer: variabel yang menyimpan alamat dari sebuah nilai.

saat kita mendeclare suatu nilai misal int x=0, maka 0 akan menempati suatu alamat pada sel memori,

nah jika kita ingin menggunakan nilai 0 ini kembali, maka kita dapat memanggil alamatnya dengan cara &x, simbol "&" disini yaitu suatu penulisan dalam pointer yang berarti perintah "woy visual express, ambilin nilai pada alamat x dong!" sehingga akan lebih efisien dalam penggunaan memori.

namun perlu diingat declare nilainya harus ada format khususnya, berikut:

int a
int *x=0 (menggunakan bintang)

a=&x

3. Queque (antrian): suatu kumpulan data dimana penambahan elemen hanya bisa dilakukan pada satu ujung (tail) dan pengambilan/penghapusan elemen dimulai dari ujung satunya (head). menggunakan prinsip FIFO (first in, first out) seperti pada shuttlecock badminton.

berikut ilustrasi yang saya buat sendiri..

4. Stacks (tumpukan):Pertama masuk, terakhir keluar. masuk terakhir, keluar pertama. stacks ini mirip dengan queque namun kebalikannya, menggunakan prinsip tumpukan seperti tumpukan karung beras, tentu yang diambil yang paling atas (yang terakhir ditaruh).

5. Binary Tree
struktur data dimana setidaknya tiap node memiliki 2 anak data.

PERTANYAAN TAMBAHAN (update 20 Februari 2018, 22.41)
1. Berapa banyak jumlah maksimal dimensi dari sebuah array?

Secara teori tidak ada batas, namun secara praktek, batasannya adalah ukuran memori komputer itu sendiri dan compiler yang digunakan (sumber: http://www.examveda.com/what-is-the-maximum-number-of-dimensions-an-array-in-c-may-have-c-programming-arrays-and-strings-6/)

Pada Java VM dibatasi pada 255, (sumber: https://www.quora.com/How-many-maximum-dimensions-can-an-array-have-in-C-C++-or-Java)

atau ada juga yang menyebutkan batasannya adalah 12, berdasar http://c0x.coding-guidelines.com/5.2.4.1.html

2. Apa beda dari single dan double pointer? apakah ada batasannya?

Single pointer untuk pass value,
sedangkan double pointer untuk passing alamat dari pointer yang menyimpan alamat suatu value
(sumber: https://stackoverflow.com/questions/25107039/confused-by-single-pointer-and-double-pointer-arguments-in-function-calls)

batasannya adalah 12 (sumber:http://c0x.coding-guidelines.com/5.2.4.1.html)

artikel ini telah selesai dibuat sejak 20 Februari 2018, 22.45..
namun saya masih mencari update jawaban dari pertanyaan tambahan

Contoh Kuis Matematika

Maaf ya.. gambarnya agak jelek.. wkwkwkwk... karena ini gambar saya sendiri yg buat melalui program "paint".

ini adalah gambar persegi  dengan sisi sepanjang 1 cm
dan bagian yang dihitami itu maksud saya adalah bagian yang diarsir

soal : hitunglah luas bagian yang TIDAK diarsir !

bisa ngerjain ga ???
wkwkwkwk
pasti bisalah..

silahkan dicoba dulu.. baru lihat jawaban di bawah...



jawaban :

diketahui :
luas persegi 1cm persegi
tinggi segitiga siku siku : 1 cm dan alasnya : 1/2 cm

ditanya    :
luas bagian yang tidak diarsir

dijawab   :
= 1cm persegi - luas 2 segitiga siku siku besar ( 1/2 x 1 x 1/2 x 2 = 8/16 = 1/2) - luas segitiga siku siku kecil (1/2 x 1/2 = 1/4)
= 1 cm persegi - (1/2 cm persegi + 1/4 cm persegi)
= 1 cm persegi - 3/4 cm persegi
= 1/4 cm persegi

jadi, luas bagian yang tidak diarsir adalah 1/4 cm persegi.

demikian,

terima kasih.