Inserir

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

insert começa como uma inserção comum em árvore binária de busca: percorra comparando valores, vá para a esquerda ou direita, e coloque o novo nó onde um espaço nulo for encontrado (ignore duplicatas). A parte AVL acontece no caminho de volta: após colocar o nó, cada ancestral no caminho recalcula sua height e verifica seu fator de equilíbrio.

Se um nó se tornar desequilibrado, qual lado está pesado e onde o novo valor caiu decidem juntos qual dos quatro casos se aplica: esquerda-esquerda e direita-direita precisam de uma rotação simples, enquanto esquerda-direita e direita-esquerda precisam de duas, uma rotação interna para endireitar o zig-zag seguida pela externa.

Desafio

Médio

Escreva um método insert(value) em AVLTree (um auxiliar recursivo é a maneira mais limpa). Insira value como em uma BST normal, ignorando-o se já estiver presente. No caminho de volta, recalcule a altura e o fator de equilíbrio de cada nó e, se um nó estiver desequilibrado, aplique a rotação correspondente (ou par de rotações) antes de retornar na pilha de chamadas.

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