Eliminar

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

La eliminación es una eliminación de BST con el mismo hábito de reequilibrio que la inserción. Tres formas a manejar para el nodo que se está eliminando: sin hijos (simplemente eliminarlo), un hijo (reemplazarlo con ese hijo), o dos hijos, el caso complicado, donde se reemplaza el valor del nodo con su sucesor en orden (el valor más pequeño en su subárbol derecho) y luego se elimina ese sucesor del subárbol derecho en su lugar.

Al igual que en la inserción, cada ancestro en el camino de regreso vuelve a calcular su altura y factor de equilibrio, aplicando el caso de rotación que corresponda si se desequilibra. La lógica de reequilibrio es idéntica a la de la inserción, solo que la condición para elegir qué caso se aplica ahora observa el factor de equilibrio del hijo pesado en lugar de dónde aterrizó un nuevo valor.

Desafío

Intermedio

Escribe un método delete(value) en AVLTree (un ayudante recursivo funciona bien). Elimina value utilizando la eliminación estándar de BST: para un nodo con dos hijos, reemplaza su valor con el valor más pequeño en su subárbol derecho, luego elimina ese valor del subárbol derecho. No hagas nada si value no se encuentra. Al regresar hacia arriba, vuelve a calcular las alturas y reequilibra exactamente como lo hace insert.

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