BINARY SEARCH TREE

Merhaba arkadaşlar,

Bu gece ki konumuz daha önce de çok yakında yazısı ile belirttiğim Binary Search Tree.

Veri yapıları çok şükür ki isimlendirilirken daha önce de bahsettiğimiz yapılar gibi mantık çerçevesinde isimlendirilmişler.. Bu yüzden şunu söylebilirim elimizde tam üç tane anahtar kelime var... İsterseniz onları şöyle bir mercek altına alalım..

Tree: Ağaç anlamına gelen bu kelime yapının bir çeşit ağaca benzediğini sanki kulağımıza fısıldıyor.. Yapımızda "root" kök ve bunun yanında "child" yani çocuk tarzı bir hiyerarşinin varlığını kestirebiliyoruz..

Search: Arama anlamına gelen bu kelime, Yapının aramalarda sanki bize yardımcı olacağı kanısına varıyoruz..(Bakalım nasıl olacak..)

Binary: İkili anlamına gelen bu kelime ağaç tarafının tamamlayıcısı gibi.. iki çocuktan oluşan bir yapının kokusunu almış olduk...

Evet yukardaki kelimeleri birleştirdiğimizde az çok kafamızda fikirler oluşmuştur...




Evet.. Yukardaki resim tipik Binary Searh Tree ... Bir adet kök ve iki çocuk ve onların yine birer veya ikişer çocukları.. Şimdi burada altını çizmemiz gereken bir iki nokta var.... Çiziyoruz tamam çizelim abi...

BİRRRRRRR!!!! Kök olsun çocuk olsun bir verinin en FAZLA İKİ ADET çocuğu olabilir...
İKİİİİ!!!!!! Çocuklardan SOL tarafdaki babasından veri olarak her zaman KÜÇÜK, SAĞ tarafda olan ise BÜYÜKTÜR...

Dilerseniz BST'nin birazda Search özelliğinden bahsedelim.. Peki niye bu ağaç yapısına arama özelliği iyi dermişcesine bu isim verilmiş? Bunun için karşılaştırma yapalım...

Örneğin, bir Linkedlist yani Bağlı Listemiz var. Burada bir veri bulmak istediğimiz bir döngü kurup tüm verileri tek tek tarıyorduk... 10 tane verimiz varsa 10 tane karşılaştırma yapmamız analamına geliyordu... Ancak Ağaç yapısının nimetleri burada ortaya çıkıyor... Basamak tarama yapmamıza izin veriyor... Bir karşılaştırma yaparak o kattaki tüm veriler kontrol edilmiş olunuyor...

Yukardaki örneği baz alırsak; "6" verisini arayalım... Önce kök de bir arama yaptık.. Eğer değer kökden küçük ise sol tarafa geçtik aksi takdirde sağ tarafda arama yapacaktık(KURAL 2 yi hatırlayalım).. Devam ediyoruz "10" ile karşılaştırdık ve tekrar sol tarafan devam ediyoruz ki "6" yı bulduk!!!!! BRAVO bize.. hemde sadece 3 aramamızda bulduk.. Bağlı Liste olsa idi 8 arama yapma ihtimalimiz vardı.. Veriler çoğaldıkça nasıl bir problem kurtulduğumuzu siz düşünün..

Siz ile şimdi güzel bir örnek yapalım... Bir adres defteri...

Verilerimiz için sınıfımız;


#ifndef DATANODE
#define DATANODE
#include
using namespace std;
class Data {
public :
string name;
string number;
Data *left;
Data *right;

Data(){ left=0; right=0; }
void setName(string ad){
name=ad;
};
string getName(){
return name;
};
string getNumber(){
return number;
};
void setNumber(string numara){
number=numara;
};





};
#endif


BURASI DA AĞAÇ YAPIMIZ




#ifndef TREENODE
#define TREENODE
#include
using namespace std;
class Tree {
public :
Data *root;

Tree() { root=0; }
void addData(Data *data){

Data *temp;
Data *prev;
if (isEmpty())
{
root=data;
}
else
{
temp=root;
while (temp!=0)
{
prev=temp;
if (compare(temp,data))

temp=temp->left;

else

temp=temp->right;

if(compare(prev,data))

prev->left=data;
else

prev->right=data;


}

}


}
bool isEmpty(){
if (root!=0)
return false;
else
return true;

}
bool compare(Data *data1,Data *data2)
{
if (data1->getName()>data2->getName())
{
return true;
}
else
{
return false;
}

}
void displayInorder(Data *data)
{

if (data!=0)
{
displayInorder(data->left);
cout<<"Name:"<getName()<<",Number:"<getNumber()<<"\n";
displayInorder(data->right);
}
}

void displayPreorder(Data *data)
{

if (data!=0)
{
cout<<"Name:"<getName()<<",Number:"<getNumber()<<"\n";
displayInorder(data->left);
displayInorder(data->right);
}
}
void displayPostorder(Data *data)
{

if (data!=0)
{
displayInorder(data->left);
displayInorder(data->right);
cout<<"Name:"<getName()<<",Number:"<getNumber()<<"\n";
}
}
void searchData(string name)
{
Data *temp;
temp=root;
int step=1;
while (name!=temp->getName())
{
step++;
if (temp->getName()>name)

temp=temp->left;
else
temp=temp->right;

}
cout<<"Found in "< cout<<"Name:"<getName()< cout<<"Number:"<getNumber()<
}
void modify(string name,string number)
{
Data *temp;
temp=root;
int step=1;
while (name!=temp->getName())
{
step++;
if (temp->getName()>name)

temp=temp->left;
else
temp=temp->right;

}
temp->setNumber(number);

}
};
#endif