asd pertemuan 6

ALGORITMA DAN STRUKTUR DATA

Tree Introduction - QuizPertemuan 6 – 26/10/2015

Universitas Muhammadiyah Malang (UMM)Wildan Suharso,S.Kom,M.Kom

www.wildansuharso.com

Yang Sudah Diperoleh

• Pengantar Algoritma dan Struktur Data• Review Java (Tipe Data, Iterasi, Rekursi, Method, Class, etc)• Algoritma (natural language, flow chart, pseudocode, analisis

kompleksitas, penulisan program)• Contoh dan Penerapan Struktur Data• Searching dan sorting pada array (bubleshort, insertion sort,

selection)• Array dan Linked List• ArrayList() dan LinkList()• Tugas Algoritma, Struktur Data, ArrayList(), Linked List, Stack,

Queue

Klasifikasi Struktur Data

Struktur Data

Tree

Stack

Non Linier

Sederhana

Linier

Linked List

Graph

Queue

Struktur Data Linier

• Linier dapat dikatakan sebagai logis memiliki start dan stop

• Memiliki link pada elemen selanjutnya (next)• Memiliki link pada elemen sebelumnya

(previous)• Dapat kita ketahui pula bahwa kita dapat

mudah mengetahui organisasi dan penyimpanan

• Contoh Array, Linked Lists, Stack, Queue

Tree

• Tree bukan struktur data terbaik• Tetapi sangat cocok untuk tujuan tertentu• Misalkan organisasi dalam perusahaan• Bukanlah tipe data linier, sehingga tidak

nampak sequensial• Meski dalam pemrograman/aplikasi dapat

menggunakan linked list atau array

Klasifikasi Tree

• Tree Umum– Child 0,1,2,...., N

• Binary Tree– Selalu child 0, 1, atau 2

Bagian Tree

• Root• Parrent• Child• Sibling• Leaf

Contoh Tree

Contoh Stuktur Data Tree

Struct node {int data;Node* left;Node* right;

}

Aplikasi Tree

• Penyimpanan Manual– File System

• Organisasi Data– Insert, Delete, Search – Binary Search Tree

• Pengecekan cepat, dinamis– Kamus

• Network Routing Algorithm

Pembacaan Tree

• Simpul dalam tempat menyimpan operator• Simpul luar tempat menyimpan operand• Operand kiri menjadi anak kiri dan Operand

kanan menjadi anak kanan operatornya• Evaluasi ekspresi dilakukan mulai operator

yang mempunyai derajat kedalaman tertinggi hingga terendah

Contoh

Klasifikasi Tree

• Tree Umum• Binary Tree

Tree Secara Umum

• Tree memiliki child dan parrent• Jumlah Child dari 0,1,2,...,N• Aturan kanan dan kiri tidak diperhatikan• Aturan sempurna, hampir sempurna, dan

tidak sempurna tidak diperhatikan

Klasifikasi Tree

Struktur Data

Tree

Stack

Non Linier

Sederhana

Linier

Linked List

Graph

Queue

Binary Tree

• Merupakan struktur data khusus• Digunakan untuk pencarian cepat, insert,

delete• Pada binary tree memungkinkan pencarian

tidak sequensial• T1<R<T2

Struktur Data Binary Tree

• Struktur data binary tree dapat menggunakan tree

• Seperti tree sama dengan two way list

Fungsi BST

• Pencarian data • Menghilangkan duplikasi data • Sorting Data

Contoh BST

• Misalkan, coba insertkan satu persatu deret di bawah ini– 60, 80, 30, 50, 65, 20, 10, 90, 25

Jawab

• Data pertama sebagai root• Kemudian ikuti aturan binary search tree• T1 < R < T2

Jawab

Soal

• Buatlah pohon biner / tree– P * Q / R – S * T + U / V – A * (B – C) / (D + E) * F * G – V * (W / (X – (Y + Z))) – (2 * 3 / 2 – 7) * (9 + 5 / 3)

• Buat BST dari data di bawah ini– 30, 80, 20, 10, 100– 100, 40, 30, 20– 100, 10, 80, 20

Next Kompleksitas

• Array >>>> O(n)• Linked List >>>> O(n)• Stack >>>> O(n)• Queue >>>> O(n)• BST >>>> O(log n)