Ekle

Coddy'nin AVL Tree - Veri Yapıları Serisi #10 kursunda ders 9 / 16.

insert sıradan bir ikili arama ağacı ekleme işlemi olarak başlar: değerleri karşılaştırarak aşağı inin, sola veya sağa gidin ve yeni düğümü boş bir yuva bulunan yere yerleştirin (yinelenenleri yoksayın). AVL kısmı yukarı dönüş yolunda gerçekleşir: düğümü yerleştirdikten sonra, yol üzerindeki her ata düğüm kendi height değerini yeniden hesaplar ve denge faktörünü kontrol eder.

Bir düğüm dengesiz hale gelirse, hangi tarafın ağır olduğu ve yeni değerin nereye yerleştiği birlikte dört durumdan hangisinin geçerli olduğuna karar verir: sol-sol ve sağ-sağ tek bir döndürme gerektirirken, sol-sağ ve sağ-sol iki döndürme gerektirir; zikzağı düzeltmek için bir iç döndürme ve ardından dış döndürme yapılır.

Görev

Orta

AVLTree üzerinde bir insert(value) metodu yazın (en temiz yol özyinelemeli bir yardımcı fonksiyon kullanmaktır). value değerini normal bir BST gibi ekleyin, eğer zaten mevcutsa görmezden gelin. Yukarı dönüş yolunda, her düğümün yüksekliğini ve denge faktörünü (balance factor) yeniden hesaplayın ve bir düğüm dengesizse, çağrı yığınında (call stack) yukarı dönmeden önce uygun rotasyonu (veya rotasyon çiftini) uygulayın.

Kendin dene

#include <stdio.h>
#include <string.h>
#include "avltree.h"

static void preorderValues(Node* node, int* vals, int* count) {
    if (node == NULL) {
        return;
    }
    vals[(*count)++] = node->value;
    preorderValues(node->left, vals, count);
    preorderValues(node->right, vals, count);
}

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "preorder") == 0) {
            int vals[10000];
            int count = 0;
            preorderValues(tree->root, vals, &count);
            for (int i = 0; i < count; i++) {
                if (i > 0) {
                    printf(" ");
                }
                printf("%d", vals[i]);
            }
            printf("\n");
        }
        if (parsed >= 1 && strcmp(cmd, "height") == 0) {
            printf("%d\n", AVLTree_getHeight(tree, tree->root));
        }
    }
    return 0;
}