Suppression

Leçon 11 sur 16 du cours Arbre AVL - Série Structures de données n°10 de Coddy.

La suppression est une suppression d'ABR avec la même habitude de rééquilibrage que l'insertion. Trois cas de figure sont à gérer pour le nœud à supprimer : aucun enfant (il suffit de le supprimer), un enfant (le remplacer par cet enfant), ou deux enfants, le cas délicat, où vous remplacez la valeur du nœud par son successeur en ordre (la plus petite valeur de son sous-arbre droit), puis vous supprimez ce successeur du sous-arbre droit à la place.

Tout comme pour l'insertion, chaque ancêtre, lors de la remontée, recalcule sa hauteur et son facteur d'équilibre, en appliquant le cas de rotation approprié s'il devient déséquilibré. La logique de rééquilibrage est identique à celle de l'insertion, seule la condition pour choisir le cas à appliquer examine désormais le facteur d'équilibre de l'enfant le plus lourd au lieu de l'endroit où une nouvelle valeur a été placée.

Défi

Moyen

Écrivez une méthode delete(value) sur AVLTree (une fonction d'aide récursive fonctionne bien). Supprimez value en utilisant la suppression standard d'un BST : pour un nœud avec deux enfants, remplacez sa valeur par la plus petite valeur de son sous-arbre droit, puis supprimez cette valeur du sous-arbre droit. Ne faites rien si value n'est pas trouvée. En remontant, recalculez les hauteurs et rééquilibrez exactement comme insert le fait.

Essayez vous-même

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