Mas por que $lg(n)$???
Primeiramente, $lg$ equivale a $log$ na base 2.
Dado que a AVL é uma árvore balanceada, ela se assemelha muito a uma árvore completa.
Uma árvore completa é uma árvore onde os elementos vão sendo adicionados de cima para baixo, da esquerda para a direita, dessa forma:
É possível notar que a altura dessa árvore vai ser sempre a menor possível.
• O nível 0 tem, no máximo, 1 elemento
• O nível 1 tem, no máximo, 2 elementos
• O nível 2 tem, no máximo, 4 elementos
...
• O nível k tem, no máximo, $2^k$ elementos
Podemos deduzir que, numa árvore de k níveis, o número de nós será, no máximo $2^0 + 2^1 + 2^2 + ... + 2^k$ .
Observemos o seguinte:
$2^0$ em binário é: 0001
$2^1$ em binário é: 0010
$2^2$ em binário é: 0100
$2^3$ em binário é: 1000, etc... se somarmos tudo, obtemos 1111
Note que a próxima potência de 2 (isto é, $2^4$) é 10000, que é equivalente a 1111 + 1.
Logo, $2^0 + 2^1 + 2^2 + ... + 2^h = 2^{k+1} - 1$
Daí tiramos que o número de nós máximo até uma altura k é limitado por $2^{k+1} - 1}
[Obs: não provarei essa sentença porque o foco é na AVL, mas para provar, basta usar indução em k]
Dito isso, dado que a árvore tem n nós, como calcular a altura mínima que ela tem?
Basta tirar o $lg(n)$.
$lg(n)$ equivale à maior potência que podemos elevar o 2 para que ele seja menor ou igual a n. Se temos a potência k de 2, $lg(2^k) = k$.
Dado que temos n, que é o número de nós, chamemos a próxima potência de 2 maior que n de $2^k$.
Sabemos que $2^k - 1$ é o maior número de nós possível de uma árvore de altura k - 1, ou seja, $2^k$ já tem um nível de altura a mais.
$lg(2^k) = k$, porém $lg(2^k - 1) < k$, então arredondamos o resultado para baixo, que resulta na altura correta de uma árvore com n nós!
Suponha uma árvore completa com 5 nós.
A próxima potência de 2 maior que n é $2^3$.
Sabemos que o máximo de nós que essa árvore pode ter é $2^3-1 = 7$.
$lg(2^3) = 3$, mas $lg(2^3 - 1) = lg(7) = 2$, assim como $lg(5) = 2$.
Sabemos como vai ser uma árvore completa com 5 nós, e sua altura de fato é 2.
Dito isso, o número de passos para se procurar um elemento numa árvore completa com 5 nós é igual à altura mais o acesso à raiz, ou seja, &lg(n) + 1$ operações, e $O(lg(n) + 1) = O(lg(n)).
Se a árvore tivesse 4 nós, seria equivalente, pois $lg(4) = 2 também.$.
Se a árvore tivesse 8 nós, a próxima potência de 2 seria 16, $lg(16-1) = 3$, um nível abaixo.
Então, no pior caso, o número de operações para se procurar um nó será 3 (como nos caminhos em verde), que é $lg(n) + 1$.
Agora vamos ao que interessa.
A AVL é uma estrutura semelhante à BST, mas sua estrutura leva em conta uma coisa a mais, o fator de balanceamento (fb). Este é o resultado da diferença entre as alturas da subárvore da esquerda e a subárvore da direita.
Na AVL, a altura é contada de baixo para cima, ou seja, o nó mais alto é a raiz.
Podemos definir a altura de um nó n como:
int H(no* n){ if(n == NULL) return -1; else return 1 + max(H(n->left), H(n->right)); }
Para uma árvore ser AVL, o fb de todos os seus nós deve estar contido em {-1, 0, 1}. Caso contrário, árvore está desbalanceada e não é AVL.
Dito isso, podemos representar um nó assim:
struct no{ int val, altura; no* left, *right; no(){} no(int v){val = v, altura = 0, left = right = NULL;} };
Eis dois exemplos de árvores:
valor dentro do nó indica sua altura, ao lado, seu fb
Podemos ver que a árvore à direita tem um nó cujo fb não está em {-1, 0, 1}, logo essa árvore não é AVL.
INSERÇÃO
A inserção na AVL se faz da quase da mesma forma que numa BST comum, porém com uma diferença.
Pergunta: O que a AVL faz quando a árvore fica desbalanceada após sucessivas inserções?
Resposta: Ela faz rotações.
Como ela está sempre balanceada, quando ocorre uma inserção que o fb de um nó fica 2 ou -2, ela já se corrige.
Não devemos nos preocupar em tratar casos como esse:
Se a árvore for AVL, nunca chegaremos em casos onde o fb de algum nó seja maior que 2 ou menor que -2, e se for 2 ou -2, será necessário fazer alguma rotação.
Existem 4 casos de desbalanceamento:
[1] Esquerda - Esquerda
- fb do nó desbalanceado e do seu filho mais pesado são positivos.
[2] Esquerda - Direita
- fb do nó desbalanceado é positivo e seu filho mais pesado, negativo.
[3] Direita - Direita
- fb do nó desbalanceado e do seu filho mais pesado são negativos.
[4] Direita - Esquerda
- fb do nó desbalanceado é negativo e seu filho mais pesado, positivo.
Para reconhecer os casos, vemos assim:
As soluções são:
[1] Rotação Simples à Direita.
[2] Rotação Dupla à Direita. [RSE no filho + RSD no pai]
[3] Rotação Simples à Esquerda.
[4] Rotação Dupla à Esquerda. [RSD no filho + RSE no pai]
Exemplos:
Inserção de 8, 6 e 5 nessa ordem:
Árvore desbalanceou de forma Esquerda - Esquerda, então aplicamos RSD.
Inserção de 8, 6 e 7 nessa ordem:
fb do nó desbalanceado é positivo, e do filho mais pesado (o da esquerda) é negativo, logo é Esquerda-Direita, e devemos aplicar uma RDD.
RDD faz primeiro uma RSE no filho mais pesado do nó desbalanceado (o da esquerda), para que a árvore fique na configuração de receber uma RSD equivalente à de um desbalanceamento Esquerda - Esquerda.
Vejamos um exemplo mais complicado.
Suponha que temos essa árvore e adicionamos a ela o elemento 14:
A raiz da árvore ficou desbalanceada, mas é só checar qual dos 4 casos.
fb do nó desbalanceado é positivo, e do filho mais pesado (o da esquerda) é negativo, logo é Esquerda-Direita, e devemos aplicar uma RDD.
Primeiro aplicamos uma RSE no filho mais pesado (10) e depois uma RSD no nó desbalanceado (27):
Repare que, na RSE, o filho da esquerda do 15 vira filho da direita do 10, e o 10 vira filho da esquerda do 15. É assim sempre, apenas não era possível visualizar em casos mais simples.
Repare também que, na RSD, o filho da direita do 15 vira filha da esquerda do 27, e o 27 vira filho da direita do 15.
Resumindo, seja N um nó e E e D seus filhos da esquerda e direita:
RSE em N:
• Filho da esquerda de D vira filho da direita de N;
• N vira o filho da esquerda de D;
RSD em N:
• Filho da direita de E vira filho da esquerda de N;
• V vira o filho da direita de E;
Eis a implementação, por enquanto sem as rotações:
struct AVL{ no *root; AVL(){root = NULL;} int H(no *n){return n == NULL? -1 : n->h;} int FB(no *n){return n == NULL? 0 : H(n->left) - H(n->right);} void add(int v){ root = add(root, v); } no *add(no* n, int v){ if(n == NULL) return new no(v); if(v >= n->val) n->right = add(n->right, v); else n->left = add(n->left, v); n->h = 1 + max(H(n->left), H(n->right)); int fb = FB(n); //Esquerda if(fb > 1){ //Esquerda if(v < n->left->val){ return RSD(n); } //Direita else{ n->left = RSE(n->left); return RSD(n); } } //Direita else if(fb < -1){ //Direita if(v > n->right->val){ return RSE(n); } //Esquerda else{ n->right = RSD(n->right); return RSE(n); } } return n; } };
Como a árvore desbalanceou no nó n e depois da inserção de v, podemos usar v para saber, entre os filhos do filho mais pesado de n, qual pesa mais.
Por exemplo, se fb > 1, sabemos que n está desbalanceado e que o filho mais pesado de n é o da esquerda.
Se v é menor que o valor do filho da esquerda de n, significa que o caso é Esquerda-Esquerda, então realizamos uma RSD em n.
Caso contrário, devemos efetuar RDD, isto é, uma RSE no filho mais pesado de n (o da esquerda) e uma RSD em n.
Rotação
Vamos relembrar as rotações simples:
Seja N um nó e E e D seus filhos da esquerda e direita:
RSE em N:
• Filho da esquerda de D vira filho da direita de N;
• N vira o filho da esquerda de D;
RSD em N:
• Filho da direita de E vira filho da esquerda de N;
• V vira o filho da direita de E;
Como as duas funcionam essencialmente da mesma forma, vamos focar na RSE:
Para realizar essas duas operações, temos que guardar apontadores para:
• D
• Filho da esquerda de D
Podemos ver que o E não muda, só o que muda é N->right e D->left.
Se fizermos $D->left = N$, perdemos a referência para a subárvore C, então vamos salvá-la antes (digamos, em b).
Dado que temos ela salva, fazemos $D->left = N$.
Estamos assim:
Agora devemos mudar o filho da direita de N para apontar para C, mas agora nossa referência para C é o b, então fazemos $N->right = b$.
Logo:
Traduzindo isso para código, temos:
no *RSE(no *N){ no *D = N->right; no *b = D->left; D->left = N; N->right = b; //atualiza as alturas N->h = max(H(N->left), H(N->right)) + 1; D->h = max(H(D->left), H(D->right)) + 1; return D; }
Analogamente:
no *RSD(no *N){ no *E = N->left; no *b = E->right; E->right = N; N->left = b; //atualiza as alturas N->h = max(H(N->left), H(N->right))+1; E->h = max(H(E->left), H(E->right))+1; return E; }
A atualização das alturas é feita em tempo constante porque a altura dos filhos dos nós atualizados não muda, apenas seus filhos viram outros, por isso não é necessário descer até as folhas, basta acessar o atributo de altura dos filhos.
Como, no pior caso, precisamos percorrer toda a altura da árvore para realizar a inserção e ainda realizar rotação dupla, a complexidade é $O(lg(n)) + O(RSE) + O(RSD)$, mas as rotações são $O(1)$, logo $O(lg(n)) + O(1) + O(1) = O(lg(n)) + 0 + 0 = O(lg(n))$.
Complexidade da Inserção: O(lg(n))
Em breve, remoção em AVL...
Nenhum comentário:
Postar um comentário