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 :