Binary Search Tree

Binary Search Tree  adalah binary tree yang memenuhi syarat-syarat ini:

–Setiap node memiliki nilai yang berbeda (tidak boleh ada dua node yang memiliki nilai yang sama).

–Nilai yang dimiliki node anak sebelah kiri harus lebih kecil dari nilai root.

–Nilai yang dimiliki node anak sebelah kanan harus lebih besar dari nilai root.

Operasi-operasi pada Binary Search Tree :

• find(x)            : mencari sebuah node pada binary search tree
• insert(x)         : memasukkan sebuah node baru pada binary search tree
• remove(x)      : menghapus sebuah node pada binary search tree

1. Proses pencarian sebuah node pada BST adalah sebagai berikut:

Pencarian dimulai dari root.
Bila nilai yang dicari sama dengan root maka pencarian selesai.
Bila nilai yang dicari < dari root maka lanjutkan pencarian ke node anak sebelah kiri.
Bila nilai yang dicari > dari root maka lanjutkan pencarian ke node anak sebelah kanan.
Lanjutkan pencarian dengan cara begini hingga node yang dicari ditemukan.

2. Proses memasukkan sebuah node baru pada BST adalah sebagai berikut:

Dimulai dari root.
Bila nilai yang ingin dimasukkan < dari root maka lanjutkan ke node anak sebelah kiri.
Bila nilai yang ingin dimasukkan > dari root maka lanjutkan ke node anak sebelah kanan.
Lanjutkan dengan cara begini sampai tiba di leaf , kemudian masukkan node baru sebagai anak dari leaftersebut.

3. Untuk delete, ada 3 kasus yang bisa terjadi:

• Jika node yang mau dihapus adalah leaf, maka node tersebut dapat langsung dihapus.
• Jika node yang mau dihapus memiliki satu anak,
  hapus node tersebut lalu hubungkan anak dari node itu dengan parent node itu.

• Jika node yang mau dihapus memiliki dua anak,
  carilah anak paling kanan dari sub tree yang sebelah kiri (misalnya: node x),
  lalu gantilah node yang mau dihapus menjadi node x, kemudian hapus node x.