Ana içeriğe geç

Ağaç Veri Yapısı

Ağaç veri yapısı, birbirine bağlı düğümlerden oluşan hiyerarşik bir yapıdır. Ağaç, kök düğümden başlar ve dallara ayrılır. Her düğüm, birden çok alt düğüme sahip olabilir, ancak yalnızca bir üst düğüme bağlıdır. Bu nedenle, her düğüm, bir üst düğüme ve birden çok alt düğüme bağlıdır. Ağaç veri yapısı, birçok algoritma ve veri yapısında kullanılır, özellikle arama, ekleme, silme, gezinme gibi işlemler için kullanışlıdır. Ağaç veri yapısı, özellikle ikili arama ağaçları, AVL ağaçları, kırmızı-siyah ağaçları, B- ağaçları ve Heap ağaçları gibi birçok türde mevcuttur. Ağaç veri yapısı, verilerin hiyerarşik bir yapıda organize edilmesi gerektiği birçok uygulama için idealdir. Örnek olarak, aile ağacı, dosya sistemleri, XML verileri vb. veri yapıları ağaç veri yapısı ile oluşturulabilir.

Ağaç Türleri​

Ağaç veri yapısı, birbirine bağlı düğümlerden oluşur ve bu düğümler hiyerarşik bir yapıda organize edilirler. Ağaçlar, aşağıdaki temel tiplere ayrılabilir:

  1. İkili ağaçlar: Her düğüm en fazla iki alt düğüme sahip olan ağaçlardır. İkili arama ağaçları, AVL ağaçları, kırmızı-siyah ağaçları vb. bu kategoriye girer.
  2. Çoklu ağaçlar: Her düğüm birden fazla alt düğüme sahip olan ağaçlardır. Örneğin, B-ağaçları ve önbellek ağaçları bu kategoriye girer.
  3. Temsil ağaçları: Yapısal ilişkileri göstermek için kullanılan ağaçlardır. Örnek olarak, aile ağacı ve dosya sistemleri bu kategoriye girer.
  4. Threaded ağaçlar: Ağaçların gezinmesini hızlandırmak için eklenen bağlantılarla düğümlere bağlıdır. İkili ağaçlar, çoklu ağaçlar ve temsil ağaçları threaded ağaçlara dönüştürülebilir.

Bu temel ağaç türleri farklı uygulamalar için kullanılabilir ve özelleştirilebilir. Her tür, birçok algoritma ve veri yapısında kullanılan farklı veri yapılarına sahiptir ve belirli işlemler için daha verimli olabilir.

 İkili Ağaçlara Giriş​

İkili ağaçlar, her düğümün en fazla iki alt düğümü olan bir ağaç türüdür. Genellikle arama işlemleri için kullanılırlar ve özellikle ikili arama ağaçları, AVL ağaçları, kırmızı-siyah ağaçları gibi türleri mevcuttur.

İkili arama ağaçları, her düğümün bir anahtar değeri olduğu, her sol alt ağacın anahtarının üst düğümün anahtarından küçük, her sağ alt ağacın anahtarının üst düğümün anahtarından büyük olduğu bir ikili ağaçtır. Bu nedenle, bir anahtarın arama işlemi, ağacın dalgalanmasını azaltarak hızlı bir şekilde yapılabilir.

AVL ağaçları, bir tür ikili arama ağacıdır ve bir düğümün sol ve sağ alt ağaçlarının yüksekliği arasındaki farkın en fazla bir birim olduğu bir özellikleri vardır. Bu özellik, ağacın denge faktörü olarak bilinir ve AVL ağacı, ağacın dalgalanmasını azaltarak arama, ekleme ve silme işlemlerini hızlandırır.

Kırmızı-siyah ağaçları da bir tür ikili arama ağacıdır ve bir düğümün kırmızı veya siyah olarak işaretlenebileceği bir özellikleri vardır. Kırmızı-siyah ağaçları, her düğümün siyah veya kırmızı olduğu bir ağaç türüdür. Kırmızı düğümler, siyah düğümler arasında bulunur ve ağacın dengesini korumak için çeşitli kurallar vardır. Bu kurallar, ağacın dalgalanmasını azaltarak arama, ekleme ve silme işlemlerini hızlandırır.

İkili ağaçlar, verilerin hiyerarşik bir yapıda organize edilmesi gerektiği birçok uygulama için idealdir. Örnek olarak, işlemci yapısı, dosya sistemi, ve yapay zeka gibi alanlarda kullanılabilirler.

İkili Ağaçlarda inorder dolaşma​

İkili ağaçlar üzerinde dolaşma, ağaçtaki düğümleri belirli bir sırayla ziyaret etmek için kullanılan bir işlemdir. Bu işlem, ağacın yapısını anlamak ve ağaçtaki verileri işlemek için önemlidir. İkili ağaçlarda, düğümler sol alt ağaç ve sağ alt ağaç olarak ikiye ayrılır ve ağaçta üç farklı şekilde dolaşma işlemi yapılabilir:

  1. Inorder Dolaşma (LNR): Inorder dolaşma, önce sol alt ağaca giderek en küçük değerli düğüme, sonra üst düğüme ve en son sağ alt ağaca giderek en büyük değerli düğüme ulaşarak tüm düğümleri ziyaret eder. Inorder dolaşma, özellikle ikili arama ağaçlarında kullanışlıdır çünkü ağaçtaki düğümler anahtarlarının artan sırayla ziyaret edilir.
  2. Preorder Dolaşma (NLR): Preorder dolaşma, önce üst düğüme, sonra sol alt ağaca ve en son sağ alt ağaca giderek tüm düğümleri ziyaret eder. Preorder dolaşma, ağacın yapısını anlamak için kullanışlıdır.
  3. Postorder Dolaşma (LRN): Postorder dolaşma, önce sol alt ağaca ve sağ alt ağaca giderek en küçük ve en büyük değerli düğümleri ziyaret eder ve son olarak üst düğüme gelir. Postorder dolaşma, ağacın yapısını anlamak için kullanışlıdır ve genellikle ağaçta silme işlemleri için kullanılır.

İkili Ağaç Oluşturmak​

İkili ağaç (Binary Tree), her bir düğümün en fazla iki alt düğümü olan bir veri yapısıdır. İşte C dilinde ikili ağaç oluşturmak için bir örnek kod:


#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node* createNode(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

void inorderTraversal(struct Node* node) {
    if (node == NULL)
        return;
    inorderTraversal(node->left);
    printf("%d ", node->data);
    inorderTraversal(node->right);
}

int main() {
    struct Node *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Inorder traversal of binary tree is: ");
    inorderTraversal(root);

    return 0;
}


Bu kod, bir struct Node yapısı tanımlar, bir düğümün veri yapısını ve ağacın sol ve sağ alt dallarına işaret eden iki işaretçiyi içerir. createNode fonksiyonu, verilen data değeriyle bir düğüm oluşturur ve başlangıçta sol ve sağ alt dallarını NULL olarak ayarlar.

inorderTraversal fonksiyonu, ağacı inorder (sol alt dal, düğüm, sağ alt dal) sırasına göre dolaşan bir yinelemeli işlevdir. main fonksiyonu, bir kök düğümü oluşturur ve sol ve sağ alt dalları ile birlikte doldurur. Sonra inorderTraversal fonksiyonunu çağırarak ağacı inorder olarak dolaşır ve düğümlerin değerlerini ekrana yazdırır.

İkili Ağaca Eleman Ekleme​

Aşağıdaki gibi bir fonksiyon ile ikili ağaca eleman ekleyebilirsiniz:

struct Node* insertNode(struct Node* node, int data) {
    if (node == NULL) {
        return createNode(data);
    }
    if (data < node->data) {
        node->left = insertNode(node->left, data);
    }
    else if (data > node->data) {
        node->right = insertNode(node->right, data);
    }
    return node;
}


Bu fonksiyon, ağaca yeni bir eleman eklemek için kullanılır. İki parametre alır: node mevcut düğümün işaretçisini ve data eklenecek olan veriyi. Eğer düğüm yoksa, createNode fonksiyonuyla yeni bir düğüm oluşturulur ve geri döndürülür. Eğer düğüm varsa, data parametresi, mevcut düğümün verisiyle karşılaştırılır ve data küçükse sol alt dala, büyükse sağ alt dala eklenir.

insertNode fonksiyonunu main fonksiyonunda aşağıdaki gibi kullanabilirsiniz:

int main() {
    struct Node *root = NULL;

    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 70);
    insertNode(root, 60);
    insertNode(root, 80);

    printf("Inorder traversal of binary tree is: ");
    inorderTraversal(root);

    return 0;
}

Bu şekilde, insertNode fonksiyonunu kullanarak ağaca çeşitli elemanlar ekleyebilirsiniz. Sonra, inorderTraversal fonksiyonunu çağırarak ağacı inorder olarak dolaşarak, düğümlerin değerlerini ekrana yazdırabilirsiniz.

İkili Arama Ağaçları​

İkili arama ağaçları (binary search trees) verileri tutmak ve sıralamak için kullanılan veri yapılarından biridir. Her düğüm, solda yer alan düğümün değeri kendisinden küçük, sağda yer alan düğümün değeri kendisinden büyük olan bir anahtar (key) tutar.

İkili arama ağaçları ayrıca AVL ağaçları, kırmızı-siyah ağaçlar ve B ağaçları gibi çeşitli tiplerde uygulanabilir. Bu ağaç türleri farklı performans ve hafıza gereksinimleri ile birlikte gelir.

İkili arama ağaçları, arama, ekleme ve silme işlemleri için oldukça verimlidir. Arama işlemi, ağacın dengeli olması durumunda O(log n) zamanında gerçekleştirilir. Ekleme ve silme işlemleri de benzer şekilde yürütülür.

Ancak, ağacın yapısının dengelenmesi ile ilgili problemler, ağaçta büyük değişiklikler yapılması gerektiğinde bazı sorunlar yaratabilir. Bu nedenle, ağacın olası maksimum derinliği, yani O(n) olabilir. Bu durumda, ağaç kötü dengelenmiş olarak nitelendirilir.

Sonuç olarak, ikili arama ağaçları, küçük ve orta boyutlu veriler için verimli bir seçenektir. Büyük veri kümeleri için, dengelenmiş ağaçlar veya başka bir veri yapısı daha uygun olabilir.

İkili Arama Ağacına Veri Eklemek​

Aşağıdaki C kodu, bir ikili arama ağacına veri eklemek için örnek bir işlev gösterir:

struct node {
    int data;
    struct node* left;
    struct node* right;
};

struct node* newNode(int data) {
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

struct node* insert(struct node* node, int data) {
    if (node == NULL) return newNode(data);
    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    return node;
}

Bu kodda, struct node veri yapısı, her düğümün bir data değeri ve sol ve sağ alt ağaçları için bağlantıları içerir. newNode() işlevi, yeni bir düğüm oluşturmak için kullanılır. insert() işlevi, ikili arama ağacına yeni bir veri eklemek için kullanılır. İşlev, node parametresi olarak mevcut ağaç düğümünü ve data parametresi olarak eklemek istediğimiz yeni veriyi alır.

insert() işlevi, ağaçta yeni bir düğüm oluşturmak için newNode() işlevini çağırır. Sonra, yeni veri, ağaçta uygun konuma yerleştirilir. Eğer veri, mevcut düğümün verisinden küçükse, işlev sol alt ağaca veriyi ekler. Eğer veri, mevcut düğümün verisinden büyükse, işlev sağ alt ağaca veriyi ekler.

İşlev, sonunda, güncellenmiş ağaç yapısını temsil eden kök düğümünü döndürür. Bu sayede, eklenen veriler ağaçta kalıcı olarak saklanır.

Bir Ağacın Düğümlerinin Sayısını Bulmak​

Aşağıdaki C kodu, bir ikili arama ağacındaki düğümlerin sayısını bulmak için örnek bir işlev gösterir:


struct node {
    int data;
    struct node* left;
    struct node* right;
};

int countNodes(struct node* node) {
    if (node == NULL)
        return 0;
    else
        return(countNodes(node->left) + 1 + countNodes(node->right));
}


Bu kodda, struct node veri yapısı, her düğümün bir data değeri ve sol ve sağ alt ağaçları için bağlantıları içerir. countNodes() işlevi, ağaçtaki düğümlerin sayısını hesaplamak için kullanılır. İşlev, node parametresi olarak mevcut ağaç düğümünü alır.

countNodes() işlevi, özyinelemeli bir yapıya sahiptir. İlk olarak, mevcut düğümün NULL olup olmadığını kontrol eder. Eğer NULL ise, ağaçta hiçbir düğüm yoktur ve işlev 0 değerini döndürür. Aksi takdirde, işlev, sol alt ağaçtaki düğümleri saymak için kendisini sol alt ağaç düğümüyle çağırır. Aynı şekilde, sağ alt ağaçtaki düğümleri saymak için kendisini sağ alt ağaç düğümüyle çağırır. Sonra, işlev, mevcut düğümü de dahil ederek sol ve sağ alt ağaçlardaki düğüm sayılarını toplar ve 1 ekler. Toplam sayı, ağaçtaki toplam düğüm sayısını temsil eder ve işlev tarafından döndürülür.

Bu şekilde, countNodes() işlevi, bir ikili arama ağacındaki düğümlerin sayısını hızlı ve etkili bir şekilde hesaplamak için kullanılabilir.

Bir Ağacın Yüksekliğini Bulma​

Aşağıdaki C kodu, bir ikili arama ağacının yüksekliğini hesaplamak için örnek bir işlev gösterir:

struct node {
    int data;
    struct node* left;
    struct node* right;
};

int height(struct node* node) {
    if (node == NULL)
        return 0;
    else {
        int left_height = height(node->left);
        int right_height = height(node->right);
        if (left_height > right_height)
            return(left_height + 1);
        else
            return(right_height + 1);
    }
}

Bu kodda, struct node veri yapısı, her düğümün bir data değeri ve sol ve sağ alt ağaçları için bağlantıları içerir. height() işlevi, ağacın yüksekliğini hesaplamak için kullanılır. İşlev, node parametresi olarak mevcut ağaç düğümünü alır.

height() işlevi, özyinelemeli bir yapıya sahiptir. İlk olarak, mevcut düğümün NULL olup olmadığını kontrol eder. Eğer NULL ise, ağaçta hiçbir düğüm yoktur ve işlev 0 değerini döndürür. Aksi takdirde, işlev, sol alt ağacın yüksekliğini hesaplamak için kendisini sol alt ağaç düğümüyle çağırır. Aynı şekilde, sağ alt ağacın yüksekliğini hesaplamak için kendisini sağ alt ağaç düğümüyle çağırır. Sonra, işlev, sol ve sağ alt ağaçların yüksekliği arasında en büyük olanını seçer ve 1 ekler. Bu, mevcut düğümün yüksekliği olarak hesaplanır ve işlev tarafından döndürülür.

Bu şekilde, height() işlevi, bir ikili arama ağacının yüksekliğini hızlı ve etkili bir şekilde hesaplamak için kullanılabilir.

İkili Arama Ağacından Bir Düğüm Silmek​


struct node {
    int data;
    struct node* left;
    struct node* right;
};

struct node* minValueNode(struct node* node) {
    struct node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

struct node* deleteNode(struct node* root, int key) {
    if (root == NULL)
        return root;

    if (key < root->data)
        root->left = deleteNode(root->left, key);

    else if (key > root->data)
        root->right = deleteNode(root->right, key);

    else {
        if (root->left == NULL) {
            struct node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct node* temp = root->left;
            free(root);
            return temp;
        }
        struct node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}


Bu kodda, struct node veri yapısı, her düğümün bir data değeri ve sol ve sağ alt ağaçları için bağlantıları içerir. minValueNode() işlevi, belirtilen ağaçtaki en küçük değere sahip düğümü bulmak için kullanılır. deleteNode() işlevi, belirtilen ağaçtan belirli bir düğümü silmek için kullanılır. İşlev, root parametresi olarak mevcut ağaç düğümünü ve key parametresi olarak silinecek düğümün değerini alır.

Buradaki deletenode işlevini detaylı açıklayalım.

İlk olarak, deleteNode() işlevi, silinecek düğümün ağaçta mevcut olup olmadığını kontrol eder. Eğer ağaçta böyle bir düğüm yoksa, işlev mevcut ağaç düğümünü geri döndürür ve silme işlemi gerçekleşmez. Bu adım şu şekildedir:

if (root == NULL)
    return root;

Ardından, işlev, silinecek düğümün, mevcut düğümün veri değerinden küçük veya büyük olduğunu kontrol eder. Eğer silinecek düğümün değeri, mevcut düğümün değerinden küçükse, işlev, sol alt ağacı ile kendisini tekrar çağırır. Aksi takdirde, işlev, sağ alt ağacı ile kendisini tekrar çağırır. Bu adım şu şekildedir:

if (key < root->data)
    root->left = deleteNode(root->left, key);

else if (key > root->data)
    root->right = deleteNode(root->right, key);

Eğer silinecek düğümün değeri, mevcut düğümün değerine eşitse, işlev, belirli koşullara göre düğümü siler. İlk olarak, işlev, silinecek düğümün sol alt ağacının NULL olup olmadığını kontrol eder. Eğer NULL ise, mevcut düğümün sağ alt ağacı, mevcut düğümün yerine geçer ve mevcut düğüm serbest bırakılır. Bu adım şu şekildedir:

if (root->left == NULL) {
    struct node* temp = root->right;
    free(root);
    return temp;
}

Eğer sol alt ağaç NULL değilse, işlev, silinecek düğümün sağ alt ağacının NULL olup olmadığını kontrol eder. Eğer NULL ise, mevcut düğümün sol alt ağacı, mevcut düğümün yerine geçer ve mevcut düğüm serbest bırakılır. Bu adım şu şekildedir:

else if (root->right == NULL) {
    struct node* temp = root->left;
    free(root);
    return temp;
}

Eğer her iki alt ağaç da NULL değilse, işlev, silinecek düğümün yerine geçecek en küçük düğümü bulur. Bu adım, minValueNode() işlevi kullanılarak gerçekleştirilir. Daha sonra, en küçük düğümün veri değeri, silinecek düğümün veri değeriyle değiştirilir. Son olarak, en küçük düğüm, ağaçtan silinir. Bu adım şu şekildedir:

struct node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);

İkili Arama Ağacında Minimum Elemanı Bulmak​

Aşağıda, bir ikili arama ağacındaki en küçük elemanı bulmak için yazılmış bir C kodu örneği verilmiştir:

struct node* minValueNode(struct node* node) {
    struct node* current = node;

    /* Ağacın en solundaki düğüm, en küçük değere sahip düğümdür */
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

Bu kod, ağacın en solundaki düğümü bulur ve bu düğümün adresini geri döndürür. Bu düğüm, ağacın en küçük değerine sahip düğümüdür. Kod, bir düğüm işaretçisi alan ve en küçük düğümün adresini döndüren bir minValueNode() işlevi olarak tanımlanabilir.

İkili Arama Ağacında Maximum Elemanı Bulmak​

Aşağıda, bir ikili arama ağacındaki en büyük elemanı bulmak için yazılmış bir C kodu örneği verilmiştir:

struct node* maxValueNode(struct node* node) {
    struct node* current = node;

    /* Ağacın en sağındaki düğüm, en büyük değere sahip düğümdür */
    while (current && current->right != NULL)
        current = current->right;

    return current;
}

Bu kod, ağacın en sağındaki düğümü bulur ve bu düğümün adresini geri döndürür. Bu düğüm, ağacın en büyük değerine sahip düğümüdür. Kod, bir düğüm işaretçisi alan ve en büyük düğümün adresini döndüren bir maxValueNode() işlevi olarak tanımlanabilir.

AVL Ağaçları​

AVL ağaçları, adını adını adını alan Adelson-Velsky ve Landis tarafından 1962 yılında icat edilen bir tür denge ağacıdır. İkili arama ağaçlarına benzer şekilde, her düğüm en fazla iki alt düğüme sahiptir ve soldaki alt ağaçtaki her düğüm, düğümün kendisinden küçük bir değere sahipken, sağdaki alt ağaçtaki her düğüm, düğümün kendisinden büyük bir değere sahiptir.

AVL ağaçları, ikili arama ağaçlarına ek olarak, her düğümdeki yüksekliğin dengeli olmasını sağlamak için özel bir dengelilik kuralı uygularlar. Bir düğümün dengelilik durumu, sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasındaki farkın (dengesizlik) en fazla 1 olmasıyla belirlenir. Bir AVL ağacındaki her düğümün dengelilik durumu doğru olduğunda, ağaç "dengeli" olarak adlandırılır.

AVL ağaçları, diğer denge ağaçlarına kıyasla daha yüksek işlem maliyetlerine sahip olmasına rağmen, ağacın dengeli kalmasını garanti ederek, en kötü durumda bile arama, ekleme ve silme işlemlerinde O(log n) zaman karmaşıklığı sağlarlar.

AVL ağaçları ayrıca, arama, ekleme ve silme işlemlerinde hızlı olmalarının yanı sıra, özellikle bellek yönetimi için de faydalıdırlar. AVL ağaçları, özellikle arama, ekleme ve silme işlemlerinin yoğun olduğu uygulamalarda kullanılırlar, özellikle veri tabanları, tarayıcılar, derleyiciler ve grafiksel kullanıcı arayüzleri gibi uygulamalarda sıklıkla kullanılırlar.

Bir AVL Ağacının Yapısı​

Bir AVL ağacı, bir ikili arama ağacının temel yapısına ek olarak, her düğümün yüksekliğinin denge durumunu korumak için takip edildiği özel bir dengeleme kuralına sahiptir. Bir AVL ağacındaki her düğüm, aşağıdaki gibi tanımlanabilir:

struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
};

Her düğüm, bir key adı verilen bir anahtar (değer) içerir ve her düğüm, kendisine bağlı sol ve sağ alt düğümlerinin adreslerini tutan iki işaretçi içerir: left ve right. Ayrıca, her düğümün yüksekliği de tutulur, bu da height adı verilen bir tamsayı değişken tarafından saklanır.

AVL ağacı, tüm düğümlerin denge durumunun korunması için özel bir dengeleme kuralı uygular. Her bir düğümün denge durumu, sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasındaki farkın (dengesizlik) en fazla 1 olmasıdır. Bu denge durumunun bozulması durumunda, AVL ağacı, dengesizlik durumunu ortadan kaldırmak için özel bir dengeleme algoritması kullanır.

AVL ağacının yapısı, birbirine bağlı bir dizi düğümden oluşur. AVL ağacı, her zaman bir kök düğümü içerir ve bu kök düğümü, ağacın tüm düğümlerine erişmek için kullanılır. Aşağıdaki kod, bir AVL ağacı oluşturmak için kullanılabilir:

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;
    return(node);
}

Bu kod, yeni bir AVL ağacı düğümü oluşturmak için kullanılabilir. newNode() işlevi, bir key değeri alan ve yeni bir AVL ağacı düğümü oluşturarak adresini geri döndüren bir işlev olarak tanımlanabilir. Bu işlev ayrıca, yeni düğümün sol ve sağ alt düğümlerini NULL olarak ayarlar ve yüksekliğini 1 olarak başlatır.

AVL Ağaçlarında Döndürme​

AVL ağaçları, yüksekliği dengelenmiş bir şekilde tutulan ikili arama ağaçlarıdır. AVL ağacının yüksekliği dengelenmiş olarak tutulması, arama, ekleme ve silme işlemlerinin daha hızlı olmasını sağlar. Bu yüksekliği dengelenmiş tutma işlemi, AVL ağacındaki düğümleri sağa veya sola döndürerek gerçekleştirilir. İki tür düğüm döndürme işlemi vardır: sağ döndürme (right rotation) ve sol döndürme (left rotation).

  1. Sağ Döndürme (Right Rotation): Sağ döndürme işlemi, bir düğümün sol alt ağacının yüksekliğinin sağ alt ağacından iki veya daha fazla olduğu durumlarda yapılır. Bu durumda, ağaç sağa döndürülerek yüksekliği dengelemek için düğümler değiştirilir. Aşağıdaki şekil sağ döndürme işlemi örneğini göstermektedir:
       y                              x
      / \                            / \
     x   T4   right rotate (y)     z   y
    / \       - - - - - - - ->    / \ / \
   z   T3                        T1 T2 T3 T4
  / \
T1   T2


  1. Sol Döndürme (Left Rotation): Sol döndürme işlemi, bir düğümün sağ alt ağacının yüksekliğinin sol alt ağacından iki veya daha fazla olduğu durumlarda yapılır. Bu durumda, ağaç sola döndürülerek yüksekliği dengelemek için düğümler değiştirilir. Aşağıdaki şekil sol döndürme işlemi örneğini göstermektedir:

    y                             x
   / \                          /   \
  T1   x      left rotate(y)   y     z
      / \   - - - - - - - ->  / \   / \
     T2  z                   T1 T2 T3 T4
        / \
       T3 T4

Döndürme işlemleri, AVL ağacının yüksekliği dengelenmiş bir şekilde tutulmasına yardımcı olur. Bu sayede AVL ağacı, diğer ikili arama ağaçlarına göre daha hızlı ve etkili bir şekilde arama, ekleme ve silme işlemleri gerçekleştirebilir.

AVL Ağaçlarında Silme İşlemi​

AVL ağaçları, yüksekliği dengelenmiş bir şekilde tutulan ikili arama ağaçlarıdır. AVL ağacındaki düğüm silme işlemi, önce normal bir ikili arama ağacında olduğu gibi yapılır. Ancak bu işlemden sonra AVL ağacı dengesi bozulmuş olabilir. Bu nedenle, AVL ağacındaki bir düğümün silinmesi işleminden sonra, ağacın dengesinin korunması için belirli düğüm döndürme işlemleri yapılması gerekir.

AVL ağacında bir düğümün silinmesi, aşağıdaki adımlarla gerçekleştirilir:

  1. AVL ağacından silinecek düğümün yerini bulun.
  2. Eğer silinecek düğüm yaprak düğüm ise, düğümü silin ve ağacı dengede tutmak için parent düğümlerindeki denge faktörlerini güncelleyin ve ağacın denge faktörlerini kontrol edin. Denge faktörleri +1 veya -1'den daha büyük olan düğümler varsa, sağ veya sol döndürme işlemi yaparak ağacın denge faktörünü yeniden ayarlayın.
  3. Eğer silinecek düğümün sadece bir alt ağacı varsa, silinecek düğümün yerine alt ağacı yerleştirin ve ağacın denge faktörlerini kontrol edin. Denge faktörleri +1 veya -1'den daha büyük olan düğümler varsa, sağ veya sol döndürme işlemi yaparak ağacın denge faktörünü yeniden ayarlayın.
  4. Eğer silinecek düğümün iki alt ağacı da varsa, silinecek düğümün yerine en büyük değerli sol alt ağaçtaki düğümden veya en küçük değerli sağ alt ağaçtaki düğümden biri yerleştirilir. Bu işlem, alt ağaçlardan biri boşalana kadar tekrarlanır. Sonra ağacın denge faktörleri kontrol edilir ve dengesiz düğümlere uygun şekilde döndürme işlemleri yapılır.

AVL ağacındaki silme işlemi, normal bir ikili arama ağacındaki silme işleminden farklı değildir. Ancak AVL ağacındaki dengenin korunması için belirli düğüm döndürme işlemleri yapılması gerekebilir.