Bağlı liste yapısını kullandığımızda eleman aramak başarım açısından oldukça maliyetli oluyordu. N tane eleman olması durumunda teorik olarak N tane elemanı kontrol etmek durumunda kalıyorduk. Binary search tree yapısı bize arama yapma ve eleman eklemede oldukça hızlı bir çözüm sağlıyor. log2(N+1)-1 tane karşılaştırma işlemi ile sonuca ulaşabiliyoruz.

Bu çalışmada ağaç yapısını gerçeklerken elemanların indislerinin daha kolay gözlenebilmesi ve algoritma takibinin daha kolay olması için dizi gösterimi kullanıldı. Dengeli olmayan ağaçlarda dizi yapısını kullanmak hafıza alanı açısından maliyetli olabilir. Bu yüzden bu örnekler oluşturma aşamasında uygun sıra ile dengeli olarak yerleştirildi. Ancak kullandığımız yapı self-balancing olmadığından zaman içerisinde yapılacak modifikasyonların bu dengeyi bozması olasıdır. Ayrıca elemanları sıralamak da bize ek işlem yükü getiriyor.

Daha geniş kapsamlı uygulamalarda struct yapısı kullanılarak işaretçiler yardımıyla yapılacak bir gerçekleme hafıza alanını daha etkili kullanma adına daha mantıklı olacaktır. Eğer bizim için en önemli ölçüt arama hızı ise self balancing tree yapısı alternatif olarak düşünülebilir.

Akış Diyagramları:

Kaynak Kodlar:

#include <stdio.h>
#include <stdlib.h>
#define isNull -99
#define size 200

void insert2tree(int tree[],int z)
{
     int i=1;
     int x=tree[i];

     while(x!=isNull){
                      if(z<x) i=2*i;
                      else i=2*i+1;

                      x=tree[i];
                      }
     tree[i]=z;
}

int searchTree(int tree[],int i,int key)
{
     if(tree[i]==isNull)
     return isNull;

     else if(tree[i]==key)
     return i;

     else if(key<tree[i])
     return searchTree(tree,i*2,key);
     else
     return searchTree(tree,i*2+1,key);
}

void balancedInsert(int tree[],int values[],int low,int hi){
     if(hi<low) return;
     int middle=(hi+low)/2;
     insert2tree(tree,values[middle]);
     balancedInsert(tree,values,low,middle-1);
     balancedInsert(tree,values,middle+1,hi);
     }

void buildTree(int tree[],int values[],int numOfElements)
{
     int i,j,temp;
     for(i=0;i<size;i++)
     tree[i]=isNull;

     for(j=0;j<numOfElements-1;j++)
     for(i=0;i<numOfElements-1;i++)
     if(values[i]>values[i+1]){
                               temp=values[i];
                               values[i]=values[i+1];
                               values[i+1]=temp;
                               }

     balancedInsert(tree,values,0,numOfElements-1);
}

void printTree(int tree[],int i)
{
     if(tree[i]!=isNull){
                            printf("Value: %d, Index: %d\n",tree[i],i);
                            printTree(tree,i*2);
                            printTree(tree,i*2+1);
                            }

}

int main()
{
    int tree[size],values[size],i,choice,z,numOfElements;
    printf("Enter of number of elements: ");
    scanf("%d",&numOfElements);

    for(i=0;i<numOfElements;i++)
    scanf("%d",&values[i]);

    buildTree(tree,values,numOfElements);

    while(1)
    {
    printf("<<MENU>>\n1.Insert New Node\n2.Search\n3.Print Tree\n4.Exit");
    scanf("%d",&choice);

    switch(choice){
                   case 1:
                        printf("\nElement: "); scanf("%d",&z);
                        insert2tree(tree,z);
                        break;
                   case 2:
                        printf("\nElement: "); scanf("%d",&z);
                        i=searchTree(tree,1,z);
                        if(i==isNull) printf("\nNot Found\n");
                        else printf("\nFound on index: %d\n",i);
                        break;
                   case 3:
                        printTree(tree,1);
                        break;
                   case 4:
                        return 0;
                   }
    }
}