Heap , Deap !

HEAP
Heap merupakan salah satu proses yang ada dalam Binary Search Tree.
Heap sendiri dibedakan menjadi 3 macam:
       -Min Heap.
       -Max Heap.
       -Min-Max Heap.
Dalam Heap dibedakan menjadi 2 macam Proses : Insertion, dan Deletion.

Min Heap : Memiliki ciri-ciri sebagai berikut;
       -Setiap elemen Node yang ada harus lebih kecil dari elemen Children(anaknya).
       -Elemen Node yang terkecil terletak pada ROOT.
       -Elemen Node yang terbesar terletak pada salah satu node yang ada di LEAVES.





Berikut adalah konsep Insertion dalam Heap
 
 kita akan memasukkan angka dengan value 2
Pertama-tama yang angka 2 akan dimasukkan ke dalam index angkat terakhir yang ada dalam tree tersebut. Angka 2 akan dimasukkan ke sebelah 8. (selalu diinsert dari node dengan index terakhir).



Disini, pengecekan dilakukan karena ciri-ciri dari heap adalah setiap Node yang ada selalu lebih kecil dari Node anaknya (children). value angka 2 lebih kecil dari parentnya yaitu 6. Maka karena 6 > 2 , angka 2 akan naik dan mereplace kedudukan 6 dan berlaku sebaliknya.




Disini pengecekan pun berhenti karena angka 2 lebih besar dari parent Nodenya yaitu 1. maka insertion dalam Min heap pun telah selesai.

Deletion


Deletion pada root.
Pertama , Root akan dihapus, lalu penggantian akan dilakukan terhadap INDEX terakhir dalam tree. Maka angka 8 akan meng-replace angka 1(yang akan di delete).

Namun, karena ciri2 dalam heap tidak di penuhi dari tree tsb, karena nilai ROOT nya lebih besar dari children yang ada maka pengecekan dilakukan


Karena nilai 8 lebih besar dari nilai 3, maka di swap. dan proses ini dilakukan terus menerus sampai tree tersebut memenuhi syaratnya

Max Heap
Proses yang ada dalam Max Heap hampir sama dengan Min Heap, hanya pembalikan saja. Dimana ROOT memiliki value yang paling besar, sedangkan leave memiliki value kecil.




Konsep Insertion dan deletion juga berlaku sama dengan Min heap , namun value yang besar lebih di prioritaskan dari pada yang kecil.

Min - Max Heap


Min Max Heap, memiliki konsep dimana, setiap level ganjil dimulai dengan MIN, dan level genap dimulai dengan MAX heap.  Maka, value terkecil terletak dalam ROOT.

Deap

Deap memiliki konsep yang sama heap, lebih tepatnya min-max heap yang lebih sederhana.
Berikut adalah aturan aturan yang ada dalam Deap:
1. root selalu NULL
2. left subtree dari root adalah min-heap
3. right subtree dari root adalah max-heap

Sesuatu yang unik dari deap adalah sesuatu yang bernama "partner". Partner adalah pasangan dari sebuah node dari deap.  Di bawah akan dijelaskan dengan lebih detail mengenai partner. 



Yang dimaksud adalah, lihat bagian tree sebelah kiri, jika diperhatikan bagian kiri memiliki MIN HEAP sedangkan bagian sebelah kanan memiliki MAX HEAP.
Partner adalah Node yang berdampingan dari MIN heap ke Max Heap, contohnya pada gambar sebelah kanan bisa dilihat, bahwa PARTNER dari angka 10 adalah 50, angka 12 dengan 40 dan angka 25 dengan Node yang kosong.
Bila lokasi partner ternyata kosong, maka partnernya menjadi parent dari posisi partner yang seharusnya.


Nama : Dickson
NIM : 1701291283
Binus University

Red Black Tree

Atau disingkat sebagai RBT, adalah jenis tree yang di seimbangkan dengan pengelompokan warna yang di bedakan menjadi 2 warna yaitu hitam dan merah.

Syarat-Syarat yang berlaku dalam RBT:

• Setiap Node memiliki warna, antara hitam atau pun Merah.
• Root yang ada dalam Tree tersebut harus berwarna Hitam.
• Setiap External Node yang ada berwarna Hitam.
• Jika sebuah Node berwarna Merah, maka kedua anaknya pasti berwarna Hitam.

Setiap Operasi yang ada dalam Red Black Tree dibagi menjadi 2 Proses, Insertion dan Deletion.

Insertion:
Dalam Insertion, proses yang dilakukan sama dengan Binary Search Tree. Namun memiliki syarat setiap Node yang dimasukan memiliki warna Merah.
Apabila saat Node dimasukkan, memiliki Parent yang berwarna Merah, maka ada pelanggaran yang terjadi dari aturan yang telah ditetapkan.
Untuk memperbaikinya, kita bisa melakukan LL, LR, RR, RL rotation. agar Tree tersebut kembali seimbang dan memenuhi syarat pewarnaan yang ada.




 Berikut adalah contoh dari double rotation


Perhatikan bahwa setiap Node leave terakhir memiliki external node dengan default color black.

Deletion
Berikut adalah catatan yang diberikan dari dosen saya.

Delete

M = target delete

C = pengganti

jika M = red   , C = Black langsung ganti

jika M = black , C = red langsung ganti dan recolor C = black

jika M = black , C = black akan menciptakan token double black di posisi C

C = N

S = sibling

Sl = sibling left

Sr = sibling right

P = parent

kondisi 1 jika S = red , SL & SR = black

maka reverse color P dan S dan rotate di P , token black tetap ada di N

kondisi 2 jika s = black , SL & SR = black

maka recolor S = red , token black pindah ke P

jika warna P = red recolor jadi black jika P = black maka terjadi double black lg

kondisi 3 jika S = black , SL / SR = RED

maka rotate di parent (single/double), parent baru mengikuti warna parent lama dan kedua anaknya jadi hitam , lalu token black hilang

nb : jika token double black berada pada node merah, maka node tsb menjadi hitam dan

token double black hilang.

 

Stack and Implementation

Pertemuan 5

Pada pertemuan kelima kita diajarkan mengenai Stack and Implementation.

Pada pertemuan ke 5, topik pembicaraan nya memiliki sangkut paut dengan pertemuan ke empat.

Stack : Memiliki 2 konsep , LIFO (Last In First Out) dan FILO (First in Last Out). Sebagai Contoh, semisal ada tumpukan piring, kita pasti mengambil tumpukan piring teratas terlebih dahulu kecuali ada orang yang repot yang ingin mengambil piring dari tengah, Memang ada 2 kemungkinan. Tetapi kalau kita ambil contoh tabung yang hanya memiliki 1 tempat keluar seperti misalkan tabung bola tenis (kalau beli di supermarket beli bola tenis yang 1 tabung memiliki isi 3) hanya bisa dikeluarkan dari one side saja. Itulah konsep dari stacking.
Dalam stacking ada yang dimaksud dengan Top. Yang digunakan untuk mengidentifikasikan parameter yang ada di atas.  Contoh yang sering digunakan adalah Tower Of Hanoi, dimana untuk menyelesaikan masalah tower of hanoi, yang di keluarkan dari tiang masing masing adalah balok yang ada di paling atas.

Dalam Stack ada 3 macam operasi: push (untuk menambahkan item ke dalam Top of the stack), pop (untuk menghapus item yang ada di Top). dan Top itu sendiri (untuk menunjuk item mana yang ada dipuncak / diatas).


Queue : Memiliki konsep FIFO (First In First Out) dan LILO (Last in Last Out). Dimana benda yang masuk pertama kali pasti akan keluar terlebih dahulu. Contohnya bila kita sedang mengantri di kasir, orang yang pertama kali mengantri pasti akan keluar terlebih dahulu, First come first serve then out!
Istilah - istilah dalam Queue:

• Front : Tempat dimana data pertama akan diletakkan.
• Rear : Tempat untuk menentukan berapa banyak jumlah data yang dimasukkan.
• Kita juga mengenal instilah Dequeue dan Enqueue. 
• Dequeue : Melepaskan front, atau mendelete data atau biasa juga disebut pop.
• Enqueue : Memasukkan data baru.

Bila kita akan mendelete data, maka indikator Front akan mundur. Dan bila kita memasukkan data, maka indikator rear yang akan mundur.

Pada pertemuan ini kita juga membahasa mengenai postfix, prefix, dan infix, Seperti yang sudah dibicarakan pada pertemuan sebelumnya.
Lalu kita juga diperkenalkan dengan DFS (Depth First Search) dan BFS.

DFS (Depth First Search)

DFS adalah sebuah algoritma untuk mentranvers dan mencari data dalam tree dan graph. DFS biasanya digabungkan dengan cara rekursif.

Algorithma:

Prepare an empty stack

Push source/root into stack

Mark source/root

While stack is not empty

  Pop an item from stack into P

  For each node X adjacent with P

  If X is not marked

  Mark X

  Push X into stack

Nama : Dickson S.
NIM : 1701291283
www.binus.ac.id || www.skyconnectiva.com

Pertemuan ke-4


Dalam pertemuan kali ini, kami diajarkan mengenai "Introduction to Tree, Binary Tree and Expression Tree".

Tree : adalah koleksi dari 1 atau lebih node. (seperti yang di tunjukan dalam gambar).

Note : Dalam tree ada yang disebut sebagai root dan ada juga yg disebut sebagai leave.

Root : Adalah node yang berada pada yang paling atas atau yang paling utama. Dalam contoh gambar berikut, rootnya adalah 2.

Leaf : Adalah node yang berada pada yang paling bawah dimana ia sudah tidak beranak cucu atau memilik cabang lagi. Leave pada gambar berikut adalah 2,5,11 dan 4.

Ada juga yang disebut dengan Level. Dimana setiap Tingkat memiliki level tertentu apa bila berada dalam baris yg sama. Contohnya:

• Level 1 : 2 (karena berada dalam baris pertama dan di baris tsb hanya ada angka 2).
• Level 2 : 7 dan 5.
• Level 3 : 2 , 6, dan 9.
• Level 4 : 5, 11, dan 4.

Tree juga sering disebut seperti silsilah keluarga, contohnya Orangtua (Parent) dari angka 7 dan 5 adalah 2. Anak (Child) dari angka 6 adalah 5 dan 11, dan seterusnya.

Binary Tree :
Binary Tree adalah struktur dari Tree yang setiap nodenya hanya boleh memiliki kurang dari 2 anak dari rootnya sampai leaf. Biasanya 2 anak cabang tersebut dibedakan menjadi bagian kiri dan bagian kanan.

Tipe Tipe Binary Tree:

• Perfect Binary Tree : Setiap bagian dari tree tsb memiliki depth yang sama. 

•  Complete Binary Tree : Setiap bagian memiliki depth yg sama kecuali pada bagian akhir akan ada kosong 1 node.

• Skewed Binary : adalah Binary yang setiap bagiannya hanya memiliki 1 anak saja.
• Balanced Binary Tree : Balanced ("seimbang") maka setiap bagian node dari binary tree tsb memiliki nilai maksimum node lebih besar 2^k dari level sebelumnya. 

Representasi dalam Binary Tree:

• Index Left Child adalah 2p + 1, dimana p adalah indeks parent.
• Index Right Child adalah 2p + 2.
• Index Parent adalah (p-1)/2.

Dalam Tree ada juga proses yang disebut sebagai prefix, postfix, dan infix.
Prefix : adalah bentuk equation dimana letak operator berada di depan.
Postfix : adalah bentuk equation dimana letak operator berada di belakang.
Infix : adalah bentuk equation dimana letak operator berada di tengah.

Contoh : 2+a+b/2 * 3

    Prefix : + 2 + a * / b 2 3

    Profix : 2 a b 2 / 3 * + + 

Contoh : a + (b/2) * 3 / 2

    Prefix : + a / * / b 2 3 2 

    Profix : a b 2 / 3 * 2 / +

*Note : (Seperti matematika dasar, operator bagi dilakukan lebih dahulu lalu  perkalian, lalu penjumlahan, apa bila ada parentheses () maka equation itu dihitung lebih dahulu).

Dimana:

• Infix : Left V Right.
• Prefix : V Left Right.
• Postfix Left Right V.

Tugas : C / A * 2 + 3 / 12 + 21
     Prefix : + + / * / C A 2 3 12 21 
     PostFix : C A 2 3 1 2 21 / * / + +


Nama : Dickson Saputra.
NIM : 1701291283

   www.binus.ac.id || www.skyconnectiva.com

Pada pertemuan ke-3

Kami kedatangan tamu dalam bimbingan belajar Struktur data. Ia adalah Okky Pribadi. Bpk. Okky sendiri merupakan salah satu alumni universitas Binus. Sebagai lulusan Sistem Informasi. Namun, ia merupakan salah satu programmer yg bekerja di berbagai bidang seperti web designing untuk kostumernya dalam bidang entertainment maupun media. Beliau memiliki working experience yang banyak sehingga memungkinkannya untuk semakin maju setiap tahunnya. Mulai dari web designing untuk konsumer dan produsen.
Ia berposisi dalam bidang freelancing programmer, karena memiliki keuntungan yang lebih banyak, dan memiliki sisi positifnya yang bisa menguntungkan profit dibandingkan bekerja dikantoran.

Melalui pertemuan itu, kita bisa belajar banyak dari saran-saran yang diberikan seperti mempelajari bahasa bahasa yang sering digunakan menurut beliau sendiri bahasa yang ia tekuni adalah Java dan C# dalam web dan gaming. Pertemuan seperti ini memotivasi kita untuk belajar lebih tekun. Dan kita bisa lebih dipersiapkan saat kita lulus nanti agar tetap di jalur yang sama dengan jurusan Teknik Informatika.

Nama : Dickson S.
NIM : 1701291283

Linked List

Bahasa Melayu untuk Linked List = Senarai Berantai


Linked List dibedakan menjadi Single Linked List(Memiliki 1 node), Double Linked List(Memiliki 2 node, seperti next atau previous), Multiple Linked List(Memiliki node lebih dari 2).
 
Single Linked List
 
Dibagi menjadi 3 Cara : Push Depan, Push Belakang, Push Tengah.
Dalam penggunaan Single Linked List, ada baiknya kita mengerti konsep penggunaan struct (dalam bahasa C) terlebih dahulu.
Selain itu, juga ada cara untuk menDelete data yang telah dimasukkan atau yang sudah ada dalam linked list, penghapusan tsb disebut sebagai POP.
Pop sendiri dibagi menjadi 2 macam : POP depan, dan POP belakang.







 

 *Notice: Pada bagian belakang node (Tail Node) selalu memiliki nilai NULL.

Push Depan : Yang dimaksud dengan push depan adalah jika user memasukkan data baru maka, data tersebut akan ditetapkan kedalam alamat current / *curr. Setelah itu alamat yg memiliki data tsb akan di push ke arah head. Sehingga head = curr. Yang awalnya berurutan melalui Head, Tail, Current. Saat di push ke depan menjadi Head Current Tail. (inti dari push depan : data head berada di depan, data yang ada di tail berada di belakang).

Berikut adalah contoh Implementasi dari Push Depan dalam bahasa C:

struct Mahasiswa{
        char nama[25];
        struct Mahasiswa *next;
};

struct Mahasiswa *curr;
*curr = (struct Mahasiswa *) malloc (sizeof(struct Mahasiswa);
strcpy (curr -> nama, nama);
curr -> next = head;
head=curr;


Push Belakang: Memiliki konsep yang sama dengan push depan, namun dalam rangka Push Belakang, pada bagian Tail yang akan di push sehingga pada akhirnya yang berawal dengan posisi Head Current Tail. Saat disisipkan data baru menjadi Current (dalam Node tersendiri), Head (dengan Node Tersendiri), Tail(dengan Node tersendiri). Saat diimplementasikan Push belakang, posisinya akan menjadi -> Head & Current (dalam 1 node!), node, dengan Tail (node sendiri dengan terakhirnya diisikan NULL).

Berikut adalah contoh Implementasi dari Push Belakang dalam bahasa C:

if (head == NULL){
     head = tail = curr;
}else{
     tail -> next = curr;
     tail = curr;
}
tail -> next = NULL;
} 

POP Depan : Dalam menghapus depan, kita harus memastikan bahwa data yang sudah dimasukkan yang tadinya berada di current, sekarang berada pada head (depan).

void popdepan(){
      if (head == tail){
            head = tail = NULL;
            free (curr); //penghapusan dalam link list dsb sebagai FREE.
      }else{
            head = head ->next;
            free (curr);
      }
}

POP Belakang: Dalam menghapus Belakang, kita harus memastikan bahwa data yang sudah dimasukkan yang tadinya berada di current, sekarang berada pada head (depan).

void popbelakang(){
      struct Mahasiswa *curr = head;
      if (head == tail){
            head = tail = NULL;
            free (curr);
      }else{
             while(curr -> next != tail){
             curr = curr -> next;
      }   tail = curr;
          free (curr -> next);
          tail -> next = NULL;
      }
}

Array, Pointer, and Introduction to Data Structured

Array:

Array adalah sebuah kumpulan data yang terdiri dari tipe data yang sama. Setiap nilai yang berada di dalam array disebut sebagai element. Element tersebut memiliki data yang sama atau disebut juga sebagai Homogen.
Elemen yang terdapat didalam sebuah array akan disimpan kedalam sebuah lokasi memori yang beurutan. Urutan lokasi memori ini disebut sebagai Index. Penomoran Index pada memori tersebut selalu dimulai dari angka 0.
Deklarasi Array menurut dimensinya:

• Array Dimensi 1:
• Syntax : typename[size];
• Declaration : int angka[5];
• Access :
  angka[0] = 7;
  angka[1] = 2;
  angka[2] = 11;
  angka[3] = 5;
  angka[4] = 9;

• Array Dimensi 2:
• Syntax: typename[size1][size2];
• Declaration : int angka[3][2];
  *[3] menunjukkan jumlah baris.
  *[2] menunjukkan jumlah kolom.
•  Access:
  angka[0][2] = 2;
  angka[2][1] = 9;
  angka[2][2] = 13;
  angka[2][4] = 10;
•  Array Multidimensi:
• Syntax: typename[size1][size2][size3][size4][...];
• Declaration: int angka[3][2][4][6];
• Access: 
  angka[0][2][2][5]= 4;
  angka[2][1][3][2]= 7;
  angka[3][0][1][4]= 5;
  angka[2][2][1][3]= 11;

Cara Menyimpan data dalam Array:

•  Initialization of Arrays:
  int angka[4] = {20, 21, 24, 30};
  *notice: Perhatikan dalam array, misalkan jumlah index yang diindikasikan ada 4. penomoran index selalu dimulai dari 0, maka seperti pada contoh inisialisasi diatas, pada index 0 = 20, index 1 = 21, index 2 = 24, dan pada index 3 = 30. Sedangkan pada index 4 tidak ada isi dikarenakan index 4 diisikan oleh NULL, dan akan selalu seperti ini. Rumus pernyataan tersebut adalah N-1. Dimana N adalah Jumlah Index.
•  Inputting Values :
   kita menginisialisasikan values dalam array melalui kehendak user, menggunakan I/O.   

•  Assigning Values:
   Menetapkan Nilai yang ada kedalam array tersebut.

Operations yang terdapat dalam sebuah Array : Traversal, Insertion, Searching, Deletion, Merging, Sorting.


Pointer

Pointer adalah tipe data yang menunjuk pada isi tipe data yang ada pada memori komputer yang ada pada tempat lain, yang diakses melalui alamat tersebut.

2 hal terpenting yang digunakan dalam mengakses pointer adalah:

• & = untuk mengakses alamat operator.
• *  = Untuk mengakses isi yang ada pada alamat yang ditunjukan.

Contoh Pengaksesan melalui pointer:
int *ptr;        
int x= 20;
ptr = &x;     
ptr = 20;  
 
Data Structured

Struktur Data adalah perkumpulan data yang sudah di arrange (diatur) yang terdapat dalam memori komputer atau di disk storage.

Struktur Data mencakup :
     - Array.
     - Linked List. 
     - Queues.
     - Stacks.
     - Binary Trees.
     - Hash Tables.

*Linked List = adalah sebuah dinamik struktur data yang setiap elementnya bisa ditambah atau dihapus sesuai keinginan user. Setiap Element yang ada pada Linked List disebut sebagai Node.
*Queues = Element yang di-insert itu selalu First In First Out (FIFO). Element yang masuk harus menunggu Element yang pertama untuk menyelesaikan tugasnya. Contohnya : Antri di bank.
*Stacks = Dapat direpresentasikan sebagai linear array. Pada Stack berlaku sistem, Last in First Out (LIFO). Dimana maksud dari sistem tersebut yang terakhir kali masuk akan menjadi orang yang pertama kali keluar. Contohnya, ada sebuah tumpukan buku (stack of books). User ingin membaca sebuah buku, maka dia mengambil buku yang ada pada tumpukan paling atas dari stack buku tsb. Sehingga buku yang terakhir kali ditumpuk menjadi buku yg pertama kali dibaca oleh user. 
*Binary Trees = Struktur data yang didefinisikan melalui koleksi element yang disebut sebagai Nodes. 
*Data Types = Koleksi / Kumpulan Objek, dan set operasi yang digunakan untuk mengakses objek tsb.


ADT

ADT adalah tipe data yang diorganisasikan sedemikian rupa sehingga spesifikasi dari objek dan spesifikasi dari operasi tersebut pada objek dipisahkan oleh representasi dari objek dan diimplementasikan kepada operasi. 

ADT mensupport bahasa C / C++, dimana pada C menggunakan struct, dan di C++ menggunakan Class. 



NAMA = Dickson Saputra.
NIM = 1701291283
Kelas = 02 PGT.