Data Structure 5: Binary Search Tree

Binary Search Tree

Binary Search Tree adalah tree yang dibuat untuk mempermudah pencarian data dalam tree. Dimana tiap node memiliki 2 child node yaitu ‘left’ dan ‘right’. Node ‘left’ untuk data yang lebih kecil dari parent dan node ‘right’ untuk data yang lebih besar dari parent nya.

Dalam Binary Search Tree ada 3 Operasi yang dapat dilakukan, yaitu:

  1. Find / Search
    • Digunakan untuk mencari data di dalam tree.
    • Langkah-langkahnya:
      1. Mulai dari root dari tree.
      2. Jika angka yang dicari sama dengan node tersebut, maka return node tersebut.
      3. Jika data yang dicari lebih kecil dari node tersebut maka pindah pencarian ke node ‘left’.
      4. Jika data yang dicari lebih besar dari node tersebut maka pindah pencarian ke node ‘right’.
      5. Ulangi langkah 2,3 dan 4 hingga mendapatkan node yang dicari (nilai node sama dengan yang dicari).
  2. Insertion
    • Digunakan untuk memasukkan data baru ke dalam tree.
    • Langkah-langkahnya:
      1. Cek apakah ada node root. Jika belum ada maka node yang akan di insert menjadi root. Apabila ada, bandingkan data yang akan dimasukkan dengan node tersebut.
      2. Jika data yang akan di- insert lebih besar dari node tersebut, pindah ke ‘right’.
      3. Jika data yang akan di- insert lebih kecil dari node tersebut, pindah ke ‘left’.
      4. Ulangi langkah 3 dan 4 hingga node yang akan dipilih/pindah tidak ada.
      5. Cek apakah data yang akan dimasukkan lebih besar / lebih kecil dari node tersebut. Jika lebih besar, maka di insert ke node ‘right’. Sebaliknya, jika lebih kecil maka di-insert ke ‘left’.
  3. Deletion
    • Digunakan untuk mengapus node.
    • Langkah-langkahnya:
      1. Gunakan metode untuk searching untuk mencari node yang akan dihapus.
      2. Jika node yang akan dihapus tidak memiliki child, maka node tersebut dapat langsung dihapus.
      3. Jika node yang akan dihapus hanya memiliki 1 child, hubungkan node child tersebut dengan parent dari node yang akan dihapus.
      4. Jika node yang akan dihapus memiliki 2 child, sesuai dengan keadaan, node yang dihapus dapat diganti dengan node child paling kanan (right) dari node ‘left’ node yang akan dihapus atau diganti dengan sebaliknya, mengganti dengan node child paling kiri (left) dari node ‘right’ yang akan dihapus.