Pada artikel sebelumnya, saya sudah membahas mengenai insert pada Binary Search Tree. Pada artikel kali ini, saya akan membahas mengenai cara menghapus sebuah node di dalam Binary Search Tree.

Pada tahap pertama, saya akan membuat sebuah fungsi search, seperti di bawah ini :

Fungsi di atas berfungsi untuk mencari sebuah node dengan nilai tertentu. Kemudian fungsi ini akan mengembalikan nilai berupa node yang ditemukan atau NULL jika nilai yang dicari tidak ditemukan.

Contoh pada gambar tree di atas, jika kita mencari angka 14, makan fungsi search akan mengembalikan node (struct tree*). Setelah fungsi search dibuat, berikutnya kita membuat fungsi pop seperti berikut ini:

Pada fungsi ini, kita memanggil fungsi search yang sudah dibuat sebelumnya. Artinya kita sudah mendapatkan lokasi dimana node tersebut. Setelah itu kita tinggal melakukan cek pada node tersebut. Jika node tidak NULL, maka kita akan menghapus node tersebut dengan fungsi rekursif. Hal ini diperlukan untuk mencari pengganti dari node yang sudah dihapus.

Berikut adalah tahapan dalam membuat fungsi popRecursive.

  1. Pertama hal yang harus di cek adalah kondisi dimana sebuah node tidak memiliki child sama sekali. Node seperti ini bisa terjadi Karena 2 kemungkinan, yaitu node tersebut adalah root yang belum memiliki anak atau node tersebut adalah node yang berada di paling bawah dari sebuah tree. Berikut adalah code nya :

    Pada code di atas, kita melakukan cek jika node tersebut adalah root, maka kita tinggal hapus saja, tetapi jika node tersebut bukan root, kita harus setting anak kiri / anak kanan dari parentnya.

  1. Kondisi kedua adalah jika node yang mau dihapus, tidak memiliki anak kanan (hanya ada anak kirinya saja).

  1. Kondisi ketiga adalah jika node yang mau dihapus tidak memiliki anak kiri (hanya ada anak kanannya saja).

  1. Kondisi terakhir adalah jika node memiliki anak kiri dan kanan, maka node akan digantikan oleh anak kiri yang memiliki nilai paling besar, kemudian node yang menggantikan akan dihapus lagi, sehingga kita perlu memanggil popRecursive sekali lagi. Berikut adalah codenya :

Dilihat dari coding di atas, kita menjumpai banyak code seperti ini :

code di atas berarti kita mengecek apakah node ini merupakan anak kiri atau anak kanan dari parentnya. Jika node tersebut merupakan anak kiri, maka kita perlu mengatur pointer left dari parent, jika node yang mau dihapus merupakan anak kanan, maka kita perlu mengatur pointer right dari parent.

Semua code di atas berlaku untuk tree yang memiliki parent. Jika kita menghilangkan node parent, artinya tree hanya memiliki left dan right, maka kita tidak perlu mengatur hubungan parentnya.