Implementasi Insert Pada Binary Search Tree dengan Single dan Double Pointer
Binary Search Tree adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Selain itu, terdapat juga aturan dimana anak kiri dari parent selalu memiliki nilai lebih kecil dari nilai parent dan anak kanan selalu memiliki nilai lebih besar dari parent. Pada artikel ini, penulis akan membahas bagaimana cara mengimplementasikan binary search tree di dalam Bahasa C.
Pertama, kita harus mempersiapkan struct yang melambangkan setiap node. Untuk contoh sederhana, struct yang dibuat disini hanya berisi 1 buah integer. Berikut adalah contoh structnya :
Setelah struct dibuat, kita akan membuat sebuah function yang digunakan untuk membuat node baru, seperti di bawah ini :
fungsi di atas berguna untuk membuat node baru. Jadi setiap createNode dipanggil, contoh createNode(50), createNode(70), maka akan jadi seperti ini :
setelah fungsi di atas sudah siap, berikutnya kita tinggal membuat fungsi insert/push menggunakan single pointer seperti di bawah ini :
Berikut adalah penjelasan dari code di atas :
- Pada if pertama, program akan melakukan cek pada root. Jika root bernilai NULL, artinya tree belum pernah terbentuk sama sekali. Karena itu kita tinggal melakukan malloc/ pemesanan memori pada root
- Pada else if kedua, program melakukan pengecekkan terhadap nilai baru yang mau diinsert. Jika nilai baru tersebut lebih kecil daripada node sekarang dan anak kiri dari node sekarang sedang kosong, maka program akan melakukan malloc pada anak kiri tersebut dan mengarahkan pointer parent kepada node yang sekarang.
- Pada else if ketiga, program akan melakukan pengecekkan seperti pada point 2. Hanya saja jika nilai baru tersebut lebih besar dari node sekarang dan anak kanan dari node sekarang sedang kosong, maka program akan melakukan malloc pada anak kanan tersebut dan mengarahkan pointer parent kepada node sekarang.
- Pada else if keempat, program akan jalan jika nilai baru lebih kecil dari node sekarang, tetapi anak kiri dari node tersebut tidak kosong. Maka program akan melakukan rekursif, memanggil fungsi push kembali dengan parameter nodel->left, yang berarti node sekarang dipindahkan ke anak kiri dan nilai a yang mau diinput. Sehingga pada tahap ini, suatu saat program akan menemui kondisi dimana anak kiri dari node sekarang sedang kosong.
- Pada else yang terakhir, program melakukan hal yang sama seperti point 4, hanya saja nilai yang dicek kondisinya harus lebih besar dari nilai node sekarang.
Jika kita ingin menggunakan double pointer, maka fungsi insert / push, akan jadi seperti ini :
Perbedaan cara memanggil fungsi single dan double pointer adalah seperti ini :
Contoh single : push(root,50);
Contoh double : push2(&root,50);
Jika dilihat dari code di atas, code double pointer terlihat lebih pendek karena dengan menggunakan double pointer, kita bisa melakukan passing by address. Sehingga ketika kita melakukan malloc atau memanggil newNode pada fungsi push2, maka root yang aslinya akan kena malloc juga. Berbeda dengan single pointer, jika kita melakukan node = newNode(a), maka root yang asli tidak akan ikut kena malloc, Karena ini merupakan passing by value.