Árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore balanceada (árvore completa) são as árvores que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas. Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação sobre seus nós (inclusão ou exclusão), para ser alcançado um custo de algoritmo com o tempo de pesquisa tendendo a .
As operações de busca, inserção e remoção de elementos possuem complexidade (no qual é o número de elementos da árvore), que são aplicados a árvore de busca binária.
O nome AVL vem de seus criadores soviéticos Adelson Velsky e Landis, e sua primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962.Adel'son-Vel'skiĭ, G. M.; Landis, E. M. (1962), "An algorithm for organization of information", Doklady Akademii Nauk SSSR, 146: 263–266.
Nessa estrutura de dados cada elemento é chamado de nó. Cada nó armazena uma chave e dois ponteiros, uma para a subárvore esquerda e outro para a subárvore direita.
No presente artigo serão apresentados: os conceitos básicos, incluindo uma proposta de estrutura; apresentação das operações busca, inserção e remoção, todas com complexidade .
História Esta estrutura foi criada em 1962 pelos soviéticos Adelson Velsky e Landis que a criaram para que fosse possível inserir e buscar um elemento em tempo c.log (n) operações, onde n é o número de elementos contido na árvore. Tal estrutura foi a primeira árvore binária balanceada criada.Kent, Allen; Williams, James G. (1993), Encyclopedia of Computer Science and Technology: Volume 28 - Supplement 13: AerosPate Applications of Artificial Intelligence to Tree Structures, CRC Press, p. 373, ISBN 9780824722814.
Conceitos básicos Definição thumb|250px|Uma árvore não AVL Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.thumb|250px|Uma árvore AVLPela definição fica estabelecido que todos os nós de uma árvore AVL devem respeitar a seguinte propriedade:
|hd(u) - he(u)| ≤ 1, onde hd(u) é a altura da subárvore direita do nó u e he(u) é a altura da subárvore esquerda do nó u.
O valor hd(u) - he(u) é denominado fator de balanço do nó. Quando um nó possui fator de balanço com valor -1, 0 ou 1 então o mesmo é um nó regulado. Todos os nós de uma árvore AVL são regulados, caso contrário a árvore não é AVL.
Estrutura Proposta de estrutura dos nós de uma árvore AVL básica, com chave do tipo inteiro: tipo No_AVL = registro chave: inteiro; fb: inteiro; // Fator de Balanço esq: ^No_AVL; // aponta subárvore esquerda dir: ^No_AVL; // aponta subárvore direita fim; O campo chave armazena o valor da chave. Os campos esq e dir são ponteiros para as subárvores esquerda e direita, respectivamente. O campo fb armazena o fator de balanço.
Definição da estrutura da árvore:tipo Arvore_AVL = registro raiz: ^No_AVL; // definição de outros campos de interesse fim;
Balanceamento Toda árvore AVL é balanceada, isto é, sua altura é O(log n).
A vantagem do balanceamento é possibilitar que a busca seja de complexidade O(log n). Entretanto, as operações de inserção e remoção devem possuir custo similar. No caso da árvore AVL, a inserção e remoção têm custo O(log n).
Por definição, todos os nós da AVL devem ter fb = -1, 0 ou 1.
Para garantir essa propriedade, a cada inserção ou remoção o fator de balanço deve ser atualizado a partir do pai do nó inserido até a raiz da árvore. Na inserção basta encontrar o primeiro nó desregulado (fb= -2 ou fb= 2), aplicar o operação de rotação necessária, não havendo necessidade de verificar os demais nós. Na remoção a verificação deverá prosseguir até a raiz, podendo requerer mais de uma rotação.
Uma árvore AVL sempre terá um tamanho menor queKnuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. p. 460. ISBN 0-201-89685-0.:
Onde n é o número de elementos da árvore e é a proporção áurea.
Complexidade A árvore AVL tem complexidade para todas operações e ocupa espaço n, onde n é o número de nós da árvore.
+ Complexidade da árvore AVL em notação O Média Pior caso Espaço Busca Inserção Deleção
Operações Busca A busca é a mesma utilizada em árvore binária de busca.
A busca pela chave de valor K inicia sempre pelo nó raiz da árvore.
Seja pt_u um ponteiro para o nó u sendo verificado. Caso o pt_u seja nulo então a busca não foi bem sucedida (K não está na árvore ou árvore vazia). Verificar se a chave K igual pt_u->chave (valor chave armazenado no nó u), então a busca foi bem sucedida. Caso contrário, se K < pt_u->chave então a busca segue pela subárvore esquerda; caso contrário, a busca segue pela subárvore direita.
Algoritmo de buscabusca_AVL(@pt_u:^no_AVL, K:inteiro):logico; inicio se pt_u é NULO então retornar Falso; se K = pt_u->chave então retornar Verdadeiro; senão se K < pt_u->chave então retornar busca_AVL(u->esq, K); senão retornar busca_AVL(u->dir, K); fim. Exemplo de algoritmo de busca em Java.// O método de procura numa AVL é semelhante ao busca binária de uma árvore binária de busca comum. public BSTNode<T> search(T element) { return search(element, this.root); }
// Método auxiliar à recursão. private BSTNode<T> search(T element, BSTNode<T> node) { if (element == null || node.isEmpty()) { return new BSTNode<T>();
if (node.isEmpty() || node.getData().equals(element)) { return node; } else if (node.getData().compareTo(element) > 0) { return search(element, node.getLeft()); } else { return search(element, node.getRight());
Inserção Para inserir um novo nó de valor K em uma árvore AVL é necessária uma busca por K nesta mesma árvore. Após a busca o local correto para a inserção do nó K será em uma subárvore vazia de uma folha da árvore. Depois de inserido o nó, a altura do nó pai e de todos os nós acima deve ser atualizada. Em seguida o algoritmo de rotação simples ou dupla deve ser acionado para o primeiro nó pai desregulado.
Algoritmo recursivo inserir_AVL(@p:^no_AVL, K:inteiro, @mudou_h:logico):logico; var aux: logico; // variável local auxiliar; inicio se p = NULO então inicio // não achou chave, inserir neste local p := novo(no_AVL); // aloca novo nó dinamicamente, diretamente na subárvore do nó pai p^.chave := K; p^.esq := NULO; p^.dir := NULO; mudou_h := Verdadeiro; // sinalizar que a altura da subárvore mudou 1 unidade retornar Verdadeiro; fim; se K < p^.chave então // inserir recursivamente na subárvore esquerda se inserir_AVL(p^.esq, K, mudou_h) então // ocorreu inserção na subárvore esquerda inicio se mudou_h então inicio // mudou altura da subárvore esquerda de p p^.fb := p^.fb - 1; // fator de balanço decrementa 1 unidade caso p^.fb -2: p := rotacao_direita(p); mudou_h := Falso; 0: mudou_h := Falso; // não mudou a altura da subárvore de raiz p // -1: mudou_h := Verdadeiro; // desnecessário pois mudou_h já é Verdadeiro fim retornar Verdadeiro; fim senão se K > p^.chave então // ocorreu inserção na subárvore direita se inserir_AVL(p^.dir, K, mudou_h) então // ocorreu inserção inicio se mudou_h então inicio // mudou altura da subárvore esquerda de p p^.fb := p^.fb + 1; // fator de balanço incrementa 1 unidade caso p^.fb 2: p := rotacao_esquerda(p); mudou_h := Falso; 0: mudou_h := Falso; // não mudou a altura da subárvore de raiz p // 1: mudou_h := Verdadeiro; // desnecessário pois mudou_h já é Verdadeiro fim retornar Verdadeiro; fim retornar Falso; fim. Os parâmetros p e mudou_h são passados por referência. O ponteiro p aponta para o nó atual. O parâmetro mudou_h é do tipo lógico e informa ao chamador se a subárvore apontada por p mudou sua altura.
Como identificar mudança de altura? Considerar que o nó p é raiz da subárvore Tp e houve inserção em uma de suas subárvores.
Caso a subárvore Tp tenha mudado de altura, decrementar fb (inserção na subárvore esquerda) ou incrementar fb (inserção na subárvore direita).
Caso 1: Ao inserir um nó folha, a subárvore Tp passa de altura 0 para altura 1, então Tp mudou de altura.
Caso 2: fb=0 antes da inserção foi alterado para 1 ou -1, então a subárvore Tp mudou de altura.
Caso 3: fb=1 ou -1 antes da inserção, passou a ter valor 0, então a subárvore Tp não mudou de altura.
Caso 4: O fb passou a ter valor -2 ou 2 após a inserção, então há necessidade de aplicação de alguma operação de rotação. Após a rotação, a subárvore Tp terá a mesma altura anterior à inserção.Exemplo de algoritmo de inserção em Java/* Por definição, a árvore AVL é uma árvore binária de busca (BST). * Por este motivo utiliza-se aqui a mesma definição (classe) de Nós que uma BST simples. */ public void insert(T element) { insertAux(element); BSTNode<T> node = search(element); // Pode-se utilizar o mesmo search exemplificado acima. rebalanceUp(node); }
private void insertAux(T element) { if (element == null) return; insert(element, this.root); }
private void insert(T element, BSTNode<T> node) { if (node.isEmpty()) { node.setData(element); node.setLeft(new BSTNode<T>()); node.setRight(new BSTNode<T>()); node.getLeft().setParent(node); node.getRight().setParent(node); } else { if (node.getData().compareTo(element) < 0) { insert(element, node.getRight()); } else if (node.getData().compareTo(element) > 0) { insert(element, node.getLeft());
}Algoritmos de complemento à inserção e/ou algoritmos para identificar desbalanceamento em Javaprotected void rebalanceUp(BSTNode<T> node) { if (node == null || node.isEmpty()) return; rebalance(node); if (node.getParent() != null) { rebalanceUp(node.getParent());
protected int calculateBalance(BSTNode<T> node) { if (node == null || node.isEmpty()) return 0; return height(node.getRight()) - height(node.getLeft()); }
protected void rebalance(BSTNode<T> node) { int balanceOfNode = calculateBalance(node);
if (balanceOfNode < -1) { if (calculateBalance(node.getLeft()) > 0) { leftRotation(node.getLeft());
rightRotation(node); } else if (balanceOfNode > 1) { if (calculateBalance(node.getRight()) < 0) { rightRotation(node.getRight());
leftRotation(node);
}Rotação para Direita e para Esquerda em Javaprotected void leftRotation(BSTNode<T> no) { BTNode<T> noDireito = no.getRight();
no.setRight(noDireito.getLeft());
noDireito.getLeft().setParent(no); noDireito.setLeft(no); noDireito.setParent(no.getParent()); no.setParent(noDireito);
if (no != this.getRoot()) { if (noDireito.getParent().getLeft() == no) { noDireito.getParent().setLeft(noDireito); } else { noDireito.getParent().setRight(noDireito);
} else { this.root = (BSTNode<T>) noDireito;
protected void rightRotation(BSTNode<T> no) { BTNode<T> noEsquerdo = no.getLeft();
no.setLeft(noEsquerdo.getRight());
noEsquerdo.getRight().setParent(no); noEsquerdo.setRight(no); noEsquerdo.setParent(no.getParent()); no.setParent(noEsquerdo);
if (no != this.getRoot()) { if (noEsquerdo.getParent().getLeft() == no) { noEsquerdo.getParent().setLeft(noEsquerdo); } else { noEsquerdo.getParent().setRight(noEsquerdo);
} else { this.root = (BSTNode<T>) noEsquerdo;
Remoção O primeiro passo para remover uma chave K consiste em realizar uma busca binária a partir do nó raiz. Caso a busca encerre em uma subárvore vazia, então a chave não está na árvore e a remoção não pode ser realizada. Caso a busca encerre em um nó u o nó que contenha a chave então a remoção poderá ser realizada da seguinte forma:
Caso 1: O nó u é uma folha da árvore, apenas exclui-lo.
Caso 2: O nó u tem apenas uma subárvore, necessariamente composta de um nó folha, basta apontar o nó pai de u para a única subárvore e excluir o nó u.