Insertar

Lección 9 de 16 del curso Árbol AVL - Serie de Estructuras de Datos #10 de Coddy.

insert comienza como una inserción ordinaria en un árbol de búsqueda binaria: se desciende comparando valores, se va a la izquierda o a la derecha, y se coloca el nuevo nodo donde se encuentre un espacio nulo (ignora los duplicados). La parte de AVL ocurre en el camino de regreso hacia arriba: después de colocar el nodo, cada ancestro en la ruta recalcula su height y verifica su factor de equilibrio.

Si un nodo se desequilibra, el lado que está pesado y el lugar donde aterrizó el nuevo valor deciden juntos cuál de los cuatro casos se aplica: izquierda-izquierda y derecha-derecha necesitan una rotación simple, mientras que izquierda-derecha y derecha-izquierda necesitan dos, una rotación interna para enderezar el zig-zag seguida de la externa.

Desafío

Intermedio

Escribe un método insert(value) en AVLTree (un ayudante recursivo es la forma más limpia). Inserta value como en un BST normal, ignorándolo si ya está presente. Al regresar hacia arriba, vuelve a calcular la altura y el factor de equilibrio de cada nodo, y si un nodo está desequilibrado, aplica la rotación correspondiente (o par de rotaciones) antes de retornar por la pila de llamadas.

Pruébalo tú mismo

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