Árvores AVL

Prévia do material em texto

• O processo de busca na ABB é mais rápido do que
em listas encadeadas.
• As ABB’s diminuem consideravelmente a
quantidade de comparações necessárias para
encontrar uma informação.
• No entanto, dependendo da ordem em que os nós
forem inseridos/removidos da ABB, ela pode ficar
muito desbalanceada.
Árvore Binária de Busca - ABB
 Se os nós forem inseridos na ordem crescente ou
decrescente, a ABB se tornará desbalanceada (árvore
degenerada):
Árvore Binária de Busca - ABB
Árvore Binária de Busca - ABB
 Todas armazenam os mesmos dados ordenados.
 Qual delas é a melhor? Qual é a pior?
 Quantas comparações são necessárias para se encontrar o 
elemento R na árvore (a)? E na árvore (c)?
 A quantidade de comparações que precisamos fazer
para encontrar um nó na árvore depende
diretamente da altura da árvore.
Árvores
Procurar pela chave 34 na ABB:
Exemplo
33
40
17 45
2810 53
439 35
34
Quantas comparações?
 Neste caso teremos que fazer cinco comparações
para encontrar a chave 34, proporcional a altura da
árvore!
 Quanto mais balanceada é a árvore, menor a sua
altura.
 Uma árvore está balanceada se a altura de suas
subárvores se diferem em no máximo uma unidade.
Árvores
 Nesta árvore todas as subárvores estão balanceadas, com
exceção da subárvore com raiz em 45.
 A subárvore 45 está desbalanceada, pois a altura de sua
subárvore esquerda é 3 e a altura de sua subárvore direita é 1,
com uma diferença de duas unidades.
33
40
17 45
2810 53
439 35
34
Árvore Desbalanceada:
 Se tivéssemos 1.048.575 nós, poderíamos armazená-los em
uma árvore binária perfeitamente balanceada com 20 níveis.
 Em outras palavras, poderíamos localizar um elemento
qualquer dentro dessa árvore com no máximo 20
comparações.
Vantagem da Árvore Balanceada
Altura Nós no último nível Nós em todos os níveis
1 20 = 1 21 - 1 = 1
2 21 = 2 22 - 1 = 3
3 22 = 4 23 - 1 = 7
20 219 = 524.288 220 - 1 = 1.048.575
h 2h - 1 2h - 1 = n
 Dizemos que uma árvore está balanceada quando, para
cada nó da mesma, a diferença entre as alturas de suas
duas subárvores é igual a -1, 0 ou 1.
 A esta diferença de altura damos o nome de fator de
balanceamento.
Árvores Balanceadas
 As figuras abaixo mostram as árvores anteriores com a
indicação em cada nó da diferença de altura entre suas
subárvores direita e esquerda.
Árvores Balanceadas
K
M
B P
D R
0
000
0
1
B
D
K
P
M R
0 0
0
0
1
3
R
B
D
K
M
P
1
0
2
3
4
5
 Árvore AVL (ou árvore balanceada pela altura) é
uma árvore binária de busca auto-balanceada.
 As árvores AVL têm o objetivo de manter a árvore
sempre balanceada, diminuindo assim a quantidade de
comparações feitas pelas operações de busca, inserção e
remoção.
Árvores AVL
 A ideia é a seguinte:
 Após cada operação de inserção/remoção na árvore,
verificar se algum nó se tornou desbalanceado.
 Em caso positivo, algumas operações adicionais devem
ser realizadas para tornar a árvore novamente
balanceada.
 A sigla AVL se refere aos criadores deste método, os
matemáticos russos Adelson-Velskii e Landis.
Árvores AVL
Operação de inserção:
 Calcular o FB dos nós que estão entre o nó que
acabou de ser inserido e a raiz da árvore, procurando
por um nó com FB=2 ou FB= -2, o que indica que a
subárvore com raiz naquele nó está desbalanceada.
 O FB de um nó X é a diferença entre a altura (h) de
sua subárvore direita e a altura da subárvore
esquerda.
Fator de Balanceamento
FB(X) = h(subárvore direita de X) – h(subárvore esquerda de X).
 Quando a árvore está desbalanceada deve-se efetuar
“rotações” em nós desbalanceados.
 Rotação ocorre quando o peso se torna maior em
um dos lados da árvore.
 Exemplo: inserção de X na direita.
Rotações
1
2
4
3 5
X
Exemplo: inserção de X na direita.
Rotações
1
2
4
3 5
X
FB(4) = 2 – 1 = 1  balanceado
FB(X) = h(subárvore direita de X) – h(subárvore esquerda de X).
Exemplo: inserção de X na direita.
Rotações
1
2
4
3 5
X
FB(2) = 3 – 1 = 2  desbalanceado
FB(4) = 2 – 1 = 1  balanceado
Rotações são feitas da seguinte forma:
FB > 1 => rotações para a esquerda do nó;
FB < -1 => rotações para a direita do nó.
Rotações
 FB(2) = 3 – 1 = 2  desbalanceada para a direita.
 Efetua-se rotação para esquerda:
Rotação para Esquerda
1
2
4
3 5
X
Efetua-se rotação para esquerda, obtendo-se a
árvore balanceada:
Rotação para Esquerda
2
4
1 3
5
X
FB(2) = 1 – 1 = 0
FB(4) = 2 – 2 = 0  balanceado.
1
2
4
3 5
X
Inserção a direita:
EXEMPLO 1
FB=2
35
45
20 50
2815 60
58 65
69
FB=1
FB(69) = 0  Toda folha tem FB zero.
FB(65) = 1 – 0 = 1
FB(60) = 2 – 1 = 1
FB(50) = 3 – 1 = 2 => desbalanceado para a direita.
Inserção de 69
 Como o nó desbalanceado (50) tem FB com o mesmo sinal
do FB do filho (60), então basta uma operação de rotação do
pai para tornar a árvore balanceada novamente.
Rotação
FB=2
35
45
20 50
2815 60
58 65
69
FB=1
No exemplo, como FB(50) > 1, devemos rotacionar o nó 50 para
a esquerda.
Rotação para Esquerda
FB=2
35
45
20 50
2815 60
58 65
69
FB=1
Árvore resultante da rotação de 50 à esquerda:
Árvore Balanceada
35
50
20 60
2815 65
5845
69
FB=2
35
45
20 50
2815 60
58 65
69
FB=1
Inserção a esquerda:
EXEMPLO 2
50
58
40 63
4830 70
20 35
15 Inserção de 15
Inserção a esquerda:
EXEMPLO 2
50
58
40 63
4830 70
20 35
15FB(20) = 0 – 1 = -1
FB(30) = 1 – 2 = -1
FB(40) = 1 – 3 = -2 => desbalanceado para a esquerda.
Inserção de 15
FB(40) < -1 => rotação à direita.
Rotação
50
58
40 63
4830 70
20 35
15
FB(40) < -1 => rotação à direita.
Rotação
50
58
40 63
4830 70
20 35
15
50
5840
6330
20 70
4835
15
 O caso mais complexo é quando o FB do nó
desbalanceado tem sinal contrário ao do nó filho.
 Neste caso são necessárias duas rotações:
 Primeiramente a rotação do filho para a direção
correspondente ao sinal do seu FB;
 Depois a rotação do pai (desbalanceado) para a
direção contrária.
Duas Rotações
Considere a seguinte árvore, onde o nó 78 foi inserido:
Exemplo 3
FB=-1
FB=2
50
6028
7520
15 90
9385
78
FB(85) = 0 – 1 = -1
FB(90) = 1 – 2 = -1
FB(75) = 3 – 1 = 2 => desbalanceado
Duas Rotações
2º
1º
FB=-1
FB=2
50
6028
7520
15 90
9385
78
FB(75) > 0 e FB(90) < 0 => duas rotações:
• Rotação à direita de 90 e
• Rotação à esquerda de 75.
Primeira Rotação
1º
FB=-1
FB=2
50
6028
7520
15 90
9385
78
Árvore resultante da rotação a direita de 90:
Primeira Rotação
FB=2
50
6028
7520
15 85
9078
93
Segunda Rotação
FB=2
50
6028
7520
15 85
9078
93
Segunda Rotação
FB=2
50
6028
7520
15 85
9078
93
FB=0
50
7528
8520
15 90
937860
Considere a árvore abaixo, onde o nó 25 foi inserido:
Exemplo 4
FB=1
FB= -2
50
5532
6030
15 70
25
2010
FB(20) = 1 – 0 = 1
FB(15) = 2 – 1 = 1
FB(30) = 1 – 3 = -2 => desbalanceado para a esquerda.
FB(30) < -1 e FB(15) > 0 => duas rotações: rotação à esquerda 
de 15 e rotação à direita de 30.
Rotação a Esquerda
FB=1
FB= -2
50
5532
6030
15 70
25
2010
Veja abaixo após a rotação à esquerda de 15.
Rotação a Esquerda
FB=-2
50
5532
6030
20 70
25
1015
FB=1
FB= -2
50
5532
6030
15 70
25
2010
Árvore resultante da rotação à direita de 30:
Rotação a Direita
50
5530
6020
15 70
2510 32
 Podem ocorrer quatro tipos de rotações, identificados
pelo FB(pai) e FB(filho).
 FB(pai) pode assumir os valores 2 ou -2, enquanto que o
FB(filho) pode assumir os valores 1 ou -1.
 Casos possíveis:
 FB(pai) = 2 e FB(filho) = 1
 FB(pai) = -2 e FB(filho) = -1
 FB(pai) = 2 e FB(filho) = -1 (sinal contrário)
 FB(pai) = -2 e FB(filho) = 1 (sinal contrário)
RESUMO DAS ROTAÇÕES
FB(pai) = 2 e FB(filho) = 1
RESUMO: Caso 1
1
pai
filho
3 5
X
FB(pai) = 2 e FB(filho) = 1
Balanceamento = rotação do pai para esquerda.
RESUMO: Caso 1
1
pai
filho
3 5
X
pai
filho
1 3
5
X
FB(pai) = -2 e FB(filho) = -1
Resumo: Caso 2
6
pai
filho
42
X
FB(pai) = -2 e FB(filho) = -1
Balanceamento = rotação do pai para direita.
Resumo: Caso 2
6
pai
filho
42
X
pai
filho
4 6
X
2
FB(pai) = 2 e FB(filho) = -1 (sinal contrário)
Resumo: Caso 3
pai
filho
3 6
X
1
FB(pai) = 2 e FB(filho) = -1 (sinal contrário)
Balanceamento:
 rotação do filho p/ direita;
 rotação do pai p/ esquerda.
Resumo: Caso 3
pai
filho
3 6
X
1
pai
filho
3
6
X
1
FB(pai) = 2 e FB(filho) = -1 (sinal contrário)
Balanceamento:
 rotação do filho p/ direita;
 rotação do pai p/ esquerda.
Resumo: Caso 3
pai
filho
3 6
X
1
pai
filho
3
6
X
1
FB(pai) = 2 e FB(filho) = -1 (sinal contrário)
Balanceamento:
 rotação do filho p/ direita;
 rotação do pai p/ esquerda.
Resumo: Caso 3
pai
filho
3
6
X
1
pai filho
3
6X1
pai
filho
3 6
X
1
FB(pai) = -2 e FB(filho) = 1 (sinal contrário)
Resumo: Caso 4
6
pai
filho
31
X
FB(pai) = -2 e FB(filho) = 1 (sinal contrário)
Balanceamento:
 rotação do filho p/ esquerda;
 rotação do pai p/ direita.
Resumo: Caso 4
6
pai
filho
3
1
X
6
pai
filho
31
X
FB(pai) = -2 e FB(filho) = 1 (sinal contrário)
Balanceamento:
 rotação do filho p/ esquerda;
 rotação do pai p/ direita.
Resumo: Caso 4
6
pai
filho
3
1
X
6
pai
filho
31
X
FB(pai) = -2 e FB(filho) = 1 (sinal contrário)
Balanceamento:
 rotação do filho p/ esquerda;
 rotação do pai p/ direita.
Resumo: Caso 4
6
pai
filho
3
1
X
6
paifilho
3
1
X
6
pai
filho
31
X
 Vamos definir a estrutura do No da Árvore
AVL contendo:
 As referências à direita e à esquerda;
 Um campo que comporte a altura do nó;
 Um campo que comporte o FB do nó.
Definição da Estrutura
Definição da Estrutura
typedef struct estrutura{
TIPOCHAVE info;
int altura, fb;
struct estrutura* esq;
struct estrutura* dir;
} NO;
Definição da Estrutura
typedef int TIPOCHAVE;
typedef struct estrutura{
TIPOCHAVE info;
int altura, fb;
struct estrutura* esq;
struct estrutura* dir;
} NO;
typedef struct {
NO* raiz;
} ARVORE;
Inicialização
typedef int TIPOCHAVE;
typedef struct estrutura{
TIPOCHAVE info;
int altura, fb;
struct estrutura *esq;
struct estrutura *dir;
} NO;
typedef struct {
NO *raiz;
} ARVORE;
void inicializarArvore(ARVORE* a){
a->raiz = NULL;
}
Mostrar a Árvore
void mostrar(NO* no){
if (no){
printf("[");
mostrar(no->esq);
printf(“%d.a%d.fb%d", no->info, 
no->altura,
no->fb);
mostrar(no->dir);
printf("]");
}
}
Exemplo: [[100.a1.fb0]120.a2.fb0[150.a1.fb0]]
 Escreva uma função que calcule a altura e o FB do
nó corrente baseado nas informações de seus nós
filhos.
Calcular Altura e 
Fator de Balanciamento
NO* calculaAlturaFB(NO* no){
//obter a altura do nó a esquerda
//obter a altura do nó a direita
//calcular a altura deste nó
//calcular FB deste nó
NO* calculaAlturaFB(NO* no){
int altEsq, altDir;
//obter a altura do nó a esquerda
if (!no->esq) altEsq = 0;
else altEsq = no->esq->altura;
//obter a altura do nó a direita
Calcular Altura e 
Fator de Balanciamento
NO* calculaAlturaFB(NO* no){
int altEsq, altDir;
//obter a altura do nó a esquerda
if (!no->esq) altEsq = 0;
else altEsq = no->esq->altura;
//obter a altura do nó a direita
if (!no->dir) altDir = 0;
else altDir = no->dir->altura;
//calcular a altura deste nó
Calcular Altura e 
Fator de Balanciamento
NO* calculaAlturaFB(NO* no){
int altEsq, altDir;
//obter a altura do nó a esquerda
if (!no->esq) altEsq = 0;
else altEsq = no->esq->altura;
//obter a altura do nó a direita
if (!no->dir) altDir = 0;
else altDir = no->dir->altura;
//calcular a altura deste nó
if (altDir > altEsq) no->altura = altDir + 1;
else no->altura = altEsq + 1;
//calcular FB deste nó
Calcular Altura e 
Fator de Balanciamento
NO* calculaAlturaFB(NO* no){
int altEsq, altDir;
//obter a altura do nó a esquerda
if (!no->esq) altEsq = 0;
else altEsq = no->esq->altura;
//obter a altura do nó a direita
if (!no->dir) altDir = 0;
else altDir = no->dir->altura;
//calcular a altura deste nó
if (altDir > altEsq) no->altura = altDir + 1;
else no->altura = altEsq + 1;
//calcular FB deste nó
no->fb = altDir - altEsq;
return no;
}
Calcular Altura e 
Fator de Balanciamento
Escreva uma função que faça a rotação à direita do nó pai.
Rotação a Direita
6
5
3
42
X
pai
5
3
4 6
X
2
filho
NO* rotacaoDir(NO* no){ 
//Realiza a rotação para a DIREITA.
...
}
6
5
3
42
X
pai
filho
NO* rotacaoDir(NO* no){ 
NO *pai = no;
NO *filho = no->esq;
pai->esq = filho->dir;
filho->dir = pai;
no = filho;
no->dir = calculaAlturaFB(no->dir);
no = calculaAlturaFB(no);
return no;
}
5
3
4
X
2
6
Rotação a Direita
 Escreva uma função que faça a rotação à esquerda
do nó pai.
1
2
4
3 5
X
pai
filho
2
4
1 3
5
X
NO* rotacaoEsq(NO* no){ 
//Realiza a rotação para a ESQUERDA.
...
}
Rotação a Esquerda
1
2
4
3 5
X
pai
filho
2
4
1 3
5
X
NO* rotacaoEsq(NO* no){
NO *pai = no;
NO *filho = no->dir;
pai->dir = filho->esq;
filho->esq = pai;
no = filho;
no->esq = calculaAlturaFB(no->esq);
no = calculaAlturaFB(no);
return no;
}
Rotação a Esquerda
 Escreva uma função que recebe um nó
desbalanceado e faz as rotações necessárias para
balanceá-lo.
Balancear
NO* balancear(NO* no){
// Realiza os 4 casos de balanceamento.
...
}
Casos Gerais p/ Balanceamento
FB(pai) = 2 e FB(filho) = 1
rotação do pai para esquerda.
FB(pai) = -2 e FB(filho) = -1
rotação do pai para direita.
FB(pai) = 2 e FB(filho) = -1 (sinal contrário)
rotação do filho p/ direita;
rotação do pai p/ esquerda.
FB(pai) = -2 e FB(filho) = 1 (sinal contrário)
rotação do filho p/ esquerda;
rotação do pai p/ direita.
NO* balancear(NO* no){
if (no->fb == 2){
if (no->dir->fb == -1)
no->dir = rotacaoDir(no->dir);
no = rotacaoEsq(no);
}
else if (no->fb == -2){
if (no->esq->fb == 1)
no->esq = rotacaoEsq(no->esq);
no = rotacaoDir(no);
}
return no;
}
Balancear
 Criar uma função para inserir um novo elemento na
árvore AVL, mantendo o balanceamento.
NO* insereNO(NO* no, TIPOCHAVE valor){
//Insere um nó na árvore mantendo ordem. 
//Liga o novo nó na árvore na volta da recursão.
...
}
void insere(ARVORE* a, TIPOCHAVE ch){
a->raiz = insereNO(a->raiz, ch);
}
Inserir ElementoNO* insereNO(NO* no, TIPOCHAVE valor){
//Insere um nó na árvore mantendo ordem. 
//Liga o novo nó na árvore na volta da recursão.
//encontrou o lugar da inserção
if (!no){
no = (NO*) malloc(sizeof(NO));
no->info = valor;
no->esq = no->dir = NULL;
}
// decidir em que lado inserir
...
Inserir Elemento
NO* insereNO(NO* no, TIPOCHAVE valor){
//Insere um nó na árvore mantendo ordem. 
//Liga o novo nó na árvore na volta da recursão.
//encontrou o lugar da inserção
if (!no){
no = (NO*) malloc(sizeof(NO));
no->info = valor;
no->esq = no->dir = NULL;
}
// decidir em que lado inserir
else if (valor < no->info)
no->esq = insereNO(no->esq, valor);
else if (valor > no->info)
no->dir = insereNO(no->dir, valor);
else {//chave já existe
...
Inserir Elemento
NO* insereNO(NO* no, TIPOCHAVE valor){
if (!no){
no = (NO*) malloc(sizeof(NO));
no->info = valor;
no->esq = no->dir = NULL;
}
// decidir em que lado inserir
else if (valor < no->info)
no->esq = insereNO(no->esq, valor);
else if (valor > no->info)
no->dir = insereNO(no->dir, valor);
else {//chave já existe
printf("\nErro: a chave ja existe.");
return no;
}
no = calculaAlturaFB(no);
//verificar se esta balanceada
...
Inserir Elemento
NO* insereNO(NO* no, TIPOCHAVE valor){
if (!no){
no = (NO*) malloc(sizeof(NO));
no->info = valor;
no->esq = no->dir = NULL;
}
else if (valor < no->info)
no->esq = insereNO(no->esq, valor);
else if (valor > no->info)
no->dir = insereNO(no->dir, valor);
else {//chave já existe
printf("\nErro: a chave ja existe.");
return no; 
}
no = calculaAlturaFB(no);
//verifica se esta balanceada
if(no->fb == 2 || no->fb == -2){
no = balancear(no); 
}
return no;
}
Inserir Elemento
NO* insereNO(NO* no, TIPOCHAVE valor){
if (!no){
no = (NO*) malloc(sizeof(NO));
no->info = valor;
no->esq = no->dir = NULL;
}
else if (valor < no->info)
no->esq = insereNO(no->esq, valor);
else if (valor > no->info)
no->dir = insereNO(no->dir, valor);
else {//chave já existe
printf("\nErro: a chave ja existe.");
return no;
}
no = calculaAlturaFB(no);
//verifica se esta balanceada
if(no->fb == 2 || no->fb == -2){
no = balancear(no); }
return no;
}
void insere(ARVORE* a, TIPOCHAVE ch){
a->raiz = insereNO(a->raiz, ch);
}
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
mostrar(arv.raiz);
}
Programa Principal
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
mostrar(arv.raiz);
}
Programa Principal
[100.a1.fb0]
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
mostrar(arv.raiz);
}
Programa Principal
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
mostrar(arv.raiz);
}
Programa Principal
[[100.a2.fb1[120.a1.fb0]]
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
insere(&arv, 150);
printf("\n");
mostrar(arv.raiz);
}
Programa Principal
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
insere(&arv, 150);
printf("\n");
mostrar(arv.raiz);
}
Programa Principal
[[100.a1.fb0]120.a2.fb0[150.a1.fb0]]
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
insere(&arv, 150);
insere(&arv, 30);
printf("\n");
mostrar(arv.raiz);
}
Programa Principal
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
insere(&arv, 150);
insere(&arv, 30);
printf("\n");
mostrar(arv.raiz);
}
Programa Principal
[[[30.a1.fb0]100.a2.fb-1]120.a3.fb-1[150.a1.fb0]]
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
insere(&arv, 150);
insere(&arv, 30);
insere(&arv, 35);
printf("\n");
mostrar(arv.raiz);
}
Programa Principal
Inserir Elemento
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
insere(&arv, 150);
insere(&arv, 30);
insere(&arv, 35);
printf("\n");
mostrar(arv.raiz);
}
Programa Principal
[[[30.a1.fb0]35.a2.fb0[100.a1.fb0]]120.a3.fb-1[150.a1.fb0]]
Inserir Elemento
 Remover 120:
Encontrar Antecessor
e Remover Elemento
120
100
150
30
35
no
noAnt
int main() {
ARVORE arv;
inicializarArvore(&arv);
insere(&arv, 100);
insere(&arv, 120);
insere(&arv, 150);
insere(&arv, 30);
insere(&arv, 35);
printf("\n");
mostrar(arv.raiz);
remover(120, &arv);
mostrar(arv.raiz);
}
 Remover 120:
Encontrar Antecessor
e Remover Elemento
120
100
150
30
35
no
noAnt 100
100
150
30
35
no
noAnt’
noAnt
int main() {
ARVORE arv;
inicializarArvore(&arv);
...
mostrar(arv.raiz);
remover(120, &arv);
 Remover 120:
Encontrar Antecessor
e Remover Elemento
100
100
150
30
35
no
noAnt’
100
150
30
35
no
noAntnoAnt
int main() {
ARVORE arv;
inicializarArvore(&arv);
...
mostrar(arv.raiz);
remover(120, &arv);
 Remover 120:
Encontrar Antecessor
e Remover Elemento
100
150
30
35
no
noAnt
[[[30.01.fb0]35.a2.fb-1]100.a3.fb-1[150.a1.fb0]]
int main() {
ARVORE arv;
inicializarArvore(&arv);
...
mostrar(arv.raiz);
remover(120, &arv);
 Criar uma função para remover um elemento da
árvore AVL, mantendo o balanceamento.
Remover Elemento
void remover(TIPOCHAVE chave, ARVORE* a){
// Remove chave da árvore.
a->raiz = removeNo(a->raiz, chave);
}
NO* removeNo(NO* no, TIPOCHAVE chave){
// Remove o nó com chave. 
// Reconstrói a árvore na volta da recursão.
...
}
NO* removeNo(NO* no, TIPOCHAVE chave){
if (!no){
printf("\nErro: a chave nao existe.");
return NULL;
}
// decidir em que lado procurar a chave
...
Remover Elemento
NO* removeNo(NO* no, TIPOCHAVE chave){
if (!no){
printf("\nErro: a chave nao existe.");
return NULL;
}
// decidir em que lado procurar a chave
if (chave < no->info)
no->esq = removeNo(no->esq, chave);
else if (no->info < chave)
no->dir = removeNo(no->dir, chave);
else
// remove nó com um filho ou folha
...
Remover Elemento
NO *removeNo(NO *no, TIPOCHAVE chave){
if (!no){
printf("\nErro: a chave nao existe.");
return NULL;
}
// decidir em que lado procurar a chave
if (chave < no->info)
no->esq = removeNo(no->esq, chave);
else if (no->info < chave)
no->dir = removeNo(no->dir, chave);
else
// remove nó folha 
if (!no->dir && !no->esq) 
no = NULL;
//remove nó com um filho
else if (!no->dir)
no = no->esq;
else if (!no->esq)
no = no->dir;
...
Remover 
Elemento
Remover 
Elemento
NO *removeNo(NO *no, TIPOCHAVE chave){
if (!no){
printf("\nErro: a chave nao existe.");
return NULL;
}
// decidir em que lado procurar a chave
if (chave < no->info)
no->esq = removeNo(no->esq, chave);
else if (no->info < chave)
no->dir = removeNo(no->dir, chave);
else
// remove nó folha 
if (!no->dir && !no->esq) 
no = NULL;
//remove nó com um filho
else if (!no->dir)
no = no->esq;
else if (!no->esq)
no = no->dir;
...
else //remove nó com dois filhos
no->esq = antecessor(&no, no->esq);
...
NO *removeNo(NO *no, TIPOCHAVEchave){
if (!no){
printf("\nErro: a chave nao existe.");
return NULL;
} // decidir em que lado procurar a chave
if (chave < no->info)
no->esq = removeNo(no->esq, chave);
else if (no->info < chave)
no->dir = removeNo(no->dir, chave);
else
// remove nó com um filho ou folha
if (!no->dir && !no->esq)
no = NULL;
else if (!no->dir) //remove nó com um filho
no = no->esq;
else if (!no->esq)
no = no->dir;
else //remove nó com dois filhos
no->esq = antecessor(&no, no->esq);
Remover 
Elemento
if(no){
no = calculaAlturaFB(no);
if(no->fb == 2 || no->fb == -2)
no = balancear(no);
}
return no;
}
NO *removeNo(NO *no, TIPOCHAVE chave){
if (!no) return NULL;
if (chave < no->info)
no->esq = removeNo(no->esq, chave);
else if (no->info < chave)
no->dir = removeNo(no->dir, chave);
else
if (!no->dir && !no->esq)
no = NULL;
else if (!no->dir)
no = no->esq;
else if (!no->esq)
no = no->dir;
else
no->esq = antecessor(&no, no->esq);
if(no){
no = calculaAlturaFB(no);
if(no->fb == 2 || no->fb == -2)
no = balancear(no);
}
return no;
}
Remover 
Elemento
Encontrar Antecessor
NO* antecessor(NO** no, NO* noAnt){
// Procura pelo nó antecessor de no 
// e remove o antecessor.
ALGORITMO
}
NO* antecessor(NO** no, NO* noAnt){
// desce até o nó mais à direita na subarvore esquerda
if (noAnt->dir)
noAnt->dir = antecessor(no, noAnt->dir);
else{ // copia a informação do antecessor para o nó removido
(*no)->info = noAnt->info;
// remove o antecessor
noAnt = noAnt->esq;
}
// reconstroi a subárvore na volta da recursão
if(noAnt){
noAnt = calculaAlturaFB(noAnt);
if(noAnt->fb == 2 || noAnt->fb == -2){
noAnt = balancear(noAnt);
}
}
return noAnt;
}
Encontrar Antecessor