Nesta aula vamos aprender como fazer uma inserção em uma Árvore Binária de Busca Balanceada, uma Árvore AVL.
Se você está acompanhando o curso desde o início você vai perceber que a inserção é exatamente igual a inserção em uma árvore binárias de busca sem balanceamento com algumas poucas alterações.
A primeira alteração é que agora não irei criar um novo nó dentro da função de inserção. Quando encontrarmos o ponto de inserção, vamos chamar a função novoNo apresentada nas aulas anteriores. Esta função irá criar um novo nó, preencher seus campos e retornar seu endereço.
No final da função, após o processo de inserção, precisamos agora realizar duas novas ações. Como acabamos de inserir um novo nó na árvore, precisamos checar a altura e o fator de balanceamento dos nós no caminho percorrido até a inserção.
A altura é simples. Basta recalcular a altura de cada nó entre a raiz e o novo nó inserido.
O fator de balanceamento é um pouco mais complicado e, apesar de poder ser feito dentro da função inserir, é altamente recomendado fazer uma função a parte uma vez que a mesma ação será necessária também na função de remoção. Assim, faremos uma nova função chamada balancear que será chamada para cada nó entre a raiz e o novo nó inserido.
/* Insere um novo nó na árvore raiz -> raiz da árvore x -> valor a ser inserido Retorno: endereço do novo nó ou nova raiz após o balanceamento */ No* inserir(No *raiz, int x){ if(raiz == NULL) // árvore vazia return novoNo(x); else{ // inserção será à esquerda ou à direita if(x < raiz->valor) raiz->esquerdo = inserir(raiz->esquerdo, x); else if(x > raiz->valor) raiz->direito = inserir(raiz->direito, x); else printf("\nInsercao nao realizada!\nO elemento %d a existe!\n", x); } // Recalcula a altura de todos os nós entre a raiz e o novo nó inserido raiz->altura = maior(alturaDoNo(raiz->esquerdo), alturaDoNo(raiz->direito)) + 1; // verifica a necessidade de rebalancear a árvore raiz = balancear(raiz); return raiz; }
A função balancear irá calcular o fator de balanceamento para o nó recebido e realizar a rotação adequada quando necessário. Observe que a rotação a ser realizada é encontrada por meio do fator de balanceamento. Se o fb for negativo já sabemos que a árvore está desbalanceada à direita. Então precisamos descobrir se é um caso clássico, pendendo completamente para à direita ou se é direita-esquerda. Para isso basta verificar também o fb da subárvore direita.
Com o fator de balanceamento podemos montar a seguinte tabela.
FB da raiz | FB da subárvore direita | FB da subárvore esquerda | Rotação |
-2 | fb <= 0 | – | Rotação Esquerda |
-2 | fb > 0 | – | Rotação Direita Esquerda |
2 | – | fb >= 0 | Rotação Direita |
2 | – | fb < 0 | Rotação Esquerda Direita |
/* Função para realizar o balanceamento da árvore após uma inserção ou remoção Recebe o nó que está desbalanceado e retorna a nova raiz após o balanceamento */ No* balancear(No *raiz){ short fb = fatorDeBalanceamento(raiz); // Rotação à esquerda if(fb < -1 && fatorDeBalanceamento(raiz->direito) <= 0) raiz = rotacaoEsquerda(raiz); // Rotação à direita else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) >= 0) raiz = rotacaoDireita(raiz); // Rotação dupla à esquerda else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) < 0) raiz = rotacaoEsquerdaDireita(raiz); // Rotação dupla à direita else if(fb < -1 && fatorDeBalanceamento(raiz->direito) > 0) raiz = rotacaoDireitaEsquerda(raiz); return raiz; }