Archive for April, 2016

BINARY SEARCH TREE

Binary Search Tree (BST) adalah binary tree dimana sub tree sebelah kiri lebih kecil daripada parentnya.

Data pada BST sudah terurut sehingga mempermudah dalam proses pencarian.

Operasi-operasi dalam BST:

1. Insert

Memasukkan data ke dalam BST. Data yang dimasukkan akan menjadi leaf.

Penempatan data yang dimasukkan akan mengikuti sifat BST, jika data lebih kecil dari parent maka akan ke kiri, jika lebih besar maka akan ke kanan, seterusnya hingga menempati posisi leaf.

2. Delete

Menghapus data dalam BST.

• Jika yang dihapus tidak mempunyai anak (leaf) , maka langsung hapus data tersebut

• Jika yang dihapus mempunyai 1 anak, maka data dihapus, lalu sambungkan anak dari node yang dihapus dengan parent dari node tersebut.

• Jika yang dihapus mempunyai 2 anak, digantikan oleh data paling kiri dari subtree kanan, atau sebaliknya.

3.  Search

Digunakan untuk mencari data dalam BST.

Step-stepnya:

– Dimulai dari root

– Jika data yang dicari sama dengan node, maka pencarian berakhir.

– Jika data lebih kecil dari node, maka:

• Jika node mempunyai subtree kiri, maka lanjutkan pencarian ke subtree kiri
• Jika tidak punya subtree kiri, pencarian berakhir, pencarian gagal.

– Jika data lebih besar dari node, maka:

• Jika node mempunyai subtree kanan, maka lanjutkan pencarian ke subtree kanan
• Jika tidak punya subtree kanan, maka pencarian berakhir, pencarian gagal.

– Ulangi step diatas sampai menemukan node yang dicari.