pert5 - binary search tree - 2101711791 - Malik Naufal Dwiyanto

BINARY SEARCH TREE

binary search tree adalah binary tree yg di rancang untuk menskemakan urutan data yg akan dimasukkan ke dalam memori agar proses pencarian, penghapusan dan penambahan data dapat berjalan secara efisien.

sifat dari skema binary tree adalah setiap elemen yg berada pada leftsubtrees selalu lebih kecil dari rightsubtrees.

contoh: 

diketqhui sekumpulan elemen sebagai berikut:

60, 75, 25, 50, 15, 66, 33, 44

pert4 - tree, binary tree, dan expression - 2101711791 - Malik Naufal Dwiyanto

TREE

merupakan salah satu bentuk struktur data yg tidak linear dan menggambarkan hubungan yg bersifat hierarkis astara data satu dengan yg lain. 

bisa disimpulkan bahwa tree merupakan kumpulan node dengan satu elemen khusus yg di sebut root.

contoh tree

berikut adalah istilah umum yg ada pada tree:

• preodecessor: node yg berada diatas node tertentu.
• successor: node yg brada di bawah node tertentu.
• ancestor: semua node yg terletak sebelum node tertentu terletak pada jalur yg sama.
• descendant: seluruh node tertentu yg terletak di bawah node tertentu dan ada pada satu jalur.
• parent: predecessor di atas satu node.
• child: successor satu node dibawah suatu node.
• sibling: node2 yg memiliki satu parent yg sama dengan suatu node,
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor
• Degree : banyaknya child yang dimiliki suatu node

BINARY TREE

binarry tree adalah tree dengan maksimal 2 subnode di tiap nodenya.

tipe2 binary tree:

• perfect: binary tree dengan setiap tingkatnya memiliki kedalaman yg sama.
• complete: binary tree yg dimana setiap tingkat, kecuali muhgkin yg terahir benar2 terisi.
• skewed: binary tree yg setiap nodenya paling banyak memiliki satu anak.
• balance: binary tree yg dimana tidakada leaf yg lebih jauh dari root daripada leaf lainnya.

operasi pada binary tree:

• create: membuat binary tree baru yg masih kosong.
• clear: mengosongkan binary tree yg sudah ada.
• empty: function untuk memeriksa apakah binary tree tersebut masih kosong atau tidak.
• insert: memasukkan node kedalam tree.
• find: mencari root, parent, left child atau right child dari suatu node,
• update: mengubah isi dari node yg di tunjuk oleh pointer.
• retrieve: mengetahui isi dari node yg ditunjuk oleh pointer.
• deletesub: menghapus sebuah subtree.
• characteristic: mengetahui carakteristic suatu tree.
• traverse: mengunjungi seluruh node-node pada tree, masing masing sekali.

EXPRESSION TREE 

prefix: *+abc

postfix: ab+c*

infix: (a+b)*c

yinggal di ubah sesuai aturan binary tree /  tree

pert3 - implementasi linked list 2 - 2101711791 - Malik Naufal Dwiyanto

KONSEP STACK

stack adalah salah satu konsep dari tipe data abstrack yg tersusun. pertama kali di ajukan dalam desain computer milik Alan M.Turing pada tahun 1946. stack atau tumpukan memiliki dua konsep dasar yaitu pop dan push.

Push: adalah proses menambahakan data ke atas suatu tumpukan.

Pop: mengambildata palimg atas dari tumpukan dan membuangnya.

kedua operasi inilah yg menjadi cirikhas sebuah stack sehingga stack bekerja secara LIFO (Last In Last Out). selain operasi pop dan push ada juga operasi peek yaitu melihat isi data paling atas tranpa membuangnya.

dalam dunia nyata stack biasa di umpamakan seperti tumpukan piring yang kalu kita mau menambah atau mengurangi tumpukanya harus di ambil/di taruh dari yg paling atas terlebih dahulu.

PREFIX INFIX DAN POSTFIX

prefix DKK adalah sebuah notasi yg terbentuk dari operand dan operator, opreand adalah data atau nilai yg membantu dalam proses, sedangkan operator adalah fungsi yg dgunakan dalam proses.

prefix: adalah notasi yg berbentuk operator ada di depan operand.

infix: adalah notasi dimana operator ada d tengah operand.

postfix: adalah notasi dimana operator ada setelah operand.

 DEPTH FIRST SEARCH DAN BREATH FIST SEARCH

DFS:

pencarian dilakukan pada satu node dalam setiap level dari yg aling kiri. jika pada level yg plaing dalam solusi belum ditemukan maka pencarian akan dillanjutkan pada node sebelah kanan. node yang kiri dapat dihapus dari memori.

BFS:

merupakan algoritma yg melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul tersebut terlebih dahulu. selanjutnya simpul yg belum dikunjungi yang bertetangga denagn simpul yg tadi dikunjungi demikian seterusnya.