BINARY SEARCH TREES

Dalam binary search tree, semua node di bagian kiri sub-tree mempunyai value lebih kecil dari root node. Untuk semua node di bagian kanan sub-tree mempunya value sama/lebih besar dari root node. Karena node di binary search tree sudah tersusun, makan waktu untuk mencari elemen dalam tree berkurang, tidak perlu lagi mentraverse seluruh tree.

Ada beberapa operasi yang dimiliki oleh Binary Search Tree.

Searching

Fungsi ini digunakan untuk mencari apakah value terdapat dalam tree/tidak. Fungsi ini dimulai dari root node. Awalnya akan dicek apakah binary search tree kosong, jika tidak maka dilanjutkan pengecekan apakah value terdapat dalam tree. Untuk contoh pencarian lebih dalamnya,

Untuk mencari angka 19, dalam perbandingan jika angka 19 dengan curr node lebih besar maka kunjungi kanan, jika lebih kecil makan kunjungi kiri. Mulai membanding dari root angka 30, 19<30 maka lanjut ke kiri. Lalu, 19>15 maka lanjut ke kanan. Setelah itu, 19<26 maka lanjut ke kiri. Terakhir 19=19, ketemulah angka 19 dalam binary search tree.

Inserting

Fungsi insert digunakan untuk menambah node ke dalam binary search tree dalam posisi yang benar. Pertama, cek apakah curr node NULL, jika ia maka tinggal ditambahkan, jika tidak maka lihat value curr node lalu recurs ke bawah kiri/kanan sub-tree. Jika curr node lebih kecil dari new node, maka kanan sub-tree ditraversed, sebaliknya kiri sub-tree yang ditraversed. Fungsi insert terus berjalan turun level binary tree sampai leaf node.

Untuk menginput angka 2, dicek dari root node. 2<4 maka ke kiri. 2>1 maka ke kanan. 2<3 maka ke kiri.

Deleting

Fungsi delete adalah untuk menghapus node dalam binary search tree. Untuk menghapus node yang tidak memiliki anak, sangat gampang tinggal dihilangkan saja. Untuk menghapus node yang memiliki 1 anak, hapus node lalu sambungkan dengan parent nya. Untuk menghapus node yang memiliki 2 anak, cari node yang value nya paling besar untuk digantikan dengan parent, lalu hapus node dari tempat sebelumnya.