Binary Search Tree Recursive Java Code

Binary search tree de silme işlemi başka yapılarda oldugu gibi biraz karmaşıktır.

Silme işlemi için adımlarımız

Öncelikle silinecek elemanın adresini buluruz. Sonra 4 durum karşımıza çıkar

1‐Hiçbir çocuk olmama durumu
2‐Sadece sağ çocuğu olma durumu
3‐Sadece sol çocuğu olma durumu
4‐Her iki çocuğu olma durumu

1‐Hiçbir çocuk olmama durumu

Bu durum oldukça basittir.  Algoritma, sileceğimiz eleman yani ebeveyne karşılık gelen sağ ya da solunu NULL olarak ayarlarız ve düğümü çıkarırız.

2‐Sadece sağ çocuğu olma durumu

Bu durumda silinecek sağ çocuğu bir önceki parentı yani ebeveynin sağına bağlarız.

3‐Sadece sol çocuğu olma durumu

Bu durumda silinecek sol çocuğu bir önceki parentı ebeveynin soluna bağlarız.

4‐Her iki çocuğu olma durumu

ilk önce silinecek elemanın sağındaki en küçük elemanı bulur,

sonra bulduğumuz en küçük elemanın bir önceki yani ebeveynini buluruz.

Sonra bulduğumuz sağ taraftaki en küçük eleman ile siliceğimiz elemanın yerine koyarız.

Sonra en küçük elemanı parent nesnesi ile sağdaysa sağ tarafı null yapar yoksa sol taraftaysa solunu null yapar sağdaki en küçük değeri kaldırmış oluruz. Böylece yapıyı bozmadan güzel bir şekilde sileceğimiz elemanı yerleriniz değiştirerek silmiş oluruz.

Binary Search Tree Recursive Kodları

void remove(int in) {
 Node rm = search(in);
 Node pr = searchParent(in, rm);
 if (pr == null)
  return;
 else {
  if ((rm.left == null) && (rm.right == null)) {//hiç cocugu olmayan
   if (pr.left == rm)
    pr.left = null;
   else
    pr.right = null;
  } else if ((rm.left == null) && (rm.right != null)) {//sadece sağ çocugu olan
   pr.right= rm.right;
  } else if ((rm.left != null) && (rm.right == null)) {//sadece sol çocugu olan
   pr.left = rm.left;
  } else {//iki çocugu olan..
   int a = rm.right.searchMin().id;
   Node nd = searchParent(a, rm.right.searchMin());
   rm.id = a;
   if (nd.left.id == a)
    nd.left = null;
   else
    nd.right = null;
   }
  }
 }