Remover

Lição 11 de 16 do curso Árvore AVL - Série de Estruturas de Dados #10 da Coddy.

A exclusão é uma exclusão de BST com o mesmo hábito de rebalanceamento da inserção. Três formas para lidar com o nó que está sendo removido: sem filhos (apenas remova-o), um filho (substitua-o por esse filho) ou dois filhos, o caso complicado, onde você substitui o valor do nó por seu sucessor em ordem (o menor valor em sua subárvore direita) e, em seguida, exclui esse sucessor da subárvore direita.

Assim como na inserção, cada ancestral no caminho de volta recomputa sua altura e fator de equilíbrio, aplicando o caso de rotação que for adequado se ele se tornar desequilibrado. A lógica de rebalanceamento é idêntica à da inserção, apenas a condição para escolher qual caso agora olha para o fator de equilíbrio do filho mais pesado em vez de onde um novo valor caiu.

Desafio

Médio

Escreva um método delete(value) em AVLTree (um auxiliar recursivo funciona bem). Remova value usando a exclusão padrão de BST: para um nó com dois filhos, substitua seu valor pelo menor valor em sua subárvore direita e, em seguida, exclua esse valor da subárvore direita. Não faça nada se value não for encontrado. No caminho de volta para cima, recompute as alturas e rebalanceie exatamente como insert faz.

Experimente você mesmo

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