Vanessa Souza

Universidade Federal de Itajubá – Instituto de Matemática e Computação

Algoritmo e Estrutura de Dados II

COM-112

Aula 10

Remoção - Implementação

É preciso implementar as funções: void atualizaBalRemocao(arvore *no, int num);

void balanceamentoRemocao(arvore *no);

É preciso chamar a função atualizaBalRemocao nas funções removeFolha e removeUmFilho

Remoção - Implementação

void atualizaBalRemocao(arvore *no, int num); Função recursiva que atualiza o FB dos nós da árvore após

uma remoção

Possui 2 critérios de parada Chegou à raiz da árvore

Após o balanceamento encontrou um nó cujo FB seja igual a 1 ou -1

Chama a função balanceamentoRemocao no caso de a árvore ter sofrido desbalanceamento com a remoção

Remoção - Implementação

void balanceamentoRemocao(arvore *no) Função que chama as rotações corretas para rebalancear a

árvore

No caso da remoção, o FB precisa ser ajustado tanto na rotação simples como na dupla

Remoção - Implementação

Exemplo Insira os números abaixo numa árvore AVL

45, 23, 69, 22, 58, 36, 97, 18, 52, 88, 99, 76, 105, 20

Posteriormente remova os números 45 e 58

Remoção - Implementação

void balanceamentoRemocao(arvore *no)