Sil

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

Silme işlemi, ekleme ile aynı yeniden dengeleme alışkanlığına sahip bir BST silme işlemidir. Kaldırılan düğüm için ele alınması gereken üç durum vardır: çocuk yoksa (sadece kaldırın), bir çocuk varsa (onu o çocukla değiştirin) veya iki çocuk varsa (zor durum), bu durumda düğümün değerini in-order successor (sağ alt ağacındaki en küçük değer) ile değiştirirsiniz ve ardından o ardılı sağ alt ağaçtan silersiniz.

Tıpkı eklemede olduğu gibi, yukarı doğru geri dönerken her ata düğüm kendi yüksekliğini ve denge faktörünü yeniden hesaplar ve dengesizleşirse uygun olan rotasyon durumunu uygular. Yeniden dengeleme mantığı ekleme ile aynıdır, sadece hangi durumun seçileceğine dair koşul, yeni bir değerin nereye yerleştiği yerine artık ağır olan çocuğun denge faktörüne bakar.

Görev

Orta

AVLTree üzerinde bir delete(value) metodu yazın (özyinelemeli bir yardımcı fonksiyon iyi sonuç verir). value değerini standart BST silme işlemini kullanarak kaldırın: iki çocuğu olan bir düğüm için, değerini sağ alt ağacındaki en küçük değerle değiştirin ve ardından bu değeri sağ alt ağaçtan silin. Eğer value bulunamazsa hiçbir şey yapmayın. Yukarı doğru geri dönerken, tıpkı insert işleminde olduğu gibi yükseklikleri yeniden hesaplayın ve yeniden dengeleyin.

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, "delete") == 0) {
            AVLTree_delete(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "search") == 0) {
            if (AVLTree_search(tree, arg)) {
                printf("true\n");
            }
            if (!AVLTree_search(tree, arg)) {
                printf("false\n");
            }
        }
        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");
        }
    }
    return 0;
}