Tag Archives: binary search tree

BINARY SEARCH TREE

Binary Search Tree (BST) adalah tree yang terurut serta dapat diproses untuk pengurutan (sorting) dan pencarian (searching).

Operasi pada Binary Search Tree:

1. find(x) : untuk mencari suatu node atau data (x) pada Binary Search Tree
2. insert(x) : untuk menambahkan suatu node atau data (x) pada Binary Search Tree
3. remove(x) : untuk menghapus suatu node atau data (x) pada Binary Search Tree

_______________________________________________________________________

SEARCHING

Proses pencarian data pada Binary Search Tree:

1. Membandingkan data yang ingin dicari apakah sama dengan Root, lebih kecil dari Root atau lebih besar dari Root.
2. Jika data sama dengan Root, maka pencarian selesai dan data ditemukan. Jika data lebih kecil dari Root, maka pencarian akan bergeser ke Child kiri dari Root. Jika data lebih besar dari Root, maka pencarian akan bergeser ke Child kanan dari Root.
3. Proses pencarian terus dilakukan menggunakan konsep lebih kecil (kiri) dan lebih besar (kanan) hingga data ditemukan. Jika pencarian telah sampai di data terakhir dan ternyata data yang ingin dicari nilainya lebih besar dari data terakhir, maka return NULL. Artinya data belum ada.

Contoh pencarian data pada Binary Search Tree di atas apabila ingin dicari angka 5:

1. Bandingkan apakah angka 5 lebih kecil atau lebih besar  dari angka 9 (Root). Karena angka 5 lebih kecil dari angka 9, proses pencarian akan jalan ke child kiri.
2. Sekarang proses ada di angka 4. Bandingkan apakah angka 5 lebih kecil atau lebih besar  dari angka 4. Karena angka 5 lebih besar dari angka 4, proses pencarian akan jalan ke child kanan.
3. Sekarang proses ada di angka 6. Bandingkan apakah angka 5 lebih kecil atau lebih besar  dari angka 6. Karena angka 5 lebih kecil dari angka 6, proses pencarian akan jalan ke child kiri.
4. Sekarang proses ada di angka 5 dan data ditemukan.

_______________________________________________________________________

INSERTION

Proses penambahan data pada Binary Search Tree:

1. Bandingkan apakah data yang ingin ditambahkan lebih kecil atau lebih besar dari Root.
2. Apabila lebih kecil, proses akan berjalan ke child kiri. Apabila lebih besar, proses akan berjalan ke child kanan.
3. Proses terus dilakukan menggunakan konsep lebih kecil (kiri) dan lebih besar (kanan) hingga data terakhir. Apabila data yang ingin dicari bernilai lebih kecil dari data terakhir, maka data baru akan ditambahkan sebagai child kiri dari data terakhir. Apabila data yang ingin dicari bernilai lebih besar dari data terakhir, maka data baru akan ditambahkan sebagai child kanan dari data terakhir.

Contoh proses penambahan data pada Binary Search Tree di atas apabila data yang ingin ditambahkan adalah angka 11:

1. Bandingkan apakah angka 11 lebih kecil atau lebih besar dari angka 6 (Root).
2. Angka 11 lebih besar dari angka 6, maka proses berjalan ke child kanan.
3. Bandingkan apakah angka 11 lebih kecil atau lebih besar dari angka 10.
4. Angka 11 lebih besar dari angka 10, maka proses berjalan ke child kanan.
5. Bandingkan apakah angka 11 lebih kecil atau lebih besar dari angka 19.
6. Angka 11 lebih kecil dari angka 19. Karena angka 19 merupakan data terakhir (left child = NULL, right child = NULL), maka angka 11 ditambahkan sebagai child kiri dari angka 19.

_______________________________________________________________________

DELETION

Ada 3 kasus yang perlu diperhatikan dalam proses deletion:

1. Jika node/data yang ingin dihapus adalah leaf, maka node/data tersebut dapat langsung dihapus.
2. Jika node/data yang ingin dihapus memiliki 1 child, maka node/data tersebut akan dihapus kemudian child dari node tersebut akan dihubungkan dengan parent dari node tersebut.
3. Jika node/data yang ingin dihapus memiliki 2 children, maka cari node paling kanan dari child kiri node tersebut. Kemudian hapus node yang ingin dihapus serta gantikan posisinya dengan node paling kanan dari child kiri node tersebut.