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

Pertemuan 2-Linked List Implementation I-2101655475-Daniel Yuan Markus

LINKED LIST

Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat dari record selanjutnya.

- Linked List lebih efisien dalam penggunaan memori, karena ketika kita hendak menyimpan data, baru kemudian dia akan meminta memorinya.
- Linked List akan mendukung bentuk struktur data yang lain

Ada beberapa macam Linked List yaitu :
1. Single Linked List
2.  Circular Single Linked List
3. Double Linked List
4. Circular Double Linked List
5.  Header Linked List

Single Linked List

Single Linked List = Menggunakan sebuah variabel  pointer   dan Pointer next nya menunjuk ke

node selanjutnya.

Nodes = Objek yang mereferensikan dirinya sendiri

Syntax :

struct tnode{

   int value;

   struct tnode *next;

};

struct tnode *head =0;

- Single Linked List : Insert

Untuk insert ada 4 macam cara :

1. Didepan (head)

Syntax :

struct tnode * node =

   (struct tnode*) malloc (sizeof(struct tnode) );

node -> value = x; //Berarti kita isi variable value yang ada di node yang baru

node -> next = head;

head = node;

2. Dibelakang (tail)

3. Ditengah (Setelah node yang kita tentukan)

4. Ditengah (Sebelum node yang kita tentukan)

- Single Linked List : Delete

   Ada 2 kondisi yang harus kita perhatikan : Jika x ada didepan node / x tidak ada didepan node

Syntax :

struct tnode *curr = head;

//Jika x ada dibagian depan node

if(head -> value == x){

   head = head -> next; //Maka head akan pindah ke sebelahnya

   free(curr);

}

//Jika x ada dibagian belakang node

else if(tail -> value == x ){

   while (curr -> next !=tail) curr = curr-> next;

   free(tail); tail = curr;

   tail -> next = NULL;

}

//Jika x tidak ada di depan node, cari lokasinya

else{

   while(curr -> next -> value != x) curr = curr -> next;

   struct tnode *del = curr -> next;

   curr -> next = del -> next;

   free(del);

}

Polynomial Representation

Contoh :

Polynomial p(x) = p(x) = 8x⁵ + 7x⁶ + 4x²  + 8. Secara khusus, polynomial dibagi menjadi 2 bagian

yaitu Koefisien dan Eksponen dari suku yang bersangkutan. Maka dapat direpresentasikan seperti

berikut :

| 8 | 5 |   | -> | 7 | 6 |   | -> | 4 | 2 |   | -> | 8| 0 | x |

Circular Single Linked List

Circular Single Linked List =  Single Linked List yang pointer nextnya menunjuk pada dirinya

sendiri. 

- Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node

  terdepannya sehingga Linked List tersebut berputar. 

- Node terakhir akan menunjuk lagi ke head.

Double Linked List

Double Linked List  = Memiliki 2 variabel pointer yaitu pointer yang menunjuk ke node selanjutnya

dan pointer yang menunjuk ke node sebelumnya 

Syntax :

struct tnode{

   int value;

   struct tnode *next;

   strcut tnode *prev;

};

struct tnode *head = 0;

struct tnode *tail = 0;

- Double Linked List : Insert

   Pertama, kita harus mengalokasi node baru  dan memberikan nilai kepadanya. Lalu kita hubungkan

   node tersebut dengan Linked List yang sudah ada

Syntax :

struct tnode *node =

   (struct tnode*) malloc (sizeof(struct tnode) );

 node -> value = x;

 node -> next = NULL;

 node -> prev = tail

 tail -> next = node;

 tail = node;

- Double Linked List : Delete

   Ada 4 kondisi yang perlu diperhatikan ketika "Delete":

  1. Kondisi jika Node tersebut hanya satu - satunya di Linked List

Syntax :

free(head);

head = NULL;

tail = NULL;

  2. Kondisi jika Node ada di Head

Syntax :

head = head -> next;

free (head -> prev);

head -> prev = NULL;

  3. Kondisi jika Node ada di Tail

Syntax :

tail = tail -> prev;

free (tail -> next);

tail -> next = NULL;

  4. Kondisi jika Node tidak di Head / Tail

Syntax :

struct tnode *curr = head;

while(curr -> next -> value != x) curr = curr -> next;

struct tnode *a = curr;

struct tnode *del = curr -> next;

a -> next = b;

b -> prev = a;

free(del);

Circular Double Linked List

Circular Double Linked List = Terdapat node yang memiliki 3 field, yaitu 1 field pointer yang

menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field

yang berisi data untuk node tersebut.

Header Linked List

Header Linked List = Header spesial yang terdiri dari node headernya. Jadi Linked List tersebut

tidak menunjuk pada node pertama (head) namun hanya menyimpan alamat dari node headernya.

Contoh Tanpa Header Node:

L : |   |  ->  |  ant |   |  ->  |  bat  |   |  -> | cat |  \  |

Contoh dengan Header Node : 

L : |   |  ->   |       |     |  ->  |  ant |   |  ->  |  bat  |   |  -> | cat |  \  |