Pertemuan 5-Binary Search Tree-21010655475-Daniel Yuan Markus

Binary Search Tree

Apa perbedaan dari Binary Tree dengan Graph ?
- Binary Tree = Tree dimana mempunyai maximum anaknya 2 dan Tidak ada looping
- Graph = Memungkinkan pencarian node yang terus berulang (Looping)

Apa perbedaan dari Tree dan Binary Search Tree ?
- Tree = Tidak ada urutannya
- Binary Search Tree = Ada urutannya. Setiap child node sebelah kiri selalu lebih kecil nilainya            daripada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar              nilainya daripada root node (If value is less go left , If value is greater go right)

Contoh Binary Search Tree :



Contoh 2 : 
Jika terdapat data, x = {50,17,76,9,23,54,14,19,72,12,67}. Maka akan dibuat Binary Search Tree seperti dibawah ini



Binary Search Tree Operation
- find(x) / search(x) = Untuk mencari data
- insert(x) / push(x) = Untuk memasukkan data
- remove(x) / pop(x) = Untuk menghapus data


Contoh Insertion (insert) :
Jika kita ingin menambahkan angka 4 pada Binary Search Tree.
- Maka bandingkan angka 4 dengan angka 5 (Gambar 1). Karena angka 4 lebih kecil dari 5, maka go    to left child.
- Kemudian bandingkan angka 4 dengan angka 2 (Gambar 2). Karena angka 4 lebih besar dari 2,          maka go to right child.
-  Lalu bandingkan angka 4 dengan angka 3 (Gambar 3). Karena angka 4 lebih besar dari 3, maka go     to right child.
- Terakhir, Tempatkan angka 4 di sebelah kanan sebagai right child dari angka 3(Gambar 4)


Gambar 1

Gambar 2

Gambar 3

Gambar 4

Contoh Deletion (remove) :
Ketika kita  menghapus angka 18(Gambar 1), maka  angka 21 akan menggantikan tempat dari 18 & child dari 21 akan mengikuti dibawahnya  (Gambar 2).


Gambar 1


Gambar 2

Pertemuan 4-Introduction to Tree, Binary Tree and Expression Tree-2101655475-Daniel Yuan Markus

TREE

Pengertian
Tree adalah  kumpulan satu / beberapa node yang saling terhubung satu sama lain yang membentuk suatu kesatuan layaknya struktur sebuah pohon.

Contoh 

Degree of Tree = 3
Height = 3
Parent of  B = A
Children of B = D, E
Sibling of G = H
Ancestor of F = A, C
Descendant of F =  G,H


Penjelasan :
- Root = Node yang berada paling atas
- Edge = Garis penghubung dari Parent ke Children
- Leaf = Node yang tidak memiliki Children
- Sibling =  Node yang memiliki Parent yang sama
- Degree = Banyaknya suatu child (sub tree) dalam suatu node
- Height = Banyaknya tingkatan dalam suatu tree
-  Jika ada 1 garis yang terhubung dari p ke q, maka p adalah Ancestor dari q. Sedangkan q adalah Descendant dari p


BINARY TREE CONCEPT

Pengertian
Binary Tree adalah Tree yang memiliki syarat bahwa tiap node hanya boleh memiliki maksimal 2 children yaitu Left Child dan Right Child

Kelebihan struktur Binary Tree :
- Mudah dalam penyusunan algoritma sorting
- Searching data relatif cepat
- Fleksibel dalam penambahan dan penghapusan data

Contoh Gambar :

Jenis dari Binary Tree :

- Perfect Binary Tree =  Binary Tree dimana setiap tingkatan memiliki kedalaman yang sama. Tiap node (kecuali leaf) memiliki 2 child (panjang path sama).

- Complete Binary Tree =  Mirip dengan Perfect Binary Tree, tetapi tiap sub tree boleh memiliki panjang path yang berbeda

- Skewed Binary Tree = Binary Tree yang semua nodenya hanya memiliki 1 child (kecuali leaf)

Property Binary Tree

- Maksimum number of  nodes di level k dari Binary Tree adalah  2^k

- Maksimum number of nodes dari Height h di Binary Tree adalah  2^h+1 - 1

- Minimum Height dari node di Binary Tree adalah ²log(n)

- Maksimum Height dari node di Binary Tree adalah n-1

Representation of Binary Tree

1. Implementation using array

- Index pada Array mewakili node number

- Index 0 adalah Root Node

- Index Left Child adalah 2p + 1 (P adalah Parent)

- Index Right Chilrd adalah 2p+2

- Index Parent adalah (p-1)/2

2. Implementation using Linked List

struct node {                 int data;                 struct node *left;                 struct node *right;                 struct node *parent; }; struct node *root = NULL;

EXPRESSION TREE CONCEPT

Contoh Soal

Prefix = */+5z-8^42

Postfix = 5z+8-/42^*

Infix =  [ (5+z)/8- ]* (4^2)

Struktur untuk tiap Node di Tree

struct tnode {                 char chr;                 struct tnode *left;                 struct tnode *right; };

Membuat Expression Tree dari Prefix

Main function Struct tnode *root = newnode (s[0]); f(root);

Prefix Transversal

void prefix(struct tnode *curr) {                printf( “%c “, curr->chr );                if ( curr->left  != 0 ) prefix(curr->left);                if ( curr->right != 0 ) prefix(curr->right); }

Postfix Transversal

void postfix(struct tnode *curr) {               if ( curr->left  != 0 ) postfix(curr->left);               if ( curr->right != 0 ) postfix(curr->right);                 printf( “%c“, curr->chr ); }

Infix Transversal

void infix(struct tnode *curr) {                 if ( curr->left  != 0 ) infix(curr->left);                 printf( “%c“, curr->chr );                 if ( curr->right != 0 ) infix(curr->right); }

Pertemuan 3-Linked List Implementation II-2101655475-Daniel Yuan Markus

STACK

Pengertian Stack
Stack (Tumpukan) adalah Struktur data linier yang dapat diimplementasikan dengan baik menggunakan array / Linked List
- Stack bersifat LIFO (Last In First Out), artinya data yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack

Contoh dari stack adalah seperti gambar diatas.  Seperti tumpukan piring (A-F), piring yang satu akan ditumpuk diatas piring yang lainnya. Bila kita ingin mengambil piring tersebut, kita harus mengambil piring dari yang paling atas (F). Jadi piring yang paling bawah / paling pertama ditumpuk (A), akan menjadi piring yang paling terakhir diambil

Array Representation
- Stack memiliki 2 variabel :
   1. Top =  Digunakan untuk menyimpan alamat unsur elemen dari stack
   2. Max =  Digunakan untuk menyimpan jumlah maksimum elemen yang dapat ditahan oleh stack
- Jika Top = NULL, maka Stack is empty(kosong)
- Jika Top = MAX-1, maka Stack is Full (penuh)

Liked List Representation

- Didalam Linked Stack, setiap node memiliki 2 bagian :

   1. Bagian yang menyimpan data

   2. Bagian yang menyimpan alamat dari next node

-  Start pointer dari Linked List digunakan sebagai Top

- Jika Top = NULL, itu berarti mengindikasikan bahwa Stack kosong

     

Operasi yang terdapat pada Stack :
- Push() = Digunakan untuk memasukkan data
- Pop() = Digunakan untuk menghapus data
- Top() = Digunakan untuk mengembalikan data  dari stack

Stack Applications
- Infix evaluation
- Postfix evaluation
- Prefix evaluation
- Infix to Postfix  conversion
- Infix to Prefix conversion
- Depth First Search


Infix, Postfix dan Prefix Notation

Prefix	Infix	Postfix
* 4 10	4 * 10	4 10 *
+ 5 * 3 4	5 + 3 * 4	5 3 4 * +
+ 4 / * 6 – 5 2 3	4 + 6 * (5-2) / 3	4 6 5 2 - * 3 / +

- Prefix = Operator ditulis setelah Operand (Rumus = Operator, Left Operand,  Right Operand)
- Infix = Operator berada diantara Operand
- Postfix = Operator ditulis setelah Operand  (Rumus = Left Operand,  Right Operand, Operator)


Depth First Search
Depth First Search adalah algoritma untuk melakukan penelusuran / pencarian struktur graf / pohon berdasarkan kedalaman

- DFS memiliki banyak aplikasi seperti :
   1. Menemukan artikulasi point dan brigde didalam graph
   2. Menemukan komponen yang terhubung
   3. Topological sorting

Aplikasi stack lainnya 

Stack biasanya digunakan untuk :

- Reverse the order of data

- Convert infix menjadi postfix

- Convert postfix menjadi infix

- Backtracking problem

- Syetem stack biasanya digunakan di setiap fungsi recursive

- Converting angka desimal menjadi binary equivalent

QUEUE

Pengertian Queue

Queue (Antrian) adalah  Struktur data penting yang menyimpan data secara teratur. 

- Queue bersifat FIFO (First In, First Out), artinya  data yang pertama kali masuk akan menjadi data 

  yang pertama kali keluar

Contoh :

Saat orang menunggu Bis. Orang yang berdiri di paling depan, akan menjadi orang pertama yang 

masuk ke bis

Queue memiliki 2 Variabel  : Front dan Rear

Operasi pada Queue :

- Push(x) : Digunakan untuk menambahkan data x ke bagian belakang Queue

- Pop() : Digunakan untuk menghapus data dari bagian depan Queue

- Front() : Mengembalikan data  paling depan dari Queue 

Queue Applications

- Deques

- Priority Queues

- Breadth First Search

Deques

Deques adalah proses dimana  elemen dapat dimasukkan /  dihapus dikedua ujung.

- Juga dikenal sebagai Head-Tail Linked, karena elemen dapat ditambahkan / dihapus dari depan 

  (head) / belakang (tail).

2 Varian dari Double-Ended Queue, termasuk :

- Input Restricted Deque = Insertion dapat dilakukan hanya pada salah satu Dequeue & penghapusan 

  dapat dilakukan dari kedua ujung  

- Output Restricted Deque = Penghapusan dapat dilakukan hanya pada salah satu Dequeue & 

  Insertion dapat dilakukan pada kedua ujungnya 

Breadth First Search

Breadth First Search (BFS) adalah Algoritma  untuk melakukan penelusuran / pencarian struktur graf

- BFS memiliki banyak aplikasi seperti  :

   1.  Menemukan komponan terhubung didalam graph

   2. Menemunkan jalan terpendek dalam unweighted graph

   3. Metode Ford-Fulkerson untuk komputasi aliran maksimum