Pertemuan 4-Introduction to Tree, Binary Tree And Expression Tree-2101706066-Muhammad Fauqhi

Introduction to Tree, Binary Tree And Expression Tree

Tree

Tree adalah kumpulan-kumpulan dari suatu nodes, bisa berupa data.

Sebagai contoh mudah tree adalah Pohon keluarga.

• Node yang paling atas adalah root.
• Garis yang menghubungkan node-node adalah edge.
• Node yang tidak memiliki children disebut leaf.
• Degree adalah total atau jumlah dari subnode.
• Height/Depth adalah maksimal degree.

1. Degree dari Tree adalah 3
2. Degree dari C adalah 2
3. Height adalah 3
4. Parent dari C adalah A
5. Children dari A adalah B,C,D (E,F,G bukan Children A, tetapi termasuk Descendant)
6. Sibling dari F adalah G (E tidak memiliki Sibling karena B hanya memiliki 1 Children)
7. Ancestor dari F adalah A,C (Ancestor adalah leluhur, jadi bukan hanya C tetapi A juga leluhur dari F)
8. Descendant dari C adalah F,G (E bukan Descendant dari C karena C tidak terhubung oleh B)

Binary Tree

Binary artinya 2, jadi dalam Binary Tree setiap nodenya memiliki paling banyak 2 Children. Children tersebut biasa dibagi menjadi Left Child dan Right Child. Node yang tidak memiliki Child disebut leaf.

Banyak tipe-tipe dari Binary Tree yaitu : Perfect Binary Tree, Complete Binary Tree, Skewed Binary Tree, dan Balanced Binary Tree.

• Perfect Binary Tree adalah Binary Tree yang mana setiap tingkatnya memiliki kedalaman yang sama.
• Complete Binary Tree adalah Binary Tree yang mana setiap tingkat, kecuali yang paling terakhir terisi penuh.
• Skewed Binary Tree adalah Binary Tree yang mana setidaknya memiliki 1 Child.
• Balanced Binary Tree adalah Binary Tree yang mana tidak ada leaf yang jauh lebih jauh dari root daripada leaf lainnya.

Expression Binary Tree

adalah Binary Tree yang mana treenya merupakan dari suatu kesatuan ekspresi dari suatu proses matematika yang dapat berupa Postfix, Infix, dan Prefix.

Prefix : * + a b / - c d e

Postfix : a b + c d - e / *

Infix : (a + b) * ((c - d) / e)

Pertemuan 3-Linked List 2-2101706066-Muhammad Fauqhi

LINKED LIST IMPLEMENTATION II

1. Stack

Stack adalah data struktur yang penting dimana suatu data disimpan dengan teratur. Contohnya seperti tumpukan piring. Dimana jika kita ingin mengambil piring tersebut tanpa ada yang terjatuh, maka kita harus mengambil dari yang paling atas.

Stack biasa juga disebut dengan LIFO(Last in First out). Apa itu? Maksudnya adalah suatu data yang terakhir masuk akan dihapus/dihilangkan terlebih dahulu.

Ada 3 Operasi yang dilakukan pada Stack. Yaitu: Push, Pop, dan Top.

1. Push

Menambahkan data diatas stack tersebut.

2. Pop

Menghapus data dari atas dari stack tersebut.

3. Top

Mengembalikan atau mengambil data dari stack tersebut.

a. Infix, Postfix, dan Prefix

Pada umumnya kita biasa melihat operasi berikut ini :

4 - 5 + 7 * (2 + 10) / 6

Ini adalah contoh Infix.

Pada dasarnya komputer tidak mengenal komputasi Infix dan lebih mengenal Prefix maupun Postfix. Karena dalam notasi tersebut tidak memerlukan pemisah untuk menentukan bagian mana yang harus dikomputasi lebih dulu. Selain itu, notasi Prefix dan Postfix juga memiliki kompleksitas yang lebih kecil dibandingkan Infix, sehingga mempercepat proses pada saat di komputer.

Postfix : LEFT OPERAND RIGHT OPERAND OPERATOR

Prefix : OPERATOR LEFT OPERAND RIGHT OPERAND

b. Depth First Search (DFS)

adalah algoritma untuk melintasi atau mencari di pohon atau grafik yang kita mulai dari akar pohon dan kemudian mencari sampai ke cabang paling dalam pada cabang tersebut sebelum kembali untuk masuk ke cabang berikutnya.

Urutan untuk DFS diatas adalah : A,C,B,E,D

2. Queue

adalah data struktur dimana data tersebut disimpan dengan teratur. Contohnya seperti orang yang sedang mengantri. Dimana jika orang yang sedang mengantri suatu antrian contohnya mengambil uang di atm. Yang mana orang pertama mengambil uang terlebih dahulu akan selesai atau keluar terlebih dahulu. Konsep ini biasa disebut FIFO (First in First Out).

Beberapa konsep yang digunakan Queue ini. Ada Circular Queue, Deques, Priority Queue, dan Breadth First Search. Kita akan membahasnya satu persatu.

a. Circular Queue

Konsep ini digunakan jika posisi data telah mencapai batas atau full, sedangkan kita masih ingin menambah data dan pada head atau data awal tidak memiliki data. Maka kita dapat mengakalinya dengan membuat index kembali keawal sehingga menjadi Circular.

b. Deques

Deques adalah queue dimana data dapat diinput dan dihapus dari depan atau belakang. Deque dibagi menjadi dua yaitu input restricted  dimana input hanya bisa dilakukan disalah satu ujung, sedangkan delete dapat dilakukan dikedua ujung dan  output restricted dimana delete hanya dapat dilakukan disalah satu ujung, sedangkan input dapat dilakukan dikedua ujungnya.

c. Priority Queue

Priority queue adalah queue yang memiliki skala prioritas dimana yang memiliki skala prioritas paling tinggi maka didahulukan pengerjaannya.

d. Breadth First Search

(BFS) sama seperti DFS juga merupakan algoritma untuk melintasi atau mencari di pohon atau grafik. Kita mulai dari akar pohon (atau beberapa simpul acak di grafik) dan jelajahi semua level node tetangga per level sampai kita menemukan tujuannya.

Pertemuan 2-Linked List 1-2101706066-Muhammad Fauqhi

LINKED LIST 1

Pengantar Kita sudah pelajari bahwa sebuah array adalah kumpulan dari suatu data yang sama elemennya dimana unsur-unsurnya disimpan pada lokasi memori yang berurutan. Saat mendeklarasikan array kita harus membatasi jumlah elemen yang disimpan array tersebut. Tetapi, bagaimana jika kita tidak yakin dengan jumlah elemen sebelumnya? Memudahkan penggunaan memori, elemen harus disimpan secara acak di lokasi manapun dan bukan di lokasi berturut-turut. Jadi, harus ada struktur data yang menghilangkan batasan pada jumlah elemen maksimum dan kondisi penyimpanan agar program lebih efisien.


Pengenalan pada Link List Link list adalah struktur data yang menghilangkan batasan tersebut. Daftar yang terhubung tidak menyimpan elemen-elemennya di lokasi yang berturut-turut dan pengguna dapat menambahkan sejumlah elemen kedalamnya. Namun tidak seperti array, linked list tidak memungkinkan untuk mengakses data secara acak. Elemen dalam linked list hanya dapat diakses secara berurutan. Tapi sebuah array, penyisipan dan penghapusan dapat dilakukan pada setiap titik dalam daftar waktu yang konstan.


Istilah Dasar Link List Sebuah linked list, secara sederhana, adalah koleksi elemen data yang linier. Elemen data ini disebut node. Linked list adalah struktur data yang pada gilirannya dapat digunakan untuk mengimplementasikan struktur data lainnya. Sebuah linked list dapat dianggap sebagai kereta atau urutan node dimana masing-masing node berisi satu atau lebih field data dan pointer ke node berikutnya.

Gambar 2.1

Pada Gambar 2.1, kita bisa lihat bahwa setipa node linked list itu terdiri dari dua bagian, yang pertama adalah tipe data integer dan yang kedua ada pointer untuk ke node berikutnya. Bagian kiri dari node bisa berisi apa saja, contohnya array, atau struct. Dan yang bagian kanan adalah untuk pointer ke node berikutnya. Node terakhir tidak memiliki pointer atau tidak ada lagi node berikutnya. Node terakhir biasa disebut juga NULL.

Pada bahasa C, kita dapat implementasikan linked list sebagai berikut:

               struct node 
               { 
                   int data;
                   struct node *next;  
               };


Melintas Linked List Mengkases node dari link list melakukan beberapa pemrosesan pada link lists. Sebuah linked list selalu berisi variabel pointer START yang menyimpan alamat node pertama dari linked list. Akhir dari linked list ditandai dengan menyimpan NULL atau -1 pada node terakhir. Untuk melintasi linked list, kita memerlukan variabel pointer lain disebut PTR dimana yang menunjukkan ke node yang saat ini sedang diakses. Contoh Algoritma melintas linked list: 

Step 1: [INITIALIZE] SET PTR = START 
Step 2: Repeat Steps 3 and 4 while PTR != NULL 
Step 3:                   Apply Process to PTR -> DATA 
Step 4:                   SET PTR = PTR -> NEXT 
             [END OF LOOP] 
Step 5: EXIT


Mencari Nilai pada Linked List Mencari nilai pada linked list berarti mencari unsur elemen didalam linked list tersebut. Jadi pencarian pada linked list apakah ada  nilai tertentu di bagian informasi dari node atau tidak. Jika ada, algoritma mengembalikan alamat dari node yang berisi nilai tersebut. Contoh Algoritmanya:

Step 1: [INITIALIZE] SET PTR = START 
Step 2: Repeat Step 3 while PTR != NULL 
Step 3:       IF VAL = PTR -> DATA 
                           SET POS = PTR 
                           Go To Step 5 
                  ELSE 
                           SET PTR = PTR -> NEXT 
                  [END OF IF] 
            [END OF LOOP] 
Step 4: SET POS = NULL 
Step 5: EXIT


Memasukkan Nilai pada Linked List Dalam memasukkan nilai pada Linked List ada beberapa kasus. Yaitu : Memasukkan node baru dari awal, Memasukkan node baru dari belakang. Sebenarnya ada kasus lainnya tetapi kali ini hanya dua kasus yang dibahas. Langsung saja ke algoritmanya.

Step 1: IF AVAIL = NULL 
                   Write OVERFLOW 
                   Go to Step 7 
            [END OF IF] 
Step 2: SET NEW_NODE = AVAIL 
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL 
Step 5: SET NEW_NODE -> NEXT = START 
Step 6: SET START = NEW_NODE 
Step 7: EXIT

Algoritma ini untuk memasukkan node baru dari awal.

Step 1: IF AVAIL = NULL 
                   Write OVERFLOW 
                   Go to Step 10 
            [END OF IF] 
Step 2: SET NEW_NODE = AVAIL 
Step 3: SET AVAIL = AVAIL -> NEXT 
Step 4: SET NEW_NODE -> DATA = VAL 
Step 5: SET NEW_NODE -> DATA = NULL 
Step 6: SET PTR = START 
Step 7: Repeat Step 8 while PTR -> NEXT != NULL 
Step 8:         SET PTR = PTR -> NEXT 
         [END OF LOOP] 
Step 9: SET PTR NEXT = NEW_NODE
Step 10: EXIT

Algoritma ini untuk memasukkan nodebaru dari akhir.


Menghapus Nilai dari Linked List Ketika kita ingin menghapus sebuah nilai atau node dari awal linked list, maka perubahan berikut akan dilakukan di linked list. Algoritma untuk menghapus nilai dari node pertama:

Step 1: IF START = NULL 
                   Write UNDERFLOW 
                   Go to Step 5 
            [END OF IF] 
Step 2: SET PTR = START 
Step 3: SET START = START -> NEXT 
Step 4: FREE PTR 
Step 5: EXIT

Perbedaan Konsep Single Linked List, Circular, Dan Double Linked List Double Linked list memiliki 2 penunjuk arah yang biasa di inisialisasikan next dan prev. Untuk Circular Linked list, node yang terakhir berisi pointer ke node yang pertama atau Head. Jadi Circular tidak memiliki nilai NULL.

Pertemuan 1-Pointer, Array, and Introduction to Data Structure-2101706066-Muhammad Fauqhi

Pointer, Array, and Introduction to Data Structure

Sub Topics

• Array Review
• Pointer Review
• Types of Data Structure
• Abstract Data Type

Array

• Array adalah kumpulan dari suatu data yang sama elementnya
• Array memiliki tipe data yang mired atau homogenous
• Element dari array ini disimpan pada memori dan diakses dengan memanggil index element tersebut
• Index array dimulai dari 0

Menyimpan nilai index dan memanggil pada Array

• Inisialisasi

Deklarasi : 

int array[5] = {0,1,2,3,4,5,6};

Memanggil array :

array[2] = 3;

array[0] = 1;

• Menginput Nilai

int array[10];

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

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

}

• Menetapkan sebuah Nilai

int array1[10];array2[10];

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

   array2[i] = array1[i];

}

Array juga bisa memiliki 2 atau lebih dimensi. 

Contohnya : 

int array[10][10];

Maksud dari deklarasi diatas adalah setiap index dari 1-10 diisi oleh 10 data setiap indexnya.

Pointer

adalah tipe data dimana nilai tersebut terpacu kepada nilai yang lain didalam komputer dengan mengakses alamatnya.

• & adalah untuk alamat pointer
• * nilai dari pointernya

Contoh : 

int x=10;

int *a = &x;

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

Output dari program ini adalah alamat dari x.

Untuk double pointer itu bisa. Maksudnya adalah pointer didalam pointer.

Data Structure

• Array
• Linked Lists

Struktur data yang dinamis, dimana element tersebut bisa ditambahkan atau dihapus darimanapun.

• Queues

First in First out.

Contoh : Antrian makanan, antrian ATM, dsb.

• Stacks

Last in First out.

Contoh : Tumpukan piring. Diambil dari paling atas

• Binary Trees
• Hash Tables

Abstract Data Type
dapat didefinisikan sebagai model matematika dari objek data yang menyempurnakan tipe data dengan cara mengaitkannya dengan fungsi-fungsi yang beroprasi pada data yang bersangkutan.