AVL AĞAÇLARI (C)

AVL ağaçlarının bir önceki konuda gördüğümüz ağaçlardan en önemli farkı genellikle balance factor adında karşımıza çıkan fonksiyonunun olmasıdır. Biraz daha açacak olursak ağacın (sol tarafı yüksekliği – sağ tarafı yüksekliği) veya (sağ tarafı yüksekliği – sol tarafı yüksekliği) şeklinde bir denge kurulmaya çalışılır. Eğer ağaçta bir dengesizlik varsa (1’den büyükse veya -1 den küçükse) döndürme işlemleri uygulanarak ağaç kendi kendini dengeler.

Binary Search Tree konusunu bir önceki yazımda ele almıştım. BST’lerde ağaca eleman eklediğimiz zamanda herhangi bir kontrol uygulanmadan ağacın sağına veya soluna ekliyorduk. Bu şekilde çok fazla eleman eklediğinde ağaçta dengesizlikler oluşabilir. 4 çeşit dengesizlik tipi ile karşı karşıya gelebiliyoruz. Bunlar:

1- Left-left Case (Sol-Sol Durumu)

Eğer ağacın kökünden hep daha küçük düğümler eklemeye çalıştığımızda sol tarafa doğru bir dengesizlik oluşur. Bu durumda sağ tarafa döndürme işlemi uygulanarak, dengesizlik çözülmeye çalışılır. Aşağıdaki şekilde gözükmektedir.

2- Right – Right Case (Sağ-Sağ Durumu)

Aynı şekilde kökten daha büyük düğümler eklenmeye çalıştıkça ağacın sağ tarafına doğru bir dengesizlik oluşacaktır. Bunun için de sola döndürme uyguluyoruz. Aşağıdaki şekilde gözükmektedir.

3- Right-Left Case (Sağ-Sol Durumu)

Ağacın sağ tarafında, sol tarafa doğru bir büyüme gerçekleştiyse bu durumda karşımıza çıkan bir bozukluktur. Bunun çözümü için ilk önce sağa sonra da sola döndürme işlemleri uygulanır.

4- Left-Right Case (Sol-Sağ Durumu)

Ağacın sol tarafında, sağ tarafa doğru bir büyüme gerçekleştiyse bu durum ile karşılaşırız. İlk olarak sol, sonra da sağ tarafa doğru döndürme gerçekleştirmeliyiz.

Şekiller üzerinden göstermemizin üzerine kodlara geçelim. AVL Ağaçlarında Ekleme-Silme fonksiyonlarını ve bu fonksiyonlar için gerekli olan fonksiyonları inceleyelim. Yukarıdaki 4 durumunda uygulanacak döndürme durumlarını kodlardan inceleyip, çizerek denemenizi öneririm.

typedef struct _node{
    struct _node *leftChild;
    struct _node *rightChild;
    int value;
    int height;
    
}Node;

// Routine Tanımları
int checkBalance(Node *root);
int max(int a,int b);
int getHeight(Node *root);
void rotateRight(Node **root);
void rotateLeft(Node **root);
void insertOnAVLTree(Node **root,int key);
Node *minValueNode(Node *node);

int max(int a, int b){ 
       return (a > b) ? a : b;
}
Node *minValueNode(Node *tree){
    Node *node = tree;
    while (node->leftChild != NULL) {
        node = node->leftChild;
    }
    return node;
}

int checkBalance(Node *root){
    if (root == NULL) {
        return 0;
    }
    return getHeight(root->leftChild) - getHeight(root->rightChild);
    
}

int getHeight(Node *root){
    if (root == NULL) {
        return 0;
    }
    return root->height;
}

void rotateRight(Node **gParent){
    Node *tempNode = (*gParent)->leftChild;
    Node *x = tempNode->rightChild;
    tempNode->rightChild = (*gParent);
    (*gParent)->leftChild = x;
    (*gParent)->height = 1 + max(getHeight((*gParent)->leftChild),getHeight((*gParent)->rightChild));
    tempNode->height = 1 + max(getHeight(tempNode->leftChild), getHeight(tempNode->rightChild));
    (*gParent) = tempNode;
    
    
}

void rotateLeft(Node **gParent){
       Node *tempNode = (*gParent)->rightChild;
       Node *x = tempNode->leftChild;
       tempNode->leftChild = (*gParent);
       (*gParent)->rightChild = x;
       (*gParent)->height = 1 + max(getHeight((*gParent)->leftChild),getHeight((*gParent)->rightChild));
       tempNode->height = 1 + max(getHeight(tempNode->leftChild), getHeight(tempNode->rightChild));
       (*gParent) = tempNode;
}

void insertOnAVLTree(Node **root,int key){
    if ((*root) == NULL  ) {
        Node *n = (Node*)malloc(sizeof(Node));
        n->leftChild = NULL;
        n->rightChild = NULL;
        n->value = key;
        n->height = 1;
        (*root) = n;
        return;
    }
    
        if ((*root)->value < key) {
            insertOnAVLTree(&((*root)->rightChild), key);
        }
        else if((*root)->value > key){
            insertOnAVLTree(&((*root)->leftChild), key);
        }
        else return;
        
        (*root)->height = 1 + max(getHeight((*root)->leftChild), getHeight((*root)->rightChild));
        int balance = checkBalance((*root));
        // Sağ-sağ Durumu 
        if (balance < -1 && (*root)->rightChild->value < key) 
             rotateLeft(&(*root));
        // Sağ-Sol Durumu
        if (balance < -1 && (*root)->rightChild->value > key) {
             rotateRight(&(*root)->rightChild);
             rotateLeft(&(*root));
        }
        // Sol-Sol Durumu
        if (balance > 1 && (*root)->leftChild->value > key) 
             rotateRight(&(*root));
        // Sol-Sağ Durumu
        if (balance > 1 && (*root)->leftChild->value < key) {
             rotateLeft(&(*root)->leftChild);
             rotateRight(&(*root));
        }
    
   
}

void deleteNode(Node **root,int key){
    if (root == NULL)
        return ;
    
    if ((*root)->value < key)
        deleteNode(&(*root)->rightChild, key);
    
    else if ((*root)->value > key)
        deleteNode(&(*root)->leftChild, key);
    
    else{
        // tek çocuk veya 0 çocuk durumu
        if ((*root)->leftChild == NULL || (*root)->rightChild == NULL)  {
            Node *temp = (*root)->leftChild ? (*root)->leftChild : (*root)->rightChild;
            // 0 çocuk durumu
            if (temp == NULL)
                (*root) = NULL;
            
            else (*root) = temp;
        }
        else{
            Node *temp = minValueNode((*root)->rightChild);
            (*root)->value = temp->value;
            deleteNode(&(*root)->rightChild, temp->value);
            
        }
    }
    if ((*root) == NULL) {
        return ;
    }
    (*root)->height = 1 + max(getHeight((*root)->leftChild), getHeight((*root)->rightChild));
    int balance;
    balance = checkBalance(*root);
    
    // LL
    if (balance > 1 && checkBalance((*root)->leftChild) >= 0)
        rotateRight(&(*root));
    
    // RR
    if (balance < -1 && checkBalance((*root)->rightChild) <= 0)
        rotateLeft(&(*root));
    
    // LR
    
    if (balance > 1 && checkBalance((*root)->leftChild) < 0 ) {
        rotateLeft(&(*root)->leftChild);
        rotateRight(&(*root));
    }
    // RL
    
    if (balance < -1 && checkBalance((*root)->rightChild) > 0) {
        rotateRight(&((*root)->rightChild));
        rotateLeft(&(*root));
    }
    
    
    
}



void printAVLTree(Node *root){. // root->sol->sağ bastıracaktır.
    if (root == NULL) {
        return ;
    }
    if(root){
        printf("[%d] ", root->value);
        printAVLTree(root->leftChild);
        printAVLTree(root->rightChild);
    }
    
}


// Yine denemeniz amaçlı main fonksiyonunu ve çıktıyı girmedim. Yanlış yaptığım yerler olabilir, çıktılarda hata alınabilir ve denemeden kod öğrenilmiyor maalesef.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir