Árvore AVL

Prévia do material em texto

UNIVERSIDADE FEDERAL DO AMAZONAS 
FACULDADE DE TECNOLOGIA 
ENGENHARIA DA COMPUTAÇÃO 
ALGORITMO E ESTRUTURA DE DADOS II 
 
 
 
 
ÁRVORE AVL 
 
 
 
 
 
 
 
 
Manaus – AM 
2014 
1 
 
AMANDA PÊGO DE PAULA - 21354614 
JOELINE DUTRA DA SILVA - 21353194 
REBECA NUNES RODRIGUES - 21350689 
 
 
 
 
 
 
 
 
ÁRVORE AVL 
 
 
 
 
 
 
 
 
 
 
Manaus – AM 
2014 
Esse trabalho foi solicitado 
como forma de obtenção de 
nota parcial para a disciplina 
Algoritmo e Estrutura de Dados 
II, ministrado pelo Prof.º Edson 
Nascimento. 
2 
 
SUMÁRIO 
 
ÍNDICE DE ILUSTRAÇÕES ........................................................................................ 3 
INTRODUÇÃO ............................................................................................................ 5 
1. O QUE É UMA ÁRVORE AVL ................................................................................. 6 
2. FATOR DE BALANCEAMENTO ............................................................................. 7 
3. ESTRUTURA DE DADOS ....................................................................................... 9 
4. ROTAÇÕES .......................................................................................................... 11 
4.1. Rotação simples para a direita ........................................................................ 11 
4.1.1. Como funciona .......................................................................................... 11 
4.1.2. Passo a passo .......................................................................................... 12 
4.2. Rotação simples para a esquerda ................................................................... 14 
4.2.1. Como funciona .......................................................................................... 14 
4.2.2. Passo a passo .......................................................................................... 15 
4.3. Rotação dupla direita-esquerda ...................................................................... 17 
4.3.1. Como funciona .......................................................................................... 17 
4.3.2. Passo a passo .......................................................................................... 18 
4.4. Rotação dupla esquerda-direita ...................................................................... 21 
4.3.1. Como funciona .......................................................................................... 21 
4.3.2. Passo a passo .......................................................................................... 22 
5. BUSCA EM UMA ÁRVORE AVL ........................................................................... 26 
6. INSERÇÃO EM UMA ÁRVORE AVL .................................................................... 27 
7. REMOÇÃO EM UMA ÁRVORE AVL ..................................................................... 29 
8. IMPRESSÃO EM UMA ÁRVORE AVL .................................................................. 30 
8.1. Imprimir todas as chaves ................................................................................ 30 
8.2. Imprimir em ordem crescente.......................................................................... 30 
8.3. Imprimir em ordem decrescente ...................................................................... 31 
CONCLUSÃO ............................................................................................................ 32 
REFERÊNCIAS ......................................................................................................... 33 
 
3 
 
ÍNDICE DE ILUSTRAÇÕES 
 
Figura 1: Árvore AVL com lado esquerdo maior.......................................................... 7 
Figura 2: Árvore AVL com lado direito maior. .............................................................. 7 
Figura 3: Árvores AVL desbalanceadas. ..................................................................... 8 
Figura 4: Inserção em AVL e FB após a inserção. .................................................... 11 
Figura 5: Rotação simples para direita na AVL. ........................................................ 12 
Figura 6: Passo 1 da rotação para direita. ................................................................ 12 
Figura 7: Passo 2 da rotação para direita. ................................................................ 12 
Figura 8: Passo 3 da rotação para direita. ................................................................ 13 
Figura 9: Passo 4 da rotação para direita. ................................................................ 13 
Figura 10: Antes e depois da rotação para direita. .................................................... 14 
Figura 11: Inserção em AVL e FB. ............................................................................ 14 
Figura 12: Rotação simples para esquerda na AVL. ................................................. 15 
Figura 13: Passo 1 da rotação para esquerda. ......................................................... 15 
Figura 14: Passo 2 da rotação para esquerda. ......................................................... 15 
Figura 15: Passo 3 da rotação para esquerda. ......................................................... 16 
Figura 16: Passo 4 da rotação para esquerda. ......................................................... 16 
Figura 17: Antes e depois da rotação para esquerda. ............................................... 17 
Figura 18: Inserção em AVL e FB. ............................................................................ 17 
Figura 19: Primeira parte da rotação dupla Direita-Esquerda - Rotação à esquerda.
 .................................................................................................................................. 18 
Figura 20: Segunda parte da rotação dupla Direita-Esquerda - Rotação à direita .... 18 
Figura 21: Passo 1 da rotação Direita-Esquerda. ...................................................... 18 
Figura 22: Passo 2 da rotação Direita-Esquerda. ...................................................... 19 
Figura 23: Passo 3 da rotação Direita-Esquerda. ...................................................... 19 
Figura 24: Passo 4 da rotação Direita-Esquerda. ...................................................... 19 
Figura 25: Passo 5 da rotação Direita-Esquerda. ...................................................... 20 
Figura 26: Passo 6 da rotação Direita-Esquerda. ...................................................... 20 
Figura 27: Antes e depois da rotação dupla Direita-Esquerda. ................................. 21 
Figura 28: Inserção em AVL e FB. ............................................................................ 21 
Figura 29: Primeira parte da rotação dupla Esquerda-Direita - Rotação à direita. .... 22 
4 
 
Figura 30: Segunda parte da rotação dupla Esquerda-Direita - Rotação à esquerda.
 .................................................................................................................................. 22 
Figura 31: Passo 1 da rotação Esquerda-Direita. ...................................................... 22 
Figura 32: Passo 2 da rotação Esquerda-Direita. ...................................................... 23 
Figura 33: Passo 3 da rotação Esquerda-Direita. ...................................................... 23 
Figura 34: Passo 4 da rotação Esquerda-Direita. ...................................................... 23 
Figura 35: Passo 5 da rotação Esquerda-Direita. ...................................................... 24 
Figura 36: Passo 6 da rotação Esquerda-Direita....................................................... 24 
Figura 37: Antes e depois da rotação dupla Esquerda-Direita. ................................. 25 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5 
 
INTRODUÇÃO 
 
 Eficiência é algo que todos procuram em algoritmos, porém não é algo fácil de 
obter. Às vezes, um código eficiente para busca pode ter um tempo muito alto na 
hora de remover um item. A árvore binária de busca (ABB) é eficiente na busca, mas 
conforme dados vão sendo inseridos e/ou removidos, seu sistema de busca acaba 
não sendo tão eficiente quanto em uma árvore binária considerada equilibrada. 
 Uma árvore equilibrada tem o tamanho do lado esquerdo e lado direito, a 
partir de sua raiz, muito parecidos. Para que a ABB fique equilibrada, é necessário 
um balanceamento estático: criar uma nova árvore e inserir os dados da árvore 
desequilibrada e então apaga-la. Todo esse processo custa muito tempo. 
 A árvore de Adelson-Velsky e Landis (AVL) propõe uma mudança às árvores 
estáticas. Elas são árvores dinâmicas, ou seja, o seu balanceamento (a busca por 
seu equilibrio) é feito dentro da árvore após a inserção ou remoção de dados. 
 
 
 
 
 
 
 
 
 
 
 
6 
 
1. O QUE É UMA ÁRVORE AVL 
 
Os matemáticos soviéticos Georgy Adelson-Velsky e Evgenii Landis 
publicaram em “Algoritmos para organização de informação”, em 1962, a proposta 
de uma árvore que fosse balanceada dinamicamente. 
Essa árvore, conforme dados fossem inseridos e removidos, iria se balancear 
automaticamente. Com isso, a árvore sempre teria uma complexidade baixa. 
O fator principal da AVL é o balanceamento, que traz equilíbrio a árvore. Se 
ela está maior para um lado do que para o outro, dependendo de seu tipo, pode não 
estar em equilíbrio. O balanceamento é feito por rotações, que podem ser simples 
ou duplas, para a direita ou para a esquerda. 
A complexidade da árvore AVL, em notação O, é: 
 Média Pior Caso 
Espaço n n 
Busca Log n Log n 
Inserção Log n Log n 
Remoção Log n Log n 
Tabela 1: Complexidade da AVL em notação O. 
 
 
 
 
 
 
 
 
 
7 
 
2. FATOR DE BALANCEAMENTO 
 
O fator de balanceamento é o que o computador utiliza para verificar o nível de 
equilíbrio da árvore AVL. Enquanto para nós é algo visual, a máquina apenas 
processa dados, logo o fator de balanceamento se torna necessário. 
Para ser considerada uma árvore AVL equilibrada, o fator de balanceamento tem 
que ser 1, 0 ou -1. Ao inserir um dado, ele se torna uma folha, cujo fator de 
balanceamento é sempre 0. 
Para calcular o fator de balanceamento, é necessário saber a altura da sub-
árvore esquerda (sae) e da sub-árvore direita (sad). O fator pode ser calculado de 
duas maneiras: 
 FB = h(sad)-h(sae) 
 
Figura 1: Árvore AVL com lado esquerdo maior. 
 
 FB = h(sae)-h(sad) 
 
 
 
 
 
0 
-1 
+1 
0 
Figura 2: Árvore AVL com lado direito maior. 
8 
 
Uma árvore AVL desequilibrada, ou desbalanceada, irá ter o fator de 
balanceamento menor que -1 ou maior que 1, como nos exemplos abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
0 
+2 
+2 
-1 
0 
-2 
-4 
-2 
0 
-1 
0 
Figura 3: Árvores AVL desbalanceadas. 
9 
 
3. ESTRUTURA DE DADOS 
 
A estrutura de uma arvore AVL é bem semelhante a estrutura de uma arvore 
binária de busca. As diferenças ficam por conta das informações que contribuirão 
para que a arvore passe por balenceamento. Assim, um nó de uma AVL pode ser: 
typedef struct no { 
int chave; 
int fb; 
struct no *Pai; //Opcional 
struct no *FilhoEsquerdo; 
struct no*FilhoDireito; 
} no; 
 
Onde fb representa a variável que armazena o valor do fator de 
balanceamento do nó. 
Outra forma de implementar esta estrutura é: 
typedef struct arvore{ 
int info; 
struct arvore *dir, *esq; 
int altura; //Altura máxima entre a altura das sub-árvores esquerda e 
direita 
}AVL; 
 
10 
 
A altura da maior das sub-árvores é declarada na estrutura, de forma que o 
fator de balanceamento é calculado a partir dessas informações e não precisa ser 
constantemente atualizado dentro da própria estrutura. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
11 
 
4. ROTAÇÕES 
 
Rotações são as operações que permitem o rebalanceamento das árvores 
AVL. As rotações alteram a posição dos nós envolvidos em seu processo. Existem 
quatro tipos de rotação: 
 Rotação simples à direita 
 Rotação simples à esquerda 
 Rotação dupla à esquerda ou rotação direita-esquerda 
 Rotação dupla à direita ou rotação esquerda-direita 
 
4.1. Rotação simples para a direita 
 
4.1.1. Como funciona 
 
 Abaixo se percebe uma situação em que uma árvore balanceada recebe um 
novo nó. Ocorre desbalanceamento para o nó C cujo fator de balanceamento passa 
de -1 para -2, sendo necessário uma rotação. 
 Sabe-se que a rotação deve ser para a direita, pois o ramo mais pesado da 
árvore é o esquerdo como indica o sinal negativo do FB de C. 
 
 
Figura 4: Inserção em AVL e FB após a inserção. 
 
Insere a 
a 
c 
b 
FB(a)=0 
FB(b)=-1 
FB(c)=-2 
c 
b 
12 
 
Balanceando: 
 
Figura 5: Rotação simples para direita na AVL. 
 
 A rotação torna B o pai de A e C e balanceia a árvore. 
4.1.2. Passo a passo 
 
 
 
Endereços de B e C são guardados em 
variáveis auxiliares. Note que os filhos esquerdos de 
B e C apontam para NULO. 
 
 
 
 
O filho esquerdo de C passa a receber o filho 
direito de B. 
 
 
c a 
b 
a 
c 
b Rotaciona 
FB(a)=0 
FB(c)=0 
FB(b)=0 
a 
c 
b 
AuxC 
AuxB 
a 
c 
b 
AuxC 
AuxB 
Figura 6: Passo 1 da rotação 
para direita. 
Figura 7: Passo 2 da rotação para 
direita. 
13 
 
 
 
 
O filho direito de B passa a ser C. 
 
 
 
 
 
 
O AuxC que indica início da árvore 
aponta para B. 
B agora é raiz. 
 
 
 
Em linhas gerais, a partir do exemplo tem-se o pseudocódigo: 
 Ap = P; //Pai é guardado em variável que indica raiz da árvore 
 Af = Ap->FilhoEsquerdo; //(F) Filho Esquerdo é guardado em variável auxiliar 
 Ap->FilhoEsquerdo = Af->FilhoDireito; 
 Af->FilhoDireito = Ap; //Pai torna-se filho 
 Ap = Af; //Filho torna-se raiz da árvore 
 
a 
c 
b 
AuxC 
AuxB 
a c 
b 
AuxC 
AuxB 
Figura 8: Passo 3 da rotação para 
direita. 
Figura 9: Passo 4 da rotação para direita. 
14 
 
 
Figura 10: Antes e depois da rotação para direita. 
 
 
4.2. Rotação simples para a esquerda 
 
4.2.1. Como funciona 
 
 Assim como no exemplo para Rotação simples, na imagem abaixo ocorre o 
desbalanceamento da árvore após a inserção de um elemento. 
 Neste caso a rotação deve ser para a esquerda, pois o ramo mais pesado da 
árvore é o direito como indica o sinal positivo do FB de A. 
 
 
Figura 11: Inserção em AVL e FB. 
 
Balanceando: 
P 
F 
 
P 
F 
 
 
a 
b 
Insere c 
c 
a 
b 
FB(c)=0 
FB(b)=+1 
FB(a)=+2 
15 
 
 
Figura 12: Rotação simples para esquerda na AVL. 
 
 A árvore fica balanceada com a rotação. 
 
4.2.2. Passo a passo 
 
 
O primeiro passo é o mesmo do da rotação para 
a direita: endereços de B e C são guardados em 
variáveis auxiliares. 
 
 
 
 
 
 
 
O filho direito de A passa a receber o filho 
esquerdo de B.c a 
b 
c 
a 
b Rotaciona 
FB(a)=0 
FB(c)=0 
FB(b)=0 
c 
a 
b 
AuxB 
AuxA 
c 
a b 
AuxB AuxA 
Figura 13: Passo 1 da rotação para 
esquerda. 
Figura 14: Passo 2 da rotação 
para esquerda. 
16 
 
 
 
O filho esquerdo de B passa a ser A. 
 
 
 
 
 
 
 
O AuxA que indica início da árvore aponta 
para B. 
B agora é raiz. 
 
 
 
 
 
O pseudocódigo para rotação à esquerda é então: 
 Ap = P; 
 Af = Ap->FilhoDireito; //(F) 
 Ap->FilhoDireito= Af->FilhoEsquerdo; 
 Af->FilhoEsquerdo = Ap; 
 Ap = Af; 
c 
a b 
AuxB AuxA 
 
c a 
b 
AuxB AuxA 
Figura 15: Passo 3 da rotação para 
esquerda. 
Figura 16: Passo 4 da rotação para 
esquerda. 
17 
 
 
Figura 17: Antes e depois da rotação para esquerda. 
 
4.3. Rotação dupla direita-esquerda 
 
4.3.1. Como funciona 
 
 A inserção de B desbalanceia a árvore tornando o ramo esquerdo mais 
pesado. 
 Desta vez, a rotação da sub-árvore(filho) deve ser à esquerda. Abaixo, pode-
se ver que em relação a A, o ramo direito pesa mais. A rotação seguinte, aplicada à 
árvore (pai), deve ser à direita. 
 
 
Figura 18: Inserção em AVL e FB. 
 
O primeiro passo do balanceamento é a rotação à esquerda da sub-árvore: 
 
P 
F 
 
P 
F 
 
 
Insere b 
FB(b)=0 
FB(a)=+1 
FB(c)=-2 
c 
a 
b 
c 
a 
18 
 
 
Figura 19: Primeira parte da rotação dupla Direita-Esquerda - Rotação à esquerda. 
Tem-se então uma árvore como a vista em rotação para a direita: 
 
Figura 20: Segunda parte da rotação dupla Direita-Esquerda - Rotação à direita 
A árvore está então balanceada com B por raiz. 
 
4.3.2. Passo a passo 
 
 
 
Variáveis guardam os endereços de C 
(pai), A (filho) e B (neto). 
 
 
 
 
FB(c)=0 
FB(b)=-1 
FB(a)=-2 
b 
a 
a 
b 
Resultando 
Rotação para 
a esquerda 
a 
c 
b 
c a 
b 
Rotação 
para a 
direita 
FB(a)=0 
FB(c)=0 
FB(b)=0 
a 
c 
b 
b 
c 
a 
AuxC 
AuxA 
AuxB 
Figura 21: Passo 1 da rotação Direita-
Esquerda. 
19 
 
 
 
Filho direito de A aponta para filho 
esquerdo de B. 
 
 
 
 
 
 
 
 
Filho direito de B aponta para A. 
 
 
 
 
 
 
Filho direito de C aponta para 
filho esquerdo de B. 
 
 
 
b 
c 
a 
AuxC 
AuxA 
AuxB 
b 
c 
a 
AuxC 
AuxA 
AuxB 
 
b 
c 
a 
AuxC 
AuxA AuxB 
 
Figura 22: Passo 2 da rotação Direita-
Esquerda. 
Figura 23: Passo 3 da rotação Direita-
Esquerda. 
Figura 24: Passo 4 da rotação Direita-Esquerda. 
20 
 
 
 
 
Filho esquerdo de B passa a 
ser C. 
 
 
 
 
 
 
O AuxA que indica início da árvore 
aponta para B. 
B agora é raiz. 
 
 
 
Pseudocódigo: 
 Ap = P; 
 Af = Ap->FilhoEsquerdo; //(F) 
 An = Af->FilhoDireito; //(N) 
 Af->FilhoDireito = An->FilhoEsquerdo; 
 An->FilhoEsquerdo = Af; 
 Ap->FilhoEsquerdo = An->FilhoDireito; 
 An->FilhoDireito = Ap; 
 Ap = An; 
b 
c 
a 
AuxC 
AuxA 
AuxB 
b 
c a 
AuxC 
AuxA 
AuxB 
Figura 25: Passo 5 da rotação Direita-Esquerda. 
Figura 26: Passo 6 da rotação Direita-
Esquerda. 
21 
 
 
Figura 27: Antes e depois da rotação dupla Direita-Esquerda. 
 
4.4. Rotação dupla esquerda-direita 
 
4.3.1. Como funciona 
 
 A inserção de B desbalanceia a árvore tornando o ramo direito mais pesado. 
 Repare que o fator de balanceamento da árvore tem sinal oposto ao da sub-
árvore (filho), isto indica rotação dupla. 
 A rotação dupla trata-se de duas rotações seguidas de sentido oposto. A 
primeira rotação aplicada à sub-árvore e a segunda à árvore. 
 A rotação da sub-árvore(filho) deve ser à direita. No exemplo a seguir, pode-
se ver que em relação a C, o ramo esquerdo pesa mais. 
 A rotação seguinte, aplicada à árvore, deve ser à esquerda. 
 
Figura 28: Inserção em AVL e FB. 
 O primeiro passo do balanceamento é a rotação à direita da sub-árvore: 
N 
P 
F 
 
 
 
N 
P F 
 
a 
c 
Insere b 
b 
a 
c 
FB(b)=0 
FB(c)=-1 
FB(a)=+2 
22 
 
 
Figura 29: Primeira parte da rotação dupla Esquerda-Direita - Rotação à direita. 
 
Tem-se então uma árvore como a vista em rotação para à esquerda: 
 
Figura 30: Segunda parte da rotação dupla Esquerda-Direita - Rotação à esquerda. 
 
A árvore está então balanceada com B por raiz. 
 
4.3.2. Passo a passo 
 
 
 
Variáveis guardam os endereços de A 
(pai), C (filho) e B (neto). 
 
FB(c)=0 
FB(b)=+1 
FB(a)=+2 
c 
b 
b 
c 
Resultando 
c 
a 
b Rotação para 
a direita 
c a 
b 
c 
a 
b 
Rotação 
para 
esquerda 
FB(a)=0 
FB(c)=0 
FB(b)=0 
b 
a 
c 
AuxC AuxA 
AuxB 
Figura 31: Passo 1 da rotação Esquerda-
Direita. 
23 
 
 
 
Filho esquerdo de C aponta para filho 
direito de B. 
 
 
 
 
 
 
Filho direito de B aponta para C. 
 
 
 
 
 
 
 
Filho direito de A aponta para filho 
esquerdo de B. 
 
 
 
b 
a 
c 
AuxC AuxA 
AuxB 
b 
a 
c 
AuxC AuxA 
AuxB 
 
b 
a 
c 
AuxC 
AuxA 
AuxB 
 
Figura 32: Passo 2 da rotação 
Esquerda-Direita. 
Figura 33: Passo 3 da rotação Esquerda-
Direita. 
Figura 34: Passo 4 da rotação Esquerda-
Direita. 
24 
 
 
 
Filho esquerdo de B passa a ser A. 
 
 
 
 
 
 
O AuxA que indica início da árvore 
aponta para B. 
B agora é raiz. 
 
 
 
Pseudocódigo: 
 Ap = P; 
 Af = Ap->FilhoDireito; (F) 
 An = Af->FilhoEsquerdo; (N) 
 Af->FilhoEsquerdo = An->FilhoDireito; 
 An->FilhoDireito = Af; 
 Ap->FilhoDireito = An->FilhoEsquerdo; 
b 
a c 
AuxC 
AuxA 
AuxB 
b 
a c 
AuxC 
AuxA 
AuxB 
Figura 35: Passo 5 da rotação Esquerda-
Direita. 
Figura 36: Passo 6 da rotação Esquerda-
Direita. 
25 
 
 An->FilhoEsquerdo = Ap; 
 Ap = An; 
 
 
 
Figura 37: Antes e depois da rotação dupla Esquerda-Direita. 
 
 
 
 
 
 
 
 
 
 
 
 
 
N 
P 
F 
 
 
 
N 
P F 
 
26 
 
5. BUSCA EM UMA ÁRVORE AVL 
 
A Busca em uma AVL ocorre tal qual em uma Árvore Binária de Busca. A 
razão disto é que a busca não dependerá da Altura da árvore. Uma árvore binária de 
busca T é uma árvore de decisão, onde a pergunta feita ao nó v é se a chave k é 
menor, igual ou maior que a chave armazenada v. O pseudocódigo ficaria como: 
Algoritmo BuscaArvore (k,v): 
Entrada: Uma chave de busca k e um nó v de uma arvore binária de busca T. 
Saída: Um nó w da subarvore T(v) da raiz T em v, tal que w é um nó interno 
que armazena k ou w é um nó externo encontrado na travessia InOrder de T(v) 
depois de todos os nós internos com chaves menores que k e antes de todos os nós 
internos com chaves maiores que k. 
IF v é um nó externo então 
 Retorne v 
IF k = chave (v) então 
 Retorne v 
Senão, se k<chave(v) então 
 Retorne BuscaArvore (k,T.FilhoEsquerdo (v)) 
Senão 
 // ocorre {k > chave (v)} 
 Retorne BuscaArvore (k, T.FilhoDireito (v)) 
 
 
 
27 
 
6. INSERÇÃO EM UMA ÁRVORE AVL 
 
Inserção em uma árvore AVL deve ser dada pela inserção do nodo seguida 
de uma verificação na propriedade do fator de balanceamento. Caso não obedeça a 
essa propriedade, deve-se fazer uma rotação conveniente. 
Suponha que uma árvore T é AVL e que um novo nó X seja inserido em T 
causando um desbalanceamentona árvore. A fim de mantermos a árvore T como 
AVL, precisamos de um rebalanceamento dos nós. Este rebalanceamento é 
realizado através de rotações no primeiro ancestral de X cujo fator de 
balanceamento torna-se ±2. Seja A o primeiro ancestral de X cujo fator de 
balanceamento torna-se ±2 após a inclusão de um novo elemento. 
 Rotação (LL): O novo nó X é inserido na sub-árvore da esquerda do filho 
esquerdo de A; 
 Rotação (LR): X é inserido na sub-árvore da direita do filho esquerdo de A; 
 Rotação (RR): X é inserido na sub-árvore da direita do filho direito de A; 
 Rotação (RL): X é inserido na sub-árvore da esquerda do filho direito de A. 
 
Para inserir um nó X em uma árvore AVL, basta os seguintes passos: 
1. Inserir X na árvore AVL usando o mesmo algoritmo de inserção de um nó em 
uma árvore de busca binária. Recursivamente, empilhar cada nó que é 
visitado a partir do nó raiz até X, exceto o próprio X; 
2. Verificar se a pilha está vazia: 
 Se sim, o algoritmo termina. 
 Senão, seguir para o passo (3). 
3. Desempilhar um nó e verificar se a diferença de altura entre a sub-árvore da 
esquerda e da direita desse nó é maior que 1. 
 Se sim, voltar para o passo (2). 
28 
 
 Senão, será necessário rotacionar os nós. Depois de realizada a rotação, 
o algoritmo termina. 
 
Nota-se que a operação de inclusão pode ser realizada em tempo O(lg(n)). 
Após as rotações, a árvore possui a mesma altura que antes da inclusão do novo 
elemento, logo os fatores de balanceamento dos elementos que não estão 
envolvidos nas rotações não mudam. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
29 
 
7. REMOÇÃO EM UMA ÁRVORE AVL 
 
A remoção deve ser dada por uma rotação em torno do nó a ser removido, a 
fim de torná-lo folha para que então possa ser removido. Em alguns casos, após a 
remoção são necessárias rotações para ajustar o fator de balanceamento. 
Para remover um nó s de uma árvore AVL, basta seguir os seguintes passos: 
1. Remover X da árvore AVL usando o mesmo algoritmo de remoção de um nó 
em uma árvore de busca binária. Recursivamente, empilhar cada nó que é 
visitado a partir do nó raiz até o nó X, incluindo-o; 
2. Verificar se a pilha está vazia 
 Se sim, o algoritmo termina. 
 Senão, seguir para o passo (3). 
3. Desempilhar um nó e verificar se a diferença de altura entre a sub-árvore da 
esquerda e da direita desse nó é maior que 1. 
 Se sim, será necessário rotacionar os nós. Dependendo do tipo de rotação 
realizada, o algoritmo pode não terminar aqui. Se ele não terminar, voltar 
para o passo (2). 
 Senão, vá para o passo (2). 
 
Nota-se que a operação de remoção pode ser realizada em tempo O(lg(n)). 
Na remoção de um elemento em uma árvore AVL, pode haver a necessidade de 
realizar mais de duas rotações (o que não acontece na inserção), podendo se 
estender para uma rotação em cada nível (O(log(n))) no pior caso. 
 
 
 
30 
 
8. IMPRESSÃO EM UMA ÁRVORE AVL 
 
 Tal qual a busca, na árvore AVL o método para impressão dos dados é o 
mesmo de uma Árvore Binária de Busca. 
 
8.1. Imprimir todas as chaves 
 
Algoritmo Imprime(*R): 
Entrada: referência de uma árvore AVL R. 
Saída: Trata-se um procedimento. Serão impressos todos os nós em Pré-
Ordem, ou seja, primeiro a raiz e depois as subárvores. Outra forma de expressar a 
ordem de processamento dos nós pode ser: r-e-d (raiz, subárvore esquerda, 
subárvores direita). 
IF R é diferente de NULL então 
 Escreve (R.chave) //imprime a chave da raiz com printf, por exemplo 
 Imprime (R.FilhoEsquerdo) //imprime chaves da subárvore esquerda 
 Imprime (R.FilhoDireito) // imprime chaves da subárvore direita 
 
8.2. Imprimir em ordem crescente 
 
Algoritmo Imprime(*R): 
Entrada: referência de uma árvore AVL R. 
Saída: Trata-se um procedimento. Serão impressas primeiramente todas as 
chaves da subárvore esquerda, depois a chave da raiz, e por fim as chaves da 
subárvore direita. Este tipo de percurso dos nós de uma árvore se chama In-Ordem, 
ou seja, raiz no meio (in) das subárvores. 
31 
 
IF R é diferente de NULL então 
 Imprime (R.FilhoEsquerdo) //imprime chaves da subárvore esquerda 
Escreve (R.chave) //imprime a chave da raiz com printf, por exemplo 
 Imprime (R.FilhoDireito) // imprime chaves da subárvore direita 
 
8.3. Imprimir em ordem decrescente 
 
Algoritmo Imprime(*R): 
Entrada: referência de uma árvore AVL R. 
Saída: Trata-se de um procedimento. Serão impressas primeiramente todas 
as chaves da subárvore direita, depois a chave da raiz e depois as chaves da 
subárvore esquerda. 
IF R é diferente de NULL então 
 Imprime (R.FilhoDireito) // imprime chaves da subárvore direita 
Escreve (R.chave) //imprime a chave da raiz com printf, por exemplo 
Imprime (R.FilhoEsquerdo) //imprime chaves da subárvore esquerda 
 
 
 
 
 
 
 
 
32 
 
CONCLUSÃO 
 
A árvore AVL é considerada uma das mais eficientes, em questão da 
complexidade, quando comparada a outros tipos de árvores. São utilizadas em 
redes de comunicação e na codificação para compactação de arquivos. 
Nas redes de comunicação, os dados são fragmentados e enviados várias 
vezes. Pode ocorrer do pacote de dados não chegar inteiro ao destino ou de ter 
dados que já foram recebidos. Por utilizar uma árvore binária, é fácil pesquisar e ter 
acesso aos dados recebidos e inseri-los a lista. Ao utilizar uma AVL, fica garantida 
uma maior rapidez ao acesso de dados. 
A principal codificação que utiliza conceitos de árvores binárias é conhecida 
como Algoritmo de Huffman, que armazena letras e a quantidade delas. Com a 
árvore binária fica fácil diminuir a quantidade antes necessária do arquivo. 
Mas ainda assim, a árvore AVL pode acabar sendo custosa devido à 
necessidade de rotações para o balanceamento da árvore. Quando maior for a 
árvore, mais rotações serão necessárias para poder chegar ao ponto de remover um 
dado, e ainda mais rotações para equilibrá-la novamente. 
 
 
 
 
 
 
 
 
 
33 
 
REFERÊNCIAS 
 
ANDRADE, Lívia. Árvores AVL. Disponível em: 
http://www.passeidireto.com/arquivo/1012626/aula-5_arvore-avl. Acesso em 14 de 
Junho de 2014. 
BORGES, Henrique. Algoritmo de Huffman. Disponível em: 
http://www.youtube.com/watch?v=2yWfo50jZiw. Acesso em 14 de Junho de 2014. 
BUENO, Letícia. Árvores AVL. Disponível em: 
http://professor.ufabc.edu.br/~leticia.bueno/classes/aed2/materiais/avl.pdf. Acesso 
em 14 de Junho de 2014. 
COSTA, Jean. Algoritmo de Huffman. Disponível em: 
http://www.youtube.com/watch?v=MXI4LWgDucA. Acesso em 14 de Junho de 2014. 
DUTRA, Caio. Árvore Binária AVL. Disponível em: 
http://www.vivaolinux.com.br/script/Arvore-binaria-AVL. Acesso em 14 de Junho de 
2014. 
FERRARI, Roberto. Estruturas de dados – Unidade 16: Árvores Binárias de 
Busca – Parte 1. Disponível em: http://www2.dc.ufscar.br/~bsi/materiais/ed/u16.html. 
Acesso em: 24 de Junho de 2014. 
HARGROVE, John. The AVL Tree Rotations Tutorial. Disponível em: 
http://pages.cs.wisc.edu/~paton/readings/liblitVersion/AVL-Tree-Rotations.pdf. 
Acesso em 14 de Junho de 2014. 
KRUSE, Robert; RYBA, Alex. Data Structures and Program Design in C++. 
Section 10.4, Height Balance: AVL tree. Disponível em: 
http://cs.gmu.edu/~setia/cs310/slides/avl.pdf. Acesso em 18 de Junho de 2014. 
MORRIS, John. AVL trees. Disponível em: 
https://www.cs.auckland.ac.nz/software/AlgAnim/AVL.html. Acesso em 14 de Junho 
de 2014. 
34 
 
NASCIMENTO, Edson. Árvore AVL. Disponível em: 
http://colabweb.ufam.edu.br/pluginfile.php/14107/mod_resource/content/3/aed2_10_
Arvore%20AVL.pdf.Acesso em 14 de Junho de 2014. 
NONATO, Luiz. Algoritmo de Inserção. Disponível em: 
http://www.lcad.icmc.usp.br/~nonato/ED/AVL/insercao.html. Acesso em: 24 de Junho 
de 2014. 
NONATO, Luiz. Implementação da Remoção. Disponível em: 
http://www.lcad.icmc.usp.br/~nonato/ED/AVL/algo-remocao.html. Acesso em: 24 de 
Junho de 2014. 
NONATO, Luiz. Inserção em uma Árvore AVL. Disponível em: 
http://www.lcad.icmc.usp.br/~nonato/ED/AVL/insercao.html. Acesso em: 24 de Junho 
de 2014. 
PARLANI, Nick. BInary Trees. Disponível em: 
http://cslibrary.stanford.edu/110/BinaryTrees.html. Acesso em: 24 de Julho de 2014. 
PROSSER, Patrick. AVL Trees. Disponível em: 
http://www.dcs.gla.ac.uk/~pat/52233/slides/AVLTrees1x1.pdf. Acesso em: 24 de 
Junho de 2014. 
SOUZA, Jairo. Árvore AVL. Disponível em: 
http://www.ufjf.br/jairo_souza/files/2009/12/5-Indexa%C3%A7%C3%A3o-Arvore-
AVL.pdf. Acesso em 18 de Junho de 2014. 
TOFFOLO, Túlio. Árvores AVL. Disponível em: 
http://www.decom.ufop.br/toffolo/site_media/uploads/2011-1/bcc202/slides/25._ 
arvores_%28parte_2%29.pdf. Acesso em 14 de Junho de 2014. 
WALKER, Julienne. AVL trees. Disponível em: 
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx. Acesso em 
14 de Junho de 2014. 
WIKIPÉDIA. Árvore AVL – Inserção. Disponível em: 
http://pt.wikipedia.org/wiki/%C3%81rvore_AVL#Inser.C3.A7.C3.A3o. Acesso em: 24 
de Junho de 2014. 
35 
 
WIKIPÉDIA. Codificação de Huffman. Disponível em: 
http://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_de_Huffman. Acesso em 14 
de Junho de 2014. 
WIKIPEDIA. Evgenii Landis. Disponível em: 
http://en.wikipedia.org/wiki/Evgenii_Landis. Acesso em 14 de Junho de 2014. 
WIKIPEDIA. Georgy Adelson-Velsky. Disponível em: 
http://en.wikipedia.org/wiki/Georgy_Adelson-Velsky. Acesso em 14 de Junho de 
2014. 
Árvore AVL. Disponível em: http://www.passeidireto.com/arquivo/2536633/arvore-
avl. Acesso em 14 de Junho de 2014.