Pertemuan 5 - Binary Search Tree - 2101696973 - Rifqi Amru Bakti

Nama : Rifqi Amru Bakti

NIM    : 2101696973

Session 5

Binary Search Tree

Binary Search Tree : 

Binary Search Tree(BST) adalah sebuah bentuk data struktur yang menyimpan "barang"(integer angka, char nama, dll) dalam memori. BST mampu melakukan pencarian cepat, penambahan, penghapusan barang, dan dapat digunakan untuk mengimplementasikan set item atau tabel pencarian yang memungkinkan penemuan barang berdasarkan kuncinya (seperti menemukan nomor HP melalui nama orang).BST merupakan sebuah "Rooted Binary Tree", dimana pada tiap node tersimpan sebuah kunci dan juga memiliki 2 "Sub-Tree" biasa dipanggil "Left" and "Right"(kiri dan kanan).

Sering sekali informasi yang direpresentasikan pada tiap node merupakan sebuah rekaman daripada satu data elemen. Namun, untuk kegunaan sequence, node dibandingkan sesuai dengan kunci yang dimiliki mereka daripada bagian manapun yang terikat dengan mereka. Keuntungan paling besar dalam penggunaan BST dibandingkan data struktur lain ialah hal-hal yang berhubungan dengan algoritma sorting dan searching relatif lebih efisien dan juga lebih mudah dikoding.

Operasi Binary Search Tree
BST memiliki operasi dasar ini :
- find(x) : mencari kunci x dalam BST
- insert(x) : memasukkan kunci x baru dalam BST
- remove(x) : menghapus kunci x dalam BST

Operasi Searching
Operasi Searching BST untuk mencari suatu kunci dapat diprogram secara rekursif dan iteratif.

Karena properti dari BST, mencari kunci dalam BST itu mudah.
Misal kunci yang ingin dicari adalah X.
- Dimulai dari root(akar)
- Jika root mengandung X search berhenti dengan suksess
- Jika X kurang dari kunci root, maka search akan rekursif ke Left Sub-tree, sebaliknya jika X lebih dari kunci root search akan ke Right Sub-tree.

struct node*search(struct node*curr,intx){
if(curr==NULL)return NULL;

//X ditemukan
if(X==curr->data)return curr;

//X ada pada Left Sub-tree
if(X<curr->data)return find(curr->left X);

//X ada pada Right Sub-tree
return find(curr->right,X);
}

Operasi Insert
Operasi InsertBinary Searcg Tree(pemasukan data) dilakukan secara rekursif.

Misal Node baru adalah X
- Dimulai dari root
- Jika X kurang dari kunci milik root X pergi ke Left Sub-tree, dan sebaliknya jika X llebih dari kunci milik root
- Diulang sampai ditemukan node kosong untuk menaruh X(X selalu menjadi Leaf baru)

if TREE=NULL, maka
alokasikan memori untuk TREE
     set TREE->data=value
     set TREE->left=TREE->right=NULL
else
if value<TREE->data
     insert(Tree->left,value)
else
     insert(Tree->right,value)

misal insert "4"



- 4 kurang dari 5, pergi ke kiri
- 4 lebih dari 2, pergi ke kanan
- 4 lebih dari 3, pergi ke kanan
- 4 sampai pada node kosong dan menjadi Leaf baru

Operasi Deletion
Ada 3 kasus yang harus dipikirkan ketika melakukan Dletion:
- Jika kuncinya merupakan sebuah Leaf, node didelete langsung
- Jika kunci merupakan node yang punya 1 Sub-tree, delete node tersebut dan sambungkan Sub-tree yang tadi pada Parents node yang terdelete
- Jika kunci merupakan node yang memiliki 2 Sub-tree, delete node tersebut dan digantikan dengan anak paling kanan dari Sub-tree kirinya atau anak paling kiri dari Sub-tree kanannya lalu delete anak yang digunakan

if Tree=NULL, maka
tulis "value not found in the tree"
else if value<Tree->data
     delete(Tree->left,value)
else if value>Tree->data
     delete(Tree->right,value)
else if Tree->left dan Tree->right
set temp=cariNodeTerbesar(Tree->left)
set Tree->data=temp->data
delete(Tree->left,temp->data)



- Bagian pertama menunjukkan delesi dari sebuah Leaf
- Bagian kedua menunjukkan delesi sebuah node dengan 1 anak
- Bagian ketiga menunjukkan dlesi node yang memiliki 2 anak

Rifqi Amru Bakti-2101696973

Pertemuan 4 - Introduction to Tree, Binary Tree and Expression Tree - 2101696973 - Rifqi Amru Bakti

Nama : Rifqi Amru Bakti
NIM    : 2101696973

Session 4
Introduction to Tree, Binary Tree and Expression Tree

Tree & Binary Tree:
- Konsep Tree 
- Konsep Binary Tree 
- Tipe-tipe Binary Tree 
- Properti Binary Tree 
- Representasi Binary Tree 
- Membuat Expresi Tree dari Prefix, Postfix dan Infix

Konsep Tree
Sebuah Tree adalah kumpulan dari satu atau lebih node.

- Note yang ada di paling atas dipanggil dengan Root
- Garis yang menyambungkan Node "Child" dengan Node "Parent" dipanggil          dengan Edge
- Node yang tidak memiliki anak dipanggil dengan Leaf Node
- Node yang memiliki "Parent" yang sama dipannggil dengan Sibling Node
- Degree node ialah total node anak yang ada di dalam Tree
- Height/Depth(Tinggi/Kedalaman) adalah Degree node maximal dalam            sebuah Tree
- Jika ada garis yang menghubungkan A ke B berarti B adalah                              Descendant(Keturunan) dari A dan A adalah Ancestor(Leluhur) dari B

Konsep Binary Tree
- Binary Tree adalah bentuk data structure pohon berakar dimana tiap Node        hanya memiliki anak paling banyak 2.
- Kedua anak tersebut dipanggil dengan Left Child(anak kiri) dan Right                Child(anak kanan).
- Node yang tidak memiliki anak dipanggil dengan Leaf.


Tipe-tipe Binary Tree
- Perfect Binary Tree
Perfect Binary Tree adalah tipe binary tree dimana tiap level memiliki              kedalaman(depth) yang sama.


- Complete Binary Tree
Complete Binary Tree adalah binary tree dimana pada tiap tingkat, kecuali        yang terakhir terisi penuh, dan semua Node sejauh mungkin terpisah. Binary Tree yang sempurna adalah Complete Binary Tree.


- Skewed Binary Tree
Skewed Binary Tree adalah bentuk binary tree dimana pada tiap node anak yang dimiliki paling banyak hanya satu.


- Balanced Binary Tree
Balanced Binary Tree adalah binary tree dimana tiada Leaf yang jauh dari Root daripada Leaf lainnya.


Properti Binary Tree
- Jumlah maximal node pada level k dari sebuah binary tree adalah 2^k.
- Jumlah maximal node pada binary tree dengan tinggi H adalah (2^(H+1))-1.
- Tinggi minimum dari sebuah binary tree dengan n Node adalah (2log(n)).
- Tinggi maximum dari sebuah binary tree dengan n Node adalah n-1.

Representasi Binary Tree

Representasi sebuah binary tree menggunakan Array dan Linked List
Membuat Expresi Tree dari Prefix, Postfix dan Infix

Prefix : F-B-A-D-C-E-G-I-H
Infix         : A-B-C-D-E-F-G-I-H
Postfix : A-C-E-D-B-H-I-G-F



Rifqi Amru Bakti-2101696973

Pertemuan 3 - Linked Lists Implementation 2 - 2101696973 - Rifqi Amru Bakti

Nama : Rifqi Amru Bakti
NIM    : 2101696973

Session 3
Linked Lists Implementation 2

Topic : 
- Konsep Stack
- Stack dengan Array dan Linked List
- Notasi Infix, Prefix, dan Postfix
- Evaluasi

Stack
Stack adalah sebuah data struktur penting yang menyimpan semua elemen dengan rapih dan teratur.

Analogi Stack
Anggap data struktur stack sebagai kumpulan piring yang tersusun dengan cara ditumpuk. ketika anda ingin mengambil sebuah piring, piring yang terambil ialah piring teratas atau piring pertama. Karena ini anda dapat menambah atau menghilangkan sebuah elemen (piringnya) hanya dari satu posisi yaitu posisi teratas.

Konsep Stack
- Stack adalah bentuk data struktur yang linear yang dapat di implementasikan    dengan menggunakan array atau linked list.
- Elemen-elemen yang ada di dalam sebuah stack ditamnahkan dan dikurangi      hanya dari sati posisi, posisi tersebut dipanggil top atau atas.
- Data yang tersimpan dengan stack tersimpan dengan cara "Terakhir Masuk        Keluar Duluan".

Representasi Array dalam Stack
Stack memiliki dua variabel : 
- TOP yang digunakan untuk menyimpan alamat elemen paling atas dalam          stack tersebut.
- MAX yang digunakan untuk menyimpan angka maximal sebuah elemen yang      dapat disimpan stack tersebut.
If TOP=NULL, ini mengindikasikan bahwa stack sedang kosong.

If TOP=MAX-1, berarti stack tersebut sudah penuh.

TOP=4, penginputan dan penghapusan akan dilakukan dalam posisi ini.

Representasi Linked List dalam Stack
Teknik pembuatan stack menggunakan array lebih mudah dipakai, akan tetapi terdapat kesulitan dalam penggunaan array. Kesulitannya ialah array tersebut harus di deklarasikan supaya memiliki ukuran yang tetap.


- Dalam linked list stack, tiap node memiliki dua bagian : 
  -> Yang menyimpan data.
  -> Yang menyimpan alamat node selanjutnya.

- Pointer START dalam linked list digunakan sebagai TOP.
- Semua penginputan dan penghapusan terjadi pada node yang tertunjuk oleh      TOP.

- If TOP=NULL, ini mengindikasikan bahwa stack tersebut kosong.

Operasi Stack
push(x) : menambahkan suatu elemen x kepada atas stack (TOP). 
pop() : menghapuskan suatu elemen dari atas stack (TOP).

top()         : menunjukan atau mengembalikan elemen top dari stack.

Notasi Infix, Prefix, dan Postfix
Terdapat tiga buah notasi aritmatika yang telah diketahui : 
- Prefix Notation
- Infix Notation
- Postfix Notation

Prefix : Operator ditulis sebelum operand.

Infix         : Operator ditulis ditengah operand.

Postfix : Operator ditulis setelah operand.

Evaluasi

Postfix Evaluation

Scan dari kiri ke kanan

7   6   5   x   3   2   ^   –    + , Scan sampai operator pertama

7   6   5   x   3   2   ^   –    + , Hitung 6x5

7   30           3   2   ^   –    + , Scan lagi hingga operator selanjutnya

7   30           3   2   ^   –    + , Hitung 3^2

7   30           9             –    + , Scan lagi sampai operator selanjutnya

7   30           9             –    + , Hitung 30-9

7   21                                + , Scan Lagi

7   21                                + , Hitung 7+21

28         , Selesai

Infix Evaluation

Misal Infix = 4 + 6 * (5 – 2) / 3.

Untuk mengevaluasi notasi Infix, kita harus mencari operator dengan prioritas tertinggi dalam string tersebut.

4 + 6 * (5 – 2) / 3 Cari operator dengan prioritas tertinggi, ditemukan ( )
4 + 6 * 3 / 3 Cari operator dengan prioritas tertinggi, ditemukan *
4 + 18 / 3         Cari operator dengan prioritas tertinggi, ditemukan  /
4 + 6 Cari operator dengan prioritas tertinggi, ditemukan +

10                            Selesai

Prefix Evaluation
Scan dari kanan ke kiri
+   7   –   x   6   5   ^   3   2   
+   7   –   x   6   5   ^   3   2   
+   7   –   x   6   5   9           
+   7   –   x   6   5   9           
+   7   –   30           9          
+   7   –   30           9          
+   7   21                           
+   7   21                           

28                                     
Penghitungan sama seperti pada Postfix, hanya saja posisi operator dibalik.

Rifqi Amru Bakti-2101696973

Pertemuan 2 - Linked Lists Implementation - 2101696973 - Rifqi Amru Bakti

Nama : Rifqi Amru Bakti
NIM    : 2101696973

Session 2
Linked Lists Implementation

Linked List : 
Linked lists merupakan sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan dalam linked lists dilakukan secara lebih efektif. 

Linked lists memiliki beberapa implementasi yang bekerja secara berbeda-beda, implementasi tersebut adalah : 

 - Singly Linked List
   Singly linked list adalah bentuk tipe data struktur linked list dimana tiap node     dalam listnya menyimpan suatu data dan pointer atau referensi ke node             selanjutnya yang ada di list tersebut. Untuk mengimplementasikan single           linked list, hanya pointer atau referensi pada node pertama di list yang harus     disimpan. Node terakhir pada single linked list tidak menunjuk pada apapun       atau NULL.

contoh Kodingan Singly Linked List : 

Mendefinisikan List

struct tnode 
{
int value;
struct tnode *next;
};


struct tnode *head = 0;

Insert List

struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next  = head;

head = node;

Delete List

struct tnode *curr = head;

// if x is in head node
if ( head->value == x ) {
head = head->next;
free(curr);}
// if x is in tail node
else if(tail->value == x){
while(curr->next!=tail) curr = curr->next;
free(tail); tail = curr;
tail->next = NULL;
}
// if x is not in head node, find the location
else {
while ( curr->next->value != x ) curr = curr->next;
struct tnode *del = curr->next;
curr->next = del->next;
free(del);
}

 - Doubly Linked List
   Doubly Linked List adalah bentuk tipe data struktur Linked List yang memiliki     dua variabel pointer, pointer yang menunjuk ke node berikutnya dan pointer       yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga tidak             menunjuk pada apapun atau bisa dibilang menunjuk NULL.

Contoh Koding : 

List

struct tnode 
{
int value;
struct tnode *next;
struct tnode *prev;
};

struct tnode *head = 0;

struct tnode *tail = 0;

Insert

struct tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next  = NULL;
node->prev  = tail;
tail->next  = node;

tail = node;

Delete

free(head);
head = NULL;

tail = NULL;

(Mendelete satu node)

head = head->next;

free(head->prev);

head->prev = NULL;

(Node yang di delete node Head)

 - Polynomial Representation
   Dalam Polynomial Representation dapat diasumsikan bahwa tiap linked list         menyimpan dua nilai yang berbeda-beda. Dalam bentuk polinom dibawah,         setiap nilai dalam node memiliki nilai asli dan pangkat variabelnya.

Dimisalkan polinom yang didapat adalah 6x^3 + 9x^2 + 7x + 1 .
dalam polinom tersebut 6, 9, dan 1 adalah koefisiennya sedangkan pangkat koefisien tersebut adalah 3, 2, 1, dan 0 karena mereka tidak memiliki nilai x.

 - Multi Linked List
   Multi Linked List merupakan bentuk unik linked list dimmana tiap node               memiliki pointer kepada satu atau lebih node dalam linked list tersebut.

 - Circular Linked List
   Circular Linked List merupakan bentuk linked list dimana node terakhir(tail)       menunjuk kepada node pertama(head). Oleh karena ini, node dalam Circular     Linked List tidak ada yang menunjuk NULL.

Ada dua jenis Circular Linked List, List tersebut ialah : 
 > Circular Single Linked List

 > Circular Doubly Linked List

 - Header Linked List

   Header Linked List adalah suatu bentuk linked list dimana ada sebuah node       yang dijadikan sebagai "Header" di awal dari list. Bentuk dari Header Linked       List dapat dilihat pada gambar dibawah, Header node berada pada awal list       tersebut.

Rifqi Amru Bakti-2101696973

Pertemuan 1 - Pointer, Array & Introduction to Data Structure - 2101696973 - Rifqi Amru Bakti

Nama : Rifqi Amru Bakti
NIM    : 2101696973

Session 1
Pointer, Array & Introduction to Data Structure

Array
- Array adalah suatu kumpulan data yang memiliki tipe data yang sama(homogen).
- Array disimpan dari memori menggunakan index yang dimulai dari 0.
- Dimensi maximal suatu Array adalah 256.

Jenis-jenis Array
- One Dimensional Array
  > Syntax = typename[size]
    Declaration : 

int boi[2];

    Accessing :

boi[0] = 2

boi[1] = 7

 boi[2] = 11

- Two Dimensional Array
  > Syntax = typename[size1][size2]
    Declaration :

int boi[3][6];

    Accessing :

boi[0][2] = 6

boi[2][1] = 9

 boi[1][5] = 12

 boi[2][4] = 15

- Multi Dimensional Array
  > Syntax = typename[size1][size2][size3][...]
    Declaration : 

int boi[4][3][7][10];

    Accessing : 

boi[0][2][2][9] = 25

boi[2][1][6][0] = 69

 boi[3][0][0][6] = 87 

boi[2][1][3][8] = 96

Menyimpan Nilai Array

Nilai Array dapat disimpan dengan melakukan tiga cara, cara tersebut yaitu dengan : 

> Inisialisasi Array

• Contoh : 

                    int boi[5] = {0,1,3,50,69};

> Menginput nilai elemen secara langsung

• Contoh :

int i;

           for(i=0;i<10;i++)

                   scanf("%d",&boi[i]);

> Memasukkan Nilai ke Array

• Contoh : 

                  int i,boi1[10],boi2[10];

           for(i=0;i<10;i++)

               boi2[i]=boi1[i];

Operasi dalam Array

Ada beberapa operasi yang dapat dilakukan pada Array,
Operasi tersebut ialah : 
- Traversal (Penelusuran Data)
- Insertion (Pemasukan Data)
- Searching (Pencarian Data)
- Deletion (Penghapusan Data)
- Merging (Penyatuan Data)
- Sorting (Pengurutan Data)

Pointer
- Pointer adalah suatu tipe data yang nilainya mengacu pada nilai lain yang tersimpan dalam memori komputer dengan menggunakan alamatnya.
- Pointer memiliki nilai maximal sebanyak 12.

Dua operator paling penting yang digunakan dalam tipe Pointer adalah : 

> "&" -> Operator yang menunjukkan alamat("alamat dari")
> "*" -> Operator yang menunjukkan isi nilai dan variabel("isi nilai dari...")
Declaration : 

int a=20;
int *p=&a;

printf("angka = %d\n",*p);

Hasil : 
angka = 20

Data Structure
- Data Structure adalah bentuk penyusunan data yang berada di dalam memori komputer atau memori HDD.

Tipe-tipe Data Structure :

- Arrays
  > Kumpulan elemen data yang mirip.
  > Elemen data memiliki tipe data yang sama.

- Linked Lists
  > Data Structure yang dinamis dikarenakan tiap elemen yang ada dapat             ditambahkan atau dihapuskan dari manapun.
  > Tiap elemen yang ada dalam Linked Lists dipanggil dengan Node.


- Queues
  > Elemen yang dimasukkan pertama akan dikeluarkan pertama juga, Struktur       dibentuk sesuai urutan pemasukan data.
  > Elemen dimasukkan pada ujung akhir(Rear) dan dikeluarkan lewat ujung           depan(Front).
  > Istilah FIFO(First In First Out) bermaksud pertama masuk keluar pertama.


- Stacks
  > Stacks dapat dipanggil dengan Array Linear.
  > Tiap stack memiliki variable TOP di dalamnya.
  > Struktur ini berjalan sebaliknya dari Queues, dimana yang pertama masuk         akan dikeluarkan terakhir dan yang terakhir masuk dikeluarkan pertama.
  > Stacks memiliki istilah LIFO(Last In First Out) dan FILO(First In Last Out)           LIFO bermaksud terakhir masuk keluar pertama dan FILO bermaksud                 sebaliknya.


- Binary Trees
  > Data Structure yang terbentuk dari kumpulan elemen yang dipanngil               nodes.
  > Tiap node memiliki pointer kiri, pointer kanan, dan sebuah elemen data.


- Hash tables
  > Hash table merupakan salah satu struktur data yang digunakan dalam               penyimpanan data sementara.
  > Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang         dibutuhkan untuk penambahan data (insertions), penghapusan data                   (deletions), dan pencarian data (searching) relatif sama dibanding struktur         data atau algoritma yang lain.


Data Type
- Data Type atau tipe data adalah sekumpulan objek dan sekumpulan operasi  yang yang beraksi pada objek - objek tersebut. 

Contohnya, tipe data int terbentuk dengan : 

• Objek : 0,+1,-1,+2,-2, dll
• Operasi : +,-,/,*,%, dll

Abstract Data Type
ADT atau Abstact Data Type merupakan tipe data yang disusun dengan cara seperti ini: spesifikasi dari object dan spesifikasi dari operasi objek dipisahkan dari perwakilan objek dan implementasi dari operasi.

Contoh ADT : 

objects : an integer x
functions:
bool is_zero() if ( x == 0 ) return TRUE else return FALSE
bool equal(y) if ( x == y ) return TRUE else return FALSE
void set(y) x = y
void add(y) x = x + y
int get () return x

Summary
- Pointer merupakan tipe data yang  nilainya menunjukkan nilai lain yang telah    tersimpan dalam memori komputer menggunakan alamatnya.
- Array merupakan kumpulan elemen data yang mirip.
- Index suatu Array dimulai dari 0.
- Data Structure merupakan bentuk penyusunan data yang berada di dalam      memori komputer atau memori HDD.
- Tipe-tipe data Structure yang digunakan adalah : Arrays, Linked list,              Queues, Stacks, Binary Tree, dan Hash Tables
- Abstract Data Type(ADT) adalah tipe data yang disusun dengan cara ini:        spesifikasi dari object dan spesifikasi dari operasi objek dipisahkan dari              perwakilan objek dan implementasi dari operasi.


Rifqi Amru Bakti-2101696973