People Innovation Excellence

Implementasi Delete pada Binary Search Tree

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.

 

 


Published at :
Written By
Ferdinand Ariandy Luwinda, S.Kom., M.T.I
Subject Content Coordinator Basic Programming | School of Computer Science

Periksa Browser Anda

Check Your Browser

Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

We're Moving Forward.

This Site Is No Longer Supporting Out-of Date Browser.

If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

Best viewed with one of these browser instead. It is totally free.

  1. Google Chrome
  2. Mozilla Firefox
  3. Opera
  4. Internet Explorer 9
Close