Inserisci

Lezione 9 di 16 del corso Albero AVL - Serie sulle strutture dati #10 di Coddy.

insert inizia come un normale inserimento in un albero binario di ricerca: scendi confrontando i valori, vai a sinistra o a destra e colloca il nuovo nodo nel punto in cui trovi uno spazio nullo (ignora i duplicati). La parte AVL avviene durante la risalita: dopo aver collocato il nodo, ogni antenato lungo il percorso ricalcola la propria height e controlla il proprio fattore di bilanciamento.

Se un nodo diventa sbilanciato, il lato più pesante e la posizione in cui è finito il nuovo valore determinano insieme quale dei quattro casi si applica: sinistra-sinistra e destra-destra richiedono una sola rotazione, mentre sinistra-destra e destra-sinistra ne richiedono due: una rotazione interna per raddrizzare lo zig-zag, seguita da quella esterna.

Sfida

Medio

Scrivi un metodo insert(value) su AVLTree (un helper ricorsivo è la soluzione più pulita). Inserisci value come in un normale BST, ignorandolo se è già presente. Durante la risalita, ricalcola l’altezza e il fattore di bilanciamento di ogni nodo e, se un nodo è sbilanciato, applica la rotazione corrispondente (o la coppia di rotazioni) prima di risalire nello stack delle chiamate.

Provalo tu

#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;
}