Elimina

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

L’eliminazione è l’eliminazione in un BST con lo stesso criterio di riequilibrio dell’inserimento. Ci sono tre casi da gestire per il nodo da rimuovere: nessun figlio (lo rimuovi semplicemente), un figlio (lo sostituisci con quel figlio) oppure due figli, il caso più complesso, in cui sostituisci il valore del nodo con il suo successore in-order (il valore più piccolo nel suo sottoalbero destro) e poi elimini invece quel successore dal sottoalbero destro.

Proprio come per l’inserimento, ogni antenato, risalendo, ricalcola la propria altezza e il fattore di bilanciamento, applicando il caso di rotazione appropriato se diventa sbilanciato. La logica di riequilibrio è identica a quella dell’inserimento; cambia solo la condizione per scegliere il caso, che ora considera il fattore di bilanciamento del figlio più pesante invece della posizione in cui è stato inserito un nuovo valore.

Sfida

Medio

Scrivi un metodo delete(value) su AVLTree (un helper ricorsivo è una buona soluzione). Rimuovi value usando la procedura standard di eliminazione degli alberi BST: per un nodo con due figli, sostituisci il suo valore con il valore più piccolo nel suo sottoalbero destro, quindi elimina quel valore dal sottoalbero destro. Non fare nulla se value non viene trovato. Risalendo, ricalcola le altezze e riequilibra esattamente come fa insert.

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, "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;
}