#include<stdio.h>
#include<stdlib.h>
/*
****************************************
****************************************
********** Algoritma Uzmanı*************
********** Daha Fazla Kod İçin**********
*******algoritmauzmani.blogspot.com*****
****************************************
****************************************
*/
// AVL Agacindaki düğümler için struct oluşturduk
struct node
{
int key;
struct node *left;
struct node *right;
int height;
};
// İki değeri birbiriyle karşılaştırıp değer döndüren fonksiyon
int max(int a, int b);
// Bir düğümün yüksekliğini geri döndüren fonksiyon
int height(struct node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// iki sayıdan hangisi büyük ise onu döndürür.
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Ekleme Yaparken bu fonksiyonu kullanacağız. Bu fonksiyon ağaca ekleme yapmaz! Sadece bir düğüm oluşturur.! */
struct node* newNode(int key)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // Yeni düğüm her zaman Yaprak yani leaf olur. Bu yüzden 1 atıyoruz. Daha sonra duruma göre güncellenir.
return(node);
}
/*
y x
/ \ Right Rotation / \
x T3 – – – – – – – > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
*/
// Bu fonksiyon sağa döndürme işlemi yapar. Kafanızda canlandıramazsanız üstteki ağaç yapısına bakabilirsiniz.
struct node *rightRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
// Döndürme işlemlerini yapıyoruz
x->right = y;
y->left = T2;
// Yükseklikleri güncelliyoruz
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
// Yeni kök düğümü döndürüyoruz
return x;
}
// Sola Döndürme işlemi yapan fonksyion
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
struct node *T2 = y->left;
// Döndürme işlemi
y->left = x;
x->right = T2;
// Yükseklik güncellemesi
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Yeni kök düğümü döndürüyoruz
return y;
}
// Balans faktörü fonksiyonu.
int getBalance(struct node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// AVL Ağacına ekleme yapan fonksiyon
struct node* insert(struct node* node, int key)
{
/* Normal Düğüm ekleme işlemlerini gerçekleştiriyoruz */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
/* Ata düğümün yüksekliğini güncelliyoruz. Yani parentin parentini (dede işte :)) */
node->height = max(height(node->left), height(node->right)) + 1;
/* Balans değişkenine getbalance fonksiyonundan return edilecek değeri atıyoruz. */
int balance = getBalance(node);
// Eğer balance değeri 1'den büyükse 4 ayrı durum oluşur.
// Sol-Sol durumu, sağ-sağ durumu, sol-sağ durumu, sağ sol durumu
// Sol Sol durumu
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Sağ Sağ durumu
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// sol sağ durumu
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Sağ sol durumu
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
/* değişmemiş düğümü döndürüyoruz */
return node;
}
// preOrder traversal yapan fonksiyon.
void preOrder(struct node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
// Main Fonksiyonu. (hadi canım)
int main()
{
struct node *root = NULL;
/* Burada kafanıza göre değer ekleyin deneyin bakın */
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
/* Yukarıdaki kodla aşağıdaki ağaç oluşut
30
/ \
20 40
/ \ \
10 25 50
*/
printf("AVL Agaci Ciktisi ... **** AlgoritmaUzmani.blogspot.com \n");
preOrder(root);
return 0;
}
Etiketler: avl ağacı c kodu, avl ağacı c kodu nasıl yazılır, avl ağacı nedir, AVL Algoritması c kodu