Yukarı ifadeye baktığımızda sağa dönüş işlemi görüyoruz. Peki ne oluyor? y nodu z'nin yerine geçiyor, z ise t4'ün yerine geçiyor. aynı şekilde x y'nin yerine geçiyor. Yani y root olurken x ve z onun çocukları oluyor. Leaf'ler yani yapraklar ise x ve y'nin çocukları oluyor. Temelde, y'nin derinliği bir azalıyor, x'in ve t3'ün derinliği bir azalıyor, t1 ve t2'nin derinlikleri bir azalıyor. Buna karşın z'nin derinliği bir artıyor. Yani dengeleme işlemi bu şekilde gerçekleşiyor.
Eğer ağaç yapımızı bir struct içersinde tutsak;
struct agac{
int deger;
struct node *solCocuk;
struct node *sagCocuk;
int yukseklik;
}
bu şekilde oluşturabilirdik. Yani her node (düğüm) için bir tane agac struct'ı create eder bilgilerini verirdik. Ama biz şimdi agac oluşturmakla uğraşmayalım. Varmış gibi yapalım. Maksat temel algoritmayı görmek.
struct node *leftRotate(struct node *y)
bu yukarıdaki ifade de bir fonksiyondur. parametre olarak struct göndereceğimi için bu şekilde oluşturduk. yani biz hangi düğümü döndüreceksek o structı parametre olarak gönderiyoruz.
Şimdi yapacağımız işlem temelde swap işlemi.
Swap nedir diye soruyorsanız ilgili yazımıza bakabilirsiniz?
Yukarıdaki şekle bakın, x'in sağında y, y'nin solunda ise T2 var, swap işlemi aynı bu mantıkta yapılıyor.
ohalde şöyle yapalım.
struct node *leftRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
}
yukarıda kırmızı renkli satırlarda
x ve
T2 adında 2 tane düğüm oluşturduk. x düğümüne y düğümünün sol çocuğunu atadık. T2 düğümüne de x düğümüne de x düğümünün sağ çocuğunu atadık. Bunlar elimizde tuttuğumuz değerler. Henüz swap yapmadık.
struct node *leftRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
x->right = y;
y->left = T2;
}
Kırmızı yazıyla yazılmış satırlara baktığımızda x->right (yani x düğümünün sağ çocuğu) değerine y düğümünü attık. Bakın döndürme işlemi aslında bu satırda yapıldı. y->left değişkenine ise T2 structında tuttuğumuz değeri atadık. (eski x->right değeri yani). Bu satırlarda ilişkiler yapılandırılmış oldu. Ancak bir eksik var. O da yükseklikler. Biz döndürmeyi yapısal olarak yaptık, ancak eğer yükseklikleri güncellemezsek ağaç yapımız yine bozuk olacak.
Şimdi bize iki fonksiyon lazım. Bir tanesi sol taraf daha derinse sol tarafı, sağ taraf daha derinse sağ tarafı döndürsün. Çok basit bir fonksiyon yazıyorum.
int HangisiDerin (int a, int b)
{
if(a>b)
return a;
else
return b;
}
Bu iş tamam. Şimdi bize bir düğümün yükseklik değerini veren bir fonksiyon lazım;
int yukseklik(struct node *N)
{
if(N=NULL)
return 0;
else
return N->height;
}
Mantık basit, bu fonksiyona bir düğüm structı gönderdiğimizde o düğümün yükseklik değerini bize verecek.
Şimdi esas fonksiyonuma geri dönüyorum;
struct node *leftRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = HandisiDerin(yukseklik(y->left), yukseklik(y->right))+1;
x->height = HangisiDerin(yukseklik(x->left), yukseklik(x-right))+1;
}
Kırmızı satırlı kodlarda y ve x yüksekliklerini güncelledik. Ne yaptık? herbir nodülün sol çocuklarına ve sağ çocuklarının sayısına baktık. Hangisinin sayısı yüksekse yüksekliğine 1 daha ekleyip artırdık, güncelledik.
Şimdi eminim soruyorsunuzdur, en baştaki satırda *x diye struct oluşturmuştuk. Ne oldu o diye. O düğüm çok büyüdü, çok geliştirdi kendini, Root oldu :) Neden? çünkü sola döndürme işleminde eski root'un sol çocuğu yeni root haline gelir. O yüzden son satırda root değerini geri döndürüyoruz.
struct node *leftRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = HandisiDerin(yukseklik(y->left), yukseklik(y->right))+1;
x->height = HangisiDerin(yukseklik(x->left), yukseklik(x-right))+1;
return x;
}
Temel mantık bu şekilde. Burada şu an balans faktörü ve bilimum diğer fonksiyon bulunmuyor. Size Rotate işlemine nasıl yaklaşılır bundan bahsettim. Değilse kafamıza göre rotate yani döndürme işlemi yapamayız. Balans faktörü fonksiyonu devreye girer ve onun sonucuna göre işlemler gerçekleştirilir. Bu kodları ve daha fazlasını merak ediyorsanız
AVL Ağacı C kodu konumuza göz atabilirsiniz.
