İkili Arama Ağacı Eleman Ekleme İşlemi

ikili arama ağacı
İkili Arama Ağaçları üzerinde eleman arama işlemini bir önceki yazımızda anlatmıştık. Bu yazımızda BST üzerine düğüm ekleme işlemini göreceğiz.



BST (Binary Search Tree) üzerinde eleman ekleme işlemi için doğru yeri bulmak önemlidir. Bunun için traverse yapmak gereklidir. Yani doğru düğümün soluna ya da sağına eleman ekleyebilmemiz için doğru düğümü bulmamız gerekiyor.

İkili arama ağacı yapısının kuralı basit, bir düğüme eklenecek olan düğümün değeri, mevcut düğümün değerinden küçükse sol çocuğu olurken, büyükse sağ çocuğu olmaktadır. (ikili arama ağaçlarında aynı değere sahip iki düğüm bulunamaz, bulunursa bu yapı ikili arama ağacı olmaz)

void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //Eger Ağaç Boşsa
   if(root == NULL){
      root = tempNode;
   }else {
      current = root;
      parent = NULL;

      while(1){                
         parent = current;
   
         //Ağacın soluna git
         if(data < parent->data){
            current = current->leftChild;                
            //sola eleman ekle
    
            if(current == NULL){
               parent->leftChild = tempNode;
               return;
            }
         }//Ağacın sağına git
         else{
            current = current->rightChild;
            //Sağına eleman ekle
            if(current == NULL){
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}
Yukarıdaki kod yapısında 3 tane düğüm oluşturduk. birinci düğüm tempNode isimli düğüm. Bu düğüm ekleyeceğimiz sayıyı tutacak. Diğer düğümler ise traverse için, current düğümü şu an tuttuğumuz düğüm, parent düğümü ise parent değerini tutan düğümdür.

Temp düğümü için alan oluşturulmuştur. temp düğümü her halükarda Leaf olacağından temp->left ve temp->right değerleri NULL yapılmıştır.

Eğer ağaç boşsa root olarak temp node atanmıştır.
Yok eğer değilse traverse işlemi için current = root, parent = NULL yapılır ve bu adımdan itibaren döngüye girilir.

her döngüde, parent değişkenine current değeri atanır. BST algoritması gereği data eğer parent-> data değerinden küçükse current = current->leftChild yapılır. Bu bir ekleme değildir, ekleme işlemi current == NULL olunca yapılır, parent->leftChild = tempNode denilerek veri eklenir.

Eğer data değeri parent->data değerinden büyükse bu sefer sağ çocuğa inilir, current = current->rightChild işlemi bir traversing işlemidir, current == NULL olduğunda ekleme yapılır. İkili arama ağacı eleman ekleme işlemi bu şekildedi.

Etiketler: , , ,