5 - Tree dan Binary Search Tree - Kelvin Ricadson - 2101691101

TREE DAN BINARY SEARCH TREE

TREE

Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).

                                                

BINARY SEARCH TREE

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child. Binary tree juga bisa diartikan dimana tree memiliki maximum 2 children / subtree untuk setiap node. Tujuan Binary Tree adalah untuk mengurutkan value, supaya mempermudah dalam pencarian value.

Method Binary Search Tree :

1.     Pertama kita harus memilih roof.

2.     Jika nilai berikutnyaa kurang dari roof maka kita tambahkan di sub sub pohon kiri.

3.     Habisi itu kita harus menulis atau mencetaknya.

Operasi dari Binary Search Tree :

1.     Find(x) : untuk mencari.

2.     Insert(x) : untuk push / menambah.

3.     Remove(x) : untuk menghapus.

                                                  

POHON CARI BINAR

Pohon cari biner adalah pohon biner yang dirancang untuk menskemakan urutan data yang akan dimasukkan ke dalam memori agar proses pencarian, penghapusan dan penambahan data dapat berjalan secara efisien dibanding dengan pemasukan data secara array maupun link.

Sifat dari skema pohon cari biner adalah : (1) setiap elemen yang berada di left substreesselalu lebih kecil dari elemen yang ada di right substrees, (2) setiap elemen yang berada di right substrees selalu lebih besar atau sama dengan elemen yang berada di left substrees.

Ada juga 3 jenis cara untuk melakukan penelusuran data(Traversal) pada BST :

1.     PreOrder : Print data, telusur kekiri, telusur ke kanan.

2.     InOrder : Telusur kekiri, print data, telusur ke kanan.

3.     PostOrder : Telusur kekiri, telusur ke kanan, print data.

Contoh : diketahui sekumpulan elemen sebagai berikut :

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

Pembentukan awal skema pohon binernya berturut-turut sebagai berikut :

                                              

dan, hasil akhirnya sebagai berikut :

                                          

4-Introduction to Tree, Binary Tree and Expression Tree-Kelvin Ricadson-2101691101

TREE

Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

1. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
2. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
3. Parent : predecssor satu level di atas suatu node.
4. Child : successor satu level di bawah suatu node.
5. Sibling : node-node yang memiliki parent yang sama dengan suatu node.
6. Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
7. Height : banyaknya tingkatan/level dalam suatu tree.
8. Degree : banyaknya child yang dimiliki suatu node

BINARY TREE

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

                                                       

PERFECT binary tree adalah pohon biner dimana setiap tingkat berada pada kedalaman yang sama.

                                               

COMPLETE binary tree adalah pohon biner dimana setiap tingkat,kecuali yang terakhir, terisi penuh,    dan semua simpul sejauh mungkin tertinggal.

                                       

SKEWED binary tree adalah pohon biner dimana masing – masing node memiliki paling banyak satu anak.

                                         

BALANCE binary tree adalah pohon biner dimana tidak ada daun yang jauh dari akar daripada daun. 

                                             

Property of Binary Tree

Untuk menghitung tinggi maximum (maksimal) dari tree dengan menggunakan rumus sebagai berikut  : 2^h+1 - 1. 

                                     

Representation of Binary Tree

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

                            

Prefix Traversal

Melakukan awalan atau postfix traversal di pohon ekspresi sederhana.

kekosongan awalan (struct tnode * curr) {
printf ("% c", curr-> chr);
if (curr-> left! = 0) awalan (curr-> left);
jika (curr-> right! = 0) awalan (curr-> right) ;?}
Dalam awalan, Anda harus mencetak / memproses sebelum anaknya diproses.

Postfix Traversal

void postfix(struct tnode *curr) {

               if ( curr->left  != 0 ) postfix(curr->left);

               if ( curr->right != 0 ) postfix(curr->right);
               printf( “%c“, curr->chr );

}

Dalam postfix, Anda harus mencetak/memproses setelah anaknya diproses.

Infix Traversal

void infix(struct tnode *curr) {

               if ( curr->left  != 0 ) infix(curr->left);

               printf( “%c“, curr->chr );

               if ( curr->right != 0 ) infix(curr->right);
}

Tampaknya benar, tetapi infix mungkin memiliki ambiguitas didahului operator tanpa tanda kurung.

Misalnya * + a b c dalam awalan akan dikodekan dalam infiks sebagai + b * c dengan kode sebelumnya, sedangkan infiks yang benar adalah (a + b) * c.
a + b * c: b dikalikan dengan c dan kemudian ditambahkan oleh a
(a + b) * c: a ditambahkan oleh b dan kemudian dikalikan dengan c

Prefix                    : *+abc

Postfix                  : ab+c*

Wrong infix         : a+b*c

Correct infix        : (a+b)*c

                                      

3 - Linked List Implementation 2 - Kelvin Ricadson - 2101691101

Stack

Pengertian Stack pada struktur data adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Stack pada struktur data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak.

Stack bersifat LIFO (Last In First Out) artinya Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack

Operasi-operasi yang biasanya terdapat pada Stack yaitu :

1.      Push  : digunakan untuk menambah item pada stack pada tumpukan paling atas.

2.      Pop    : digunakan untuk mengambil item pada stack pada tumpukan paling atas.

3.      Clear  : digunakan untuk mengosongkan stack.

Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS). Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack. Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.

                                                                          

Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack.

Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.

                                                              

Array Representation

Stack memiliki dua variabel:
TOP yang digunakan untuk menyimpan alamat elemen paling atas dari stack
MAX yang digunakan untuk menyimpan jumlah maksimum elemen yang dapat disimpan stack
Jika TOP = NULL, maka menunjukkan bahwa stack kosong
Jika TOP = MAX - 1, maka stack sudah penuh

Linked Array Representation

Teknik membuat stack menggunakan array lebih mudah, namun kekurangannya adalah array harus dinyatakan memiliki beberapa ukuran tetap. Dalam sebuah linked stack, setiap node memiliki dua bagian : Yang menyimpan dataSalah satu yang menyimpan alamat simpul berikutnya. Petunjuk START dari linked list digunakan sebagai TOP Semua penyisipan dan penghapusan dilakukan pada simpul yang ditunjukkan oleh TOP .Jika TOP = NULL, maka itu menunjukkan bahwa stack kosong

Infix, Postfix, and Prefix Notation

Notasi Postfix  diberikan oleh Jan Lukasiewicz yang adalah seorang Polandia ahli logika, matematikawan, dan filsuf. Tujuannya adalah untuk berkembang. Notasi awalan bebas tanda kurung (juga dikenal sebagai notasi polandia) dan notasi postfix yang lebih dikenal dengan Reverse Polish

Ada 3 notasi aritmatika :

1.      Prefix notation

Prefix à Operator ditulis sebelum operan.

Contoh dari Prefix , yaitu :

* 4 10

+ 5 * 3 4

+ 4 / * 6 – 5 2 3

2.      Infix notation

Infix à Operator ditulis antara operan.

Contoh dari Infix , yaitu :

4 * 10

5 + 3 * 4

4 + 6 * (5 – 2) / 3

3.      Postfix notation

Postfix à Operator ditulis setelah operan.

4 10 *

5 3 4 * +

4 6 5 2 – * 3 /  +

Contoh :

1. Ubahlah 1/ (2 * 3 - 5) menjadi Prefix and Postfix notation

Prefix : 1 / (2 * 3 - 5 ) -> 1 / (* 2 3 - 5 ) -> 1 / ( - * 2 3 5 ) -> / 1 - * 2 3 5

Postfix : 1 / ( 2 * 3 – 5 ) -> 1 / ( 2 3 *- 5 ) -> 1 / ( 2 3 * 5 - ) -> 1 2 3 * 5 - /

Depth First Search ( DFS )

DFS adalah algoritma untuk mencari di pohon atau grafik.

Pencarian menggunakan DFS adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan kenode paling dalam lainnya yang masih memiliki successor yang belum di ekspansi.

Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. DFS dapat diimplementasikan dengan fungsi rekursif atau iteratif.

                                                  

Breadth First Search (BFS)

BFS adalah sebuah algoritma pencarian solusi yang digambarkan dengan struktur pohon. Dimana penyelesaiannya dilakukan dimulai dari simpul akar kemudian melebar sesuai dengan tingkatan yang ada didalam pohon.

Algoritma BFS :

1     Masukkan simpul ujung (akar) ke dalam antrian

2.    Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi

3.    Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4.   Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian

5.   Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

6.    Ulangi pencarian dari langkah kedua.

                                       

Queue

Queue merupakan kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang ( tail ) dan penghapusan data hanya melalui sisi depan ( head ). Berbeda dengan stack yang bersifat LIFO ( Last In First Out ), maka queue bersifat FIFO ( First In First Out ), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.

Linked List Representation

Mirip dengan stack, teknik membuat antrian menggunakan array itu mudah, namun kelemahannya adalah bahwa array memilik beberapa ukuran tetap.

Dalam Linked queue, setiap elemen memiliki 2 elemen :

1.     Satu untuk menyimpan data

2.     Satu untuk menyimpan alamat elemen berikutnya

Petunjuk start dari linked list digunakan sebagai FRONT.

Semua penyisipan akan dilakukan di REAR, dan semua penghapusan dilakukan diujung DEPAN.

Jika FRONT=REAR=NULL, maka menunjukkan bahwa antrian kosong.

Operasi Queue

1.      Push(x) : menambahkan data x kebagian belakang antrian.

2.      Pop() : menghapus data dari bagian depan antrian.

3.      Front() : mengembalikan item paling depan dari antrian.

GAMBAR

Deques

Adalah antrian dimana elemennya bisa masuk dan keluar lewat kedua ujungnya (berbeda dengan queue yang hanya bisa masuk lewat ujung belakang dan keluar lewat ujung depan). Biasanya deque disajikan dengan menggunakan double linked list yang memiliki dua buah pointer yang menunjuk keposisi sebelumnya dan sesudahnya.

Ada 2 varian antrian double-ended, meliputi :

1.     Input restricted deque

Dalam sisipan deque ini bisa dilakukan hanya pada salah satu dequeue sementara penghapusan bisa dilakukan dari kedua ujungnya.

2.     Output restricted deque

Dalam penghapusan dequeue ini bisa dilakukan hanya pada salah satu dequeue sementara sisipan bisa dilakukan pada kedua ujungnya.

Priority Queue

Antrian prioritas adalah tipe data abstrak dimana masing-masing elemen diberi prioritas.

Aturan umum elemen pemrosesan antrian prioritas :

1.      Elemen dengan prioritas yang tinggi adalah proses sebelum elemen dengan prioritas yang rendah.

2.      Dua elemen dengan prioritas yang sama diproses berdasarkan First Come First Served ( FCFS ).