Aula prática 10: árvores AVL

Esta lista retoma a ABB da prática 9 e exercita o conteúdo da aula de AVL. Use Resposta esperada para comparação e autocorreção, sem entrega ou correção individual. Faça os desenhos no papel ou na ferramenta que preferir. Os exercícios com código pedem trace manual, sem implementar um programa. O tempo estimado inclui tentativa e conferência.

Convenções: os exercícios são independentes. A altura conta níveis: árvore vazia tem altura 0 e folha tem altura 1. O fator de balanceamento é FB = altura da esquerda − altura da direita. Uma AVL mantém a ordem da ABB e FB em {-1, 0, 1} em todos os nós. Isso não exige uma árvore completa nem a menor altura possível.

Cada no_avl guarda chave, altura e os ponteiros de filhos esquerda e direita. O tipo arvore_avl é um ponteiro para nó:

/* Cada nó guarda a chave, a altura da subárvore e os endereços dos dois filhos. */
typedef struct no_avl {
    int chave;
    int altura;
    struct no_avl *esquerda;
    struct no_avl *direita;
} no_avl;

/* O tipo representa um endereço de nó. arvore_avl* aponta para a caixa da raiz. */
typedef no_avl *arvore_avl;

/* Aloca apenas a caixa da raiz e cria uma árvore vazia, como na ABB da aula 9. */
static arvore_avl *criar_avl(void) {
    arvore_avl *arvore = malloc(sizeof(*arvore));
    /* A caixa só pode receber uma raiz vazia quando sua alocação existe. */
    if (arvore == NULL) {
        return NULL;
    }
    *arvore = NULL;
    return arvore;
}

Como na prática 9, arvore_avl *arvore = criar_avl(); aloca a caixa da raiz. arvore aponta para a caixa, *arvore guarda o endereço do primeiro nó e (*arvore)->chave acessa sua chave. arvore == NULL indica falha de criação. Uma caixa válida com *arvore == NULL representa a árvore vazia. Inserção, busca e remoção recebem arvore, como em inserir_avl(arvore, 5).

Nos exercícios de rotação, no_avl *raiz aponta diretamente para a subárvore tratada. A caixa permanece no mesmo endereço durante inserções e remoções, mesmo quando seu conteúdo muda. Ao encerrar, liberar_avl(arvore) libera os nós e a caixa. Depois, o chamador faz arvore = NULL.

h nas figuras representa altura. NULL indica ausência de filho. Os trechos pressupõem <stdlib.h> e <stdbool.h>. bool usa true e false. O operador condição ? valor1 : valor2 escolhe um dos dois valores. Por exemplo, no == NULL ? 0 : no->altura retorna 0 para uma subárvore vazia. const indica um acesso somente para consulta.

Exercício 1: calcular o FB e verificar a árvore inteira

Observe as ligações. As chaves já obedecem à propriedade da ABB.

FB = altura da subárvore esquerda − altura da subárvore direita.

O nível do nó indica sua posição a partir da raiz da árvore, que está no nível 1. A altura da subárvore é a quantidade de nós no maior caminho de sua própria raiz até uma folha. Uma folha tem altura 1 e uma subárvore vazia tem altura 0. Calcule das folhas para os pais: altura do pai = 1 + maior altura entre suas subárvores esquerda e direita.

Calcule a altura e o FB de cada nó. A árvore é AVL? Justifique com os fatores encontrados.

Exercício 2: rastrear uma rotação simples à esquerda

Observe os filhos e as alturas armazenadas antes da chamada.

Faça um trace manual de raiz = rotacionar_esquerda(raiz);, com raiz apontando para 20. Registre as mudanças de ponteiros e alturas e desenhe a árvore resultante.

Apoio em C: altura_no consulta a altura armazenada. atualizar_altura recalcula a altura de um nó a partir dos filhos. rotacionar_esquerda devolve a nova raiz da subárvore.

/* Uma subárvore vazia não acrescenta níveis à altura do pai. */
static int altura_no(const no_avl *no) {
    return no == NULL ? 0 : no->altura;
}

/* Recalcula a altura após atualizar as alturas dos filhos de um nó existente. */
static void atualizar_altura(no_avl *no) {
    const int altura_esquerda = altura_no(no->esquerda);
    const int altura_direita = altura_no(no->direita);
    no->altura = 1 + (altura_esquerda > altura_direita ? altura_esquerda : altura_direita);
}

/* Caso RR: raiz e raiz->direita devem existir. A subárvore intermediária muda de pai. */
static no_avl *rotacionar_esquerda(no_avl *raiz) {
    no_avl *nova_raiz = raiz->direita;
    no_avl *subarvore_transferida = nova_raiz->esquerda;
    nova_raiz->esquerda = raiz;
    raiz->direita = subarvore_transferida;
    atualizar_altura(raiz);
    atualizar_altura(nova_raiz);
    return nova_raiz;
}

Exercício 3: rastrear uma rotação simples à direita

Observe o estado inicial desta outra árvore.

Faça um trace manual de raiz = rotacionar_direita(raiz);, com raiz apontando para 60. Registre as mudanças de ponteiros e alturas e desenhe a árvore resultante. Use também as auxiliares do exercício 2.

Apoio em C:

/* Caso LL: raiz e raiz->esquerda devem existir. A rotação não aloca nem libera nós. */
static no_avl *rotacionar_direita(no_avl *raiz) {
    no_avl *nova_raiz = raiz->esquerda;
    no_avl *subarvore_transferida = nova_raiz->direita;
    /* Preserva a subárvore intermediária antes de substituir a ligação de seu antigo pai. */
    nova_raiz->direita = raiz;
    raiz->esquerda = subarvore_transferida;
    /* Atualiza primeiro o nó rebaixado, pois a altura do promovido depende dele. */
    atualizar_altura(raiz);
    atualizar_altura(nova_raiz);
    return nova_raiz;
}

Exercício 4: rastrear o rebalanceamento de 20

Observe o estado da subárvore que será passada a rebalancear.

Faça um trace manual de raiz = rebalancear(raiz);, com raiz apontando para 20. Registre os fatores consultados, as rotações e o retorno. Desenhe a árvore resultante. Use as rotações dos exercícios 2 e 3.

Apoio em C: fator_balanceamento calcula o FB. rebalancear devolve a raiz corrigida, ou a mesma raiz quando não precisa de rotação. As subárvores dos filhos já devem estar corrigidas antes de tratar o pai.

/* Uma subárvore vazia não acrescenta níveis à altura do pai. */
static int altura_no(const no_avl *no) {
    return no == NULL ? 0 : no->altura;
}

/* Recalcula a altura após atualizar as alturas dos filhos de um nó existente. */
static void atualizar_altura(no_avl *no) {
    const int altura_esquerda = altura_no(no->esquerda);
    const int altura_direita = altura_no(no->direita);
    no->altura = 1 + (altura_esquerda > altura_direita ? altura_esquerda : altura_direita);
}

/* Caso RR: raiz e raiz->direita devem existir. A subárvore intermediária muda de pai. */
static no_avl *rotacionar_esquerda(no_avl *raiz) {
    no_avl *nova_raiz = raiz->direita;
    no_avl *subarvore_transferida = nova_raiz->esquerda;
    nova_raiz->esquerda = raiz;
    raiz->direita = subarvore_transferida;
    atualizar_altura(raiz);
    atualizar_altura(nova_raiz);
    return nova_raiz;
}

/* Caso LL: raiz e raiz->esquerda devem existir. A rotação não aloca nem libera nós. */
static no_avl *rotacionar_direita(no_avl *raiz) {
    no_avl *nova_raiz = raiz->esquerda;
    no_avl *subarvore_transferida = nova_raiz->direita;
    /* Preserva a subárvore intermediária antes de substituir a ligação de seu antigo pai. */
    nova_raiz->direita = raiz;
    raiz->esquerda = subarvore_transferida;
    /* Atualiza primeiro o nó rebaixado, pois a altura do promovido depende dele. */
    atualizar_altura(raiz);
    atualizar_altura(nova_raiz);
    return nova_raiz;
}

/* O fator usa altura da esquerda menos altura da direita, com o sinal adotado na aula. */
static int fator_balanceamento(const no_avl *no) {
    return no == NULL ? 0 : altura_no(no->esquerda) - altura_no(no->direita);
}

/* Restaura uma subárvore após inserir ou remover em uma AVL anteriormente válida. */
static no_avl *rebalancear(no_avl *raiz) {
    /* A remoção de uma folha pode deixar uma subárvore sem altura para atualizar. */
    if (raiz == NULL) {
        return NULL;
    }
    atualizar_altura(raiz);
    const int fator = fator_balanceamento(raiz);

    /* O excesso de altura à esquerda exige uma correção LL ou LR. */
    if (fator > 1) {
        /* O filho inclinado para dentro exige a primeira rotação do caso LR. */
        if (fator_balanceamento(raiz->esquerda) < 0) {
            raiz->esquerda = rotacionar_esquerda(raiz->esquerda);
        }
        return rotacionar_direita(raiz);
    }
    /* O excesso de altura à direita exige uma correção RR ou RL. */
    if (fator < -1) {
        /* O filho inclinado para dentro exige a primeira rotação do caso RL. */
        if (fator_balanceamento(raiz->direita) > 0) {
            raiz->direita = rotacionar_direita(raiz->direita);
        }
        return rotacionar_esquerda(raiz);
    }
    return raiz;
}

Exercício 5: rastrear o rebalanceamento de 80

Observe a subárvore com raiz 80.

Faça um trace manual de raiz = rebalancear(raiz);, com raiz apontando para 80. Registre os fatores consultados, as rotações e o retorno. Desenhe a árvore resultante. Use as funções dos exercícios 2 a 4.

Exercício 6: acompanhar duas inserções consecutivas

Observe a AVL inicial. A caixa da raiz já existe, e *arvore aponta para o nó 50.

Faça o trace manual de inserir_avl(arvore, 5) e, em seguida, inserir_avl(arvore, 2). Para cada chamada, registre o retorno e as atualizações relevantes e desenhe a árvore resultante. Use rebalancear e suas auxiliares dos exercícios 2 a 4.

Apoio em C: o tipo resultado_insercao_avl usa nomes para distinguir os resultados. AVL_INSERIDO significa inserção realizada. Os outros valores indicam duplicata, falta de memória e referência inválida. criar_no_avl cria uma folha, e inserir_no devolve a raiz da subárvore após a tentativa de inserção.

/* Resultados explícitos distinguem duplicata, falta de memória e referência inválida. */
typedef enum {
    AVL_INSERIDO,
    AVL_CHAVE_DUPLICADA,
    AVL_SEM_MEMORIA,
    AVL_ARVORE_INVALIDA
} resultado_insercao_avl;

/* Aloca uma folha. sizeof(*no) mede o nó, e não o ponteiro. */
static no_avl *criar_no_avl(int chave) {
    no_avl *no = malloc(sizeof(*no));
    /* Informa a falha antes de escrever em um endereço inválido. */
    if (no == NULL) {
        return NULL;
    }
    no->chave = chave;
    no->altura = 1;
    no->esquerda = NULL;
    no->direita = NULL;
    return no;
}

/* Desce como em uma ABB e corrige os ancestrais no retorno da recursão. */
static no_avl *inserir_no(no_avl *raiz, int chave, resultado_insercao_avl *resultado) {
    /* Somente uma posição vazia pode receber a nova folha. */
    if (raiz == NULL) {
        no_avl *no = criar_no_avl(chave);
        *resultado = no == NULL ? AVL_SEM_MEMORIA : AVL_INSERIDO;
        return no;
    }
    /* Uma chave já presente não cria outro nó nem altera a árvore. */
    if (chave == raiz->chave) {
        *resultado = AVL_CHAVE_DUPLICADA;
        return raiz;
    }
    /* A ordem da ABB determina o único ramo que pode receber a chave. */
    if (chave < raiz->chave) {
        raiz->esquerda = inserir_no(raiz->esquerda, chave, resultado);
    } else {
        raiz->direita = inserir_no(raiz->direita, chave, resultado);
    }
    /* Uma inserção rejeitada ou sem memória não alterou a subárvore. */
    if (*resultado != AVL_INSERIDO) {
        return raiz;
    }
    return rebalancear(raiz);
}

/* Atualiza o conteúdo da caixa, preservando seu endereço mesmo quando a raiz muda. */
static resultado_insercao_avl inserir_avl(arvore_avl *arvore, int chave) {
    /* Sem caixa, não existe uma posição válida para guardar a raiz. */
    if (arvore == NULL) {
        return AVL_ARVORE_INVALIDA;
    }
    resultado_insercao_avl resultado = AVL_SEM_MEMORIA;
    *arvore = inserir_no(*arvore, chave, &resultado);
    return resultado;
}

Exercício 7: acompanhar uma remoção

Observe a AVL antes da chamada. A caixa da raiz já existe, e *arvore aponta para 40.

Faça um trace manual de remover_avl(arvore, 60). Registre as decisões, as alterações e o retorno. Desenhe a árvore resultante. Use rebalancear e suas auxiliares dos exercícios 2 a 4.

Apoio em C: remover_no devolve a raiz da subárvore após a remoção. Para um nó com dois filhos, este programa copia a chave do sucessor, o menor nó da subárvore direita, e remove sua ocorrência antiga. Essa é a política do complemento C da aula de AVL. A implementação de ABB da prática 9 usa outra política.

/* O nó mais à esquerda contém a menor chave de uma subárvore não vazia. */
static no_avl *no_minimo(no_avl *raiz) {
    no_avl *no = raiz;
    /* Descarta a cada passo os nós que não podem conter a menor chave. */
    while (no->esquerda != NULL) {
        no = no->esquerda;
    }
    return no;
}

/* Remove como em uma ABB e rebalanceia os ancestrais afetados no retorno. */
static no_avl *remover_no(no_avl *raiz, int chave, bool *removido) {
    /* Uma posição vazia comprova que a chave procurada não existe. */
    if (raiz == NULL) {
        return NULL;
    }
    /* A igualdade identifica o nó cuja chave deve sair da árvore. */
    if (chave == raiz->chave) {
        *removido = true;
        /* Preserva o filho direito antes de liberar um nó sem filho esquerdo. */
        if (raiz->esquerda == NULL) {
            no_avl *direita = raiz->direita;
            free(raiz);
            return direita;
        }
        /* O filho esquerdo substitui o nó cuja subárvore direita está vazia. */
        if (raiz->direita == NULL) {
            no_avl *esquerda = raiz->esquerda;
            free(raiz);
            return esquerda;
        }
        no_avl *sucessor = no_minimo(raiz->direita);
        raiz->chave = sucessor->chave;
        bool sucessor_removido = false;
        raiz->direita = remover_no(raiz->direita, sucessor->chave, &sucessor_removido);
    } else {
        /* Sem igualdade, a ordem da ABB seleciona o único ramo possível. */
        if (chave < raiz->chave) {
            raiz->esquerda = remover_no(raiz->esquerda, chave, removido);
        } else {
            raiz->direita = remover_no(raiz->direita, chave, removido);
        }
    }
    /* Uma chave ausente deve preservar a subárvore e seus endereços. */
    if (!*removido) {
        return raiz;
    }
    return rebalancear(raiz);
}

/* Informa se uma chave foi removida. Referência inválida ou chave ausente resulta em false. */
static bool remover_avl(arvore_avl *arvore, int chave) {
    /* Rejeita a referência inválida antes de acessar a árvore. */
    if (arvore == NULL) {
        return false;
    }
    bool removido = false;
    *arvore = remover_no(*arvore, chave, &removido);
    return removido;
}

Exercício 8: continuar a correção nos ancestrais

Observe a AVL inicial. As alturas aparecem nos nós para apoiar o trace.

Faça um trace manual de remover_avl(arvore, 20), com a caixa já criada e *arvore apontando para 50. Registre as decisões, as alterações e o retorno. Desenhe a árvore resultante. Use as funções do exercício 7 e as auxiliares dos exercícios 2 a 4.