Pertemuan 5 - Binary Search Tree - 2101711122 - Bela Kristianti

 

Binary Search Tree (BST)

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Aturan yang harus dipenuhi untuk membangun sebuah BST adalah sebagai berikut:

·     Semua data dibagian kiri sub-tree (left child) dari node harus lebih kecil dari pada data dibagian kanan sub-tree (right child) dan parentnya (root).

·     Semua data dibagian kanan sub-tree (right child) dari node harus lebih besar dari pada data dibagian kiri sub-tree (left child) dan parentnya (root).

Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pendarian node tertentu dalam binary tree. Pada dasarnya operasi dalam Binary Search Tree

sama dengan Binary Tree biasa, kecuali pada operasi insert, update, dan delete. Berikut adalah

contoh dari Binary Search Tree dan bukan.

Binary Search Tree memiliki operasi dasar berikut :

·     Find (x): temukan node x di BST

·     Insert (x): masukkan node baru x ke BST. Ada tiga pilihan insert : root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

·     Remove (x): hapus node x dari BST

Perbedaan binary tree dengan binary search tree :

·     Binary tree hanya diperbolehkan memiliki maksimal 2 child (cabang)

·     Binary tree tidak boleh terjadi looping

·     Binary tree memiliki node yang tidak tersusun secara berurutan (random)

·     Binary search tree mempunyai root dan memiliki node yang terstruktur (terurut)

Gambar diatas merupakan BST

Gambar diatas bukan BST, karena memiliki lebih dari 2 cabang.

 

Contoh membuat BST :

Langkah 1 : Pemasukan data 10 sebagai root

Langkah 2 : Pemasukan data 12 disebelah kanan simpul 10 karena 12>10

Langkah 3 : Pemasukan data 5 disebelah kiri simpul 10 karena 5<10

Langkah 4 : Pemasukan data 4. Karena data 4 lebih kecil dari data di root yaitu 10 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri sudah ada daun dengan nilai 5 dan data 4 lebih kecil dari data 5 maka data 4 disisipkan disebelah kiri simpul 5.

Langkah 5 : Pemasukan data 20. Karena data 20 lebih besar dari data di root yaitu 10 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 12 dan karena data 20 lebih besar dari data 12 maka data 20 disisipkan disebelah kanan simpul 12.

Langkah 6 : Pemasukan data 8. Karena data 8 lebih kecil dari data di root yaitu 10 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri sudah ada simpul dengan nilai 5 dan data 8 lebih besar dari data 8 maka data 8 disisipkan disebelah kanan simpul 5.

Langkah 7 : Pemasukan data 7. Karena data 7 lebih kecil dari data di root yaitu 10 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri bukan merupakan daun yaitu simpul dengan nilai 5 dan karena data 7 lebih besar dari data 5 penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan daun dengan nilai 8, karena data 7 lebih kecil dari 8 maka data 7 disisipkan disebelah kiri simpul 8.

Langkah 8 : Pemasukan data 15. Pemasukan data 15. Karena data 15 lebih besar dari data di root yaitu 10 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan bukan merupakan daun yaitu simpul dengan nilai 12 dan karena data 15 lebih besar dari data 12 penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan daun dengan nilai 20, karena data 15 lebih kecil dari 20 maka data 15 disisipkan disebelah kiri simpul 20.

Langkah 9 : Pemasukan data 13. Pemasukan data 13. Karena data 13 lebih besar dari data di root yaitu 10 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan bukan merupakan daun yaitu simpul dengan nilai 12 dan karena data 13 lebih besar dari data 12 penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan daun dengan nilai 20, karena data 13 lebih kecil dari 20 maka penelusuran dilanjutkan kesebelah kiri data. Selanjutnya ditemukan daun dengan data 15 karena data 13 lebih kecil dari 15 maka data 13 disisipkan disebelah kiri simpul 15.