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.