Insertion

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

insert commence comme une insertion ordinaire dans un arbre binaire de recherche : on descend en comparant les valeurs, on va à gauche ou à droite, et on place le nouveau nœud là où un emplacement nul est trouvé (ignorez les doublons). La partie AVL se produit lors de la remontée : après avoir placé le nœud, chaque ancêtre sur le chemin recalcule sa height et vérifie son facteur d'équilibre.

Si un nœud devient déséquilibré, le côté qui est lourd et l'endroit où la nouvelle valeur a été placée décident ensemble lequel des quatre cas s'applique : left-left et right-right nécessitent une rotation simple, tandis que left-right et right-left en nécessitent deux, une rotation interne pour redresser le zig-zag suivie de la rotation externe.

Défi

Moyen

Écrivez une méthode insert(value) sur AVLTree (un assistant récursif est la manière la plus propre). Insérez value comme dans un BST normal, en l'ignorant si elle est déjà présente. Lors de la remontée, recalculez la hauteur et le facteur d'équilibre de chaque nœud, et si un nœud est déséquilibré, appliquez la rotation correspondante (ou la paire de rotations) avant de remonter dans la pile d'appels.

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