Extermı́nio de mariposas∗
Tássio Naia dos Santos
15 de dezembro de 2011
Sumário
1. Enunciado . . . . . . . . . . . . . . . . . . . . . .
2. Que tristeza! Querem matar as mariposas! . . . .
19. Encontrando o fecho . . . . . . . . . . . . . . . .
21. Comparando com pontos do fecho . . . . . . . .
26. Mı́nimo e máximo elemento com a propriedade P
27. A árvore binária de busca balanceada . . . . . .
35. Árvore rubro-negra . . . . . . . . . . . . . . . . .
37. Inserção . . . . . . . . . . . . . . . . . . . . . . .
50. Remoção . . . . . . . . . . . . . . . . . . . . . .
68. Inicialização e incremento do fecho . . . . . . . .
77. Algumas coisas que vou deixar aqui por enquanto
81. Gerando a saı́da . . . . . . . . . . . . . . . . . .
1.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
3
7
9
12
13
17
18
22
27
30
31
Enunciado
Entomologistas colocaram armadilhas para determinar o influxo de mariposas de julho em uma dada região do
planeta. A intenção é estudar programas de extermı́nio que tenham algum potencial de controlar o aumento na
população de mariposas.
O estudo requer uma organização das armadilhas em regiõs compactas, que serão então usadas para testar cada
técnica de extermı́nio. Uma região é definida como o polı́gono com o perı́metro de menor comprimento que pode
circundar todas as armadilhas em uma região. A figura 1 ilustra as armadilhas (representadas por pontos) de uma
região, e o polı́gono a elas associado.
y
x
Figura 1: Exemplo correspondente à Regi~
ao #3 da entrada de exemplo.
.
Entrada O arquivo de entrada contém registros de dados para diversas regiões. A primeira linha de cada registro
contém o número (inteiro) de armadilhas na região. Linhas seguintes contém cada dois números reais que são as
coordenadas x e y de uma armadilha. Não há duplicação de dados em um registro (cada armadilha aparece apenas
uma vez em um registro). O fim da entrada é indicado por uma região com zero armadilhas.
Saı́da A saı́da, para uma região, é representada por ao menos três linhas.
∗ Problema
para UVA Online Judge
1
Primeira linha O número da região. O primeiro registro corresponde à Regi~
ao #1, o segundo à Regi~
ao #2, etc.
Próxima(s) linhas Uma lista dos pontos que aparecem no perı́metro de uma região. Os pontos devem ser identificados na forma (x, y), arredondados para uma única casa decimal. O ponto inicial da listagem é irrelevante,
mas a lista deve estar orientada em sentido horário, além de iniciar e terminar com o mesmo ponto. No caso
de pontos colineares, qualquer ordem que descreva o perı́metro de menor comprimento é aceitável.
Última linha O perı́metro da região, arredondado para duas casas decimais.
Uma linha em branco deve separar a saı́da de dois registros consecutivos.
ENTRADA
3
1 2
4 10
5 12.3
6
0 0
1 1
3.1 1.3
3 4.5
6 2.1
2 -3.2
7
1 0.5
5 0
4 1.5
3 -0.2
2.5 -1.5
0 0
2 2
0
SAÍDA
Region #1:
(1.0,2.0)-(4.0,10.0)-(5.0,12.3)-(1.0,2.0)
Perimeter length = 22.10
Region #2:
(0.0,0.0)-(3.0,4.5)-(6.0,2.1)-(2.0,-3.2)-(0.0,0.0)
Perimeter length = 19.66
Region #3:
(0.0,0.0)-(2.0,2.0)-(4.0,1.5)-(5.0,0.0)-(2.5,-1.5)-(0.0,0.0)
Perimeter length = 12.52
2
2.
Que tristeza! Querem matar as mariposas!
E usando cientistas da computação. Onde é que vamos parar?! Já sei, já sei. Você não está lendo este documento
para este tipo de coisa. Talvez esteja mesmo avaliando se não é bom pular alguns parágrafos até que o autor volte
ao normal, e discuta as coisas como se deve fazer. Pronto, pronto, o próximo parágrafo é seguro. Parei.
O desafio é encontrar o fecho convexo (doravante simplesmente fecho) de um conjunto de pontos, e fornecer o
seu perı́metro. Vamos usar hoje um algoritmo incremental para fazer esse serviço. Incremental no sentido de que,
após algum pré-processamento, vamos analisar os pontos um a um, guardando o fecho dos pontos já observados.
Naturalmente, ao fim desse processo teremos o fecho convexo do conjunto de pontos todo. Depois é só percorrer
esse conjunto em sentido horário — vamos precisar fazer isso para imprimir os pontos do fecho, de qualquer modo
— calculando o seu perı́metro.
Começamos com uma breve discussão dos predicados geométricos que vamos usar, seguida das estruturas de
dados que serão úteis. Por fim, alguns detalhes mais técnicos do algoritmo, para garantir consumo de tempo
esperado O(n lg n).
3. Os pontos do fecho são pontos extremos, da coleção, em um certo sentido. Ademais, o fecho é um polı́gono
convexo (mora?). Ora, seguindo o esquema geral do algoritmo que esboçamos, é preciso descobrir se cada ponto
pnovo que analisamos está dentro ou fora do fecho intermediário que temos em mãos. Chamaremos de H o conjunto
de pontos já analisados que pertencem à fronteira do polı́gono, por razões anglófonas1 .
Se o ponto pnovo está dentro do polı́gono do fecho, então podemos passar ao próximo ponto, não temos nada
a fazer. Caso contrário, ele passa a fazer parte de H, e, com sua inserção, alguns dos pontos que estavam em H
devem sair dele (lembre-se que H contém apenas os pontos na “fronteira” do fecho).
pnovo
u v
v1
v2
pbaixo
Figura 2: Analisando o ponto pnovo — deve ser acrescentado ao fecho?
Na figura 2, H contém, em sentido horário os pontos pbaixo , . . . , v1 , . . . , u, v, v2 . . . (reticências indicam pontos a
que não demos nomes). Ali, o ponto pnovo está do lado de fora da fronteira, e então ele deve ser acrescentado ao
fecho. Os pontos u, v, assim como vários pontos da fronteira que são vistos por pnovo devem ser removidos. Note
que os pontos que vão sair estão entre v1 e v2 . Isso é importante: os pontos que saem são sempre um conjunto
de pontos consecutivos na fronteira de H (se o conjunto de pontos tivesse um “furo”, o fecho não seria convexo).
Além disso, esses extremos (v1 e v2 ), são exatamente os pontos “vizinhos” de pnovo na fronteira do polı́gono, depois
que ele é acrescentado ao fecho. Depois da remoção da região visı́vel, H passa a conter, em sentido horário, os
pontos pbaixo , . . . , v1 , pnovo , v2 . . . Pode também acontecer de pnovo pertencer a uma aresta do fecho. Nesse caso,
consideramos (de acordo com o enunciado) que ele deve ser acrescentado a H.
4. Certo, testar se o pnovo está dentro do polı́gono nos diz se ele entra ou não em no fecho H. Mas como encontrar
(caso existam) os pontos do fecho que precisam sair com a chegada do ponto?
Já observamos que a parte do fecho que deve sair com a entrada de pnovo é “um pedaço só” da fronteira.
Trocando em miúdos, isso significa que só precisamos encontrar os extremos do pedaço que deve ser removido. Na
verdade, os extremos só não bastam, já que dois pontos no fecho determinam dois pedaços, e precisamos saber
qual deles queremos remover. A ambiguidade some se orientamos o fecho em um sentido — por exemplo, o sentido
horário — e chamamos um dos extremos de primeiro e o outro de último.
Bom, é isso. Agora que compreendemos melhor o problema, vamos atacá-lo!
1 Fecho
convexo, em inglês, é convex hull, e. . . bem, inglês é uma lı́ngua tão comum quando se fala de algoritmos!
3
5.
Estrutura de nosso programa.
h Arquivos de cabeçalho 8 i
h Constantes e variáveis globais 6 i
h Pré-declaração de funções 34 i
h Funções 33 i
h Rotina principal 7 i
6. O s dados da região analisada ficam guardados em variáveis globais. O número de pontos N e o número da
região numero regiao .
h Constantes e variáveis globais 6 i ≡
int N = 0;
int numero regiao = 1;
Veja também os trechoss 15, 28, 29 e 31.
Código utilizado no trecho 5.
7. A rotina principal opera em laços leitura, processamento, saı́da, que em cada iteração encontra o fecho convexo
para cada uma das regiões descrita na entrada.
Como o número de pontos no fecho pode ser “arbitrariamente” grande2 , vamos fazer alguma alocação de
memória, que precisaremos desfazer depois de processadas as regiões. Essa é a última tarefa de nosso programa.
h Rotina principal 7 i ≡
int main (int argc , char ∗∗argv )
{
h Variáveis locais de main 12 i
printf ("prompt $ ");
fflush (stdin );
scanf ("%d", &N );
while (N > 0) {
h Leitura e processamento do registro da região 9 i
h Imprime a resposta para a região 81 i
++ numero regiao ;
/∗ Avança contador de região. ∗/
printf ("prompt $ ");
fflush (stdin );
scanf ("%d", &N );
}
h Libera memória alocada 18 i
return 0;
}
Código utilizado no trecho 5.
8. Nossas necessidades de entrada, saı́da e alocação dinâmica de memória deixam claro que algumas bibliotecas
são necessárias.
h Arquivos de cabeçalho 8 i ≡
#include <stdio.h>
#include <stdlib.h>
Veja também os trechoss 22 e 32.
Código utilizado no trecho 5.
9. Guardamos as coordenadas dos pontos nos vetores X[0..N − 1] e Y [0..N − 1]. O fecho convexo é armazenado
usando dois vetores: H[ ] e antecessor em H [ ], que não vamos manipular diretamente. Como precisamos exibir os
pontos do fecho em sentido horário, armazenamos essa informação em H[]: se o ponto i = (x, y) = (X[i],Y [i]) está
no fecho, então sucessor (i) é o próximo ponto (da fronteira) do fecho, percorrido em sentido horário. Por sua vez,
antecessor (sucessor (i)) ≡ i se i é um ponto do fecho. Certo, mas como saber se um ponto está no fecho? Bom,
tomando alguns cuidados na hora de escrever nosso algoritmo, podemos garantir que o ponto zero sempre faz parte
2 Desde
que não excedidas as limitações do computador que se está usando.
4
do fecho. Um jeito de fazer isso é colocar nessa posição algum dos pontos extremos da região, digamos, o de menor
y-coordenada. Em caso de empate entre pontos, tomamos o que tem a menor x-coordenada entre eles. Essa é nossa
escolha aqui. Doravante, esse ponto será chamado de pbaixo . Para economizar um pouco de tempo, encontramos
pbaixo à medida que lemos a entrada do problema. Vamos aproveitar também para encontrar palto , o ponto de maior
x-coordenada entre os pontos que empatam na maior y-coordenada da coleção. Quando N > 1, a condição de que
não há pontos da coleção com ambas as coordenadas iguais, garante que esse ponto existe e é diferente de pbaixo .
Em todo caso, se N ≡ 1, o fecho é trivial.
h Leitura e processamento do registro da região 9 i ≡
h Aloca espaço para X e Y ; pára o programa em caso de erro 13 i
scanf ("%lf %lf", &X[0], &Y [0]);
/∗ Lê o primeiro ponto. ∗/
if (N > 1) {
h Lê o segundo ponto e inicializa ı́ndices pbaixo e palto 10 i
h Lê os demais pontos, mantendo pbaixo e palto apontando para os pontos certos 11 i
h Troca pbaixo e 0 de posição e também palto e 1 em X[ ] e Y [ ] 16 i
for (i = 0; i < N ; ++ i) printf ("%d -> %.1f %.1f\n", i, X[i], Y [i]);
h Encontra o fecho convexo da região 19 i;
}
Código utilizado no trecho 7.
10. h Lê o segundo ponto e inicializa ı́ndices pbaixo e palto 10 i ≡
scanf ("%lf %lf", &X[1], &Y [1]);
if (h O ponto 0 tem y-coordenada menor do que a do ponto 1, ou ambos têm mesma y-coordenada mas 0 tem
x-coordenada menor 25 i) {
p baixo = 0;
p alto = 1;
}
else {
p baixo = 1;
p alto = 0;
}
Código utilizado no trecho 9.
11. h Lê os demais pontos, mantendo pbaixo e palto apontando para os pontos certos 11 i ≡
for (p novo = 2; p novo < N ; ++ p novo ) {
scanf ("%lf %lf", &X[p novo ], &Y [p novo ]);
if (h Ponto pnovo deve entrar no lugar de pbaixo 23 i) p baixo = p novo ;
else
/∗ Nenhum ponto poderia ser atribuı́do a ambos pbaixo e palto ao mesmo tempo. ∗/
if (h Ponto pnovo deve entrar no lugar de palto 24 i) p alto = p novo ;
}
Código utilizado no trecho 9.
12. h Variáveis locais de main 12 i ≡
int p novo ;
Veja também os trechoss 17, 76 e 86.
Código utilizado no trecho 7.
13. Usamos uma abordagem hı́brida para gerenciamento da memória no programa. Se o tamanho dos vetores,
tamanho pontos , não excede o limite tamanho inicial pontos , usamos vetores estaticamente alocados. Quando N
ultrapassa o valor de tamanho pontos , alocamos memória. A cada nova região processada, verificamos se N excedeu
tamanho pontos , alocando mais memória se necessário.
Como o tamanho do fecho não é necessariamente o tamanho do vetor de pontos, e como usamos dois vetores
(H e antecessor ) para armazenar o fecho, o tamanho inicial fecho é menor do que tamanho inicial pontos .
Além disso, ainda não sabemos como vamos fazer a parte do programa que trata do aumento ou diminuição
do fecho, então deixamos a alocação de H e antecessor em H para depois. De todo modo, é importante que cada
um dos vetores tenha inicialmente ao menos uma posição, para que o programa trate os casos N ≡ 1 e N ≡ 2
graciosamente.
5
#define tamanho inicial pontos 2000
#define tamanho inicial fecho 1000
/∗ Será que é melhor usar uma potência de 2? ∗/
h Aloca espaço para X e Y ; pára o programa em caso de erro 13 i ≡
if (N > tamanho pontos ) {
libera pontos ( );
X = malloc (sizeof (double) ∗ N );
Y = malloc (sizeof (double) ∗ N );
tamanho pontos = N ;
}
Código utilizado no trecho 9.
14. A macro libera pontos ( ) só faz lguma coisa se o conjunto de pontos foi alocado alguma vez. Como isso só
acontece se tamanho pontos > tamanho inicial pontos . . .
#define libera pontos () do
{
if (tamanho pontos > tamanho inicial pontos ) {
free (X);
free (Y );
X = X estatico ;
Y = Y estatico ;
tamanho pontos = tamanho inicial pontos ;
}
}
while (0)
15.
Como dissemos, inicialmente X e Y apontam para vetores estaticamente alocados.
h Constantes e variáveis globais 6 i +≡
double X estatico [tamanho inicial pontos ], Y estatico [tamanho inicial pontos ];
double ∗X = X estatico , ∗Y = Y estatico ;
int tamanho pontos = tamanho inicial pontos ;
16.
x
y
x
y
h Troca pbaixo e 0 de posição e também palto e 1 em X[ ] e Y [ ] 16 i ≡
aux = X[0]; X[0] = X[p baixo ]; X[p baixo ] = x aux ;
aux = Y [0]; Y [0] = Y [p baixo ]; Y [p baixo ] = y aux ;
aux = X[1]; X[1] = X[p alto ]; X[p alto ] = x aux ;
aux = Y [1]; Y [1] = Y [p alto ]; Y [p alto ] = y aux ;
Código utilizado no trecho 9.
17. h Variáveis locais de main 12 i +≡
int p baixo , p alto ;
double x aux , y aux ;
18. h Libera memória alocada 18 i ≡
libera pontos ( );
libera arvore ( );
Código utilizado no trecho 7.
6
19.
Encontrando o fecho
Nosso algoritmo opera “aumentando” o fecho pouco a pouco. Ele começa com algum fecho pequeno (três dos
pontos da coleção), e percorre a seguir os pontos que ainda não foram analisados, alterando-o quando necessário.
A estrutura do algoritmo é bastante simples. Inicializamos o fecho e depois processamos os pontos um a um.
Em um estágio intermediário, temos um fecho H, que podemos percorrer no sentido horário usando sucessor ( ).
Queremos saber se o ponto pnovo deve entrar nessa lista, e, além disso, que pontos devem sair do fecho com a sua
entrada — se é que algum sai. Como fazer? Já vimos que o ponto entra no fecho somente se está fora, ou na
fronteira, de seu polı́gono. E como decidir se esse é o caso? Um jeito de decidir é percorrer as arestas do fecho em
um sentido (horário ou anti-horário), observando de que lado está o ponto. Como o polı́gono definido pelos pontos
do fecho é convexo, o ponto estará sempre do mesmo lado somente quando ele está dentro do polı́gono. Um exemplo
pode ser visto na figura 3.
p
p
q
q
Figura 3: Esquerda: pontos fora (p) e dentro (q) do fecho. Se percorremos o fecho em sentido horário, q permanece
à nossa direita, enquanto p fica ora à esquerda, ora à direita. Direita: Fecho após a inclusão de p. Os pontos em H
(vértices na fronteira do fecho) estão conectados por arestas — são os vértices do polı́gono definido pelo fecho.
Fixando que vamos percorrer o polı́gono em sentido horário, se o ponto novo se mantiver à direita, ele está
dentro do polı́gono, e não precisamos alterar o fecho. Se em algum caso o ponto fica à esquerda de uma aresta,
sabemos que ele está fora do polı́gono, mas isso não é tudo! Sabemos ainda que ele vê os extremos dessa aresta. Na
figura 3, os pontos vistos por p estão conectados a ele por uma linha tracejada. Já vimos que os pontos vistos por
p são uma porção conexa do fecho — uma curva poligonal. É fácil decidir quem fica ou sai de H se sabemos quais
pontos vêem (ou, se preferir, são vistos por) p: mantemos os extremos da região visı́vel, e eliminamos seu interior.
Uma primeira estratégia então é: observar, para cada aresta do fecho, se pnovo está à esquerda, guardando a
primeira e a última aresta da região visı́vel. Colocamos pnovo no fecho, entre os extremos dessa região, eliminando
do fecho os pontos internos.
O problema com essa estratégia é que sempre requer que analisemos todos os pontos que estão no nosso fecho
intermediário. Vamos fazer algo um pouco diferente, que às vezes nos leva mais rápido à resposta. . .
Queremos uma estrutura de dados que nos permita fazer uma espécie de busca binária pelos extremos da região
vista por pnovo , de modo a encontrar uma aresta decisora da situação de pnovo . Se pnovo está à esquerda da aresta
decisora, então ele está fora do polı́gono; se está à direita, então está dentro do polı́gono. Essa aresta, claro, pode
ser diferente para cada pnovo .
Existe uma aresta assim? Considere um fecho — que é um polı́gono convexo — com ao menos dois
e um ponto pnovo diferente de qualquer de seus vértices.
Se pnovo está estritamente dentro do polı́gono (isto é, está dentro mas não pertence a nenhuma
aresta), então o ponto está à direita de todas as arestas, subendendendo como antes que percorremos
as arestas em sentido horário. Nesse caso, todas as arestas são decisoras.
Se pnovo está em alguma aresta, então ele está à direita não estrita de todas as arestas. Em particular,
está à direita estrita de todas as arestas exceto uma, e nesse caso pertence à aresta. A princı́pio, usando
um teste de esquerda estrita, ainda aqui todas as arestas são decisoras.
Se, por fim, está fora do polı́gono, está à esquerda de algumas arestas e à direita de outras. Tome
um vértice qualquer do fecho, e trace um segmento de reta dele até pnovo . Esse segmento tem uma
intersecção não nula com o fecho, que é pelo menos o vértice tomado, e no máximo um segmento de reta
que “corta” o fecho. Seja pref o ponto da interseção desse segmento que está mais próximo de pnovo . Se
pref é um vértice do fecho, então
1. pnovo está à ersquerda estrita de algum das arestas partindo de pref , ou
2. as arestas do fecho que tem pref como extremidade são ambas paralelas ao segmento de reta que
une pref e pnovo .
7
Enquanto, se pref não é vértice do fecho, então as propriedades acima valem para a aresta em que está.
Isso sugere que a(s) arestas que incidem em pref são arestas decisoras, desde que tomemos o cuidado de
verificar quanto à colinearidade.
Em todo caso, existe uma aresta decisora. Com ela podemos decidir o destino de pnovo . Nosso
objetivo então é encontrar essa aresta com uma busca binária.
Mas uma busca binária requer que se disponha de elementos em ordem, e a ordenação de coisas, por sua vez,
requer algum meio de compará-las. Essa comparação é o assunto das próximas seções.
Voltando à construção do fecho, ela tem duas etapas: construı́mos um fecho inicial, com poucos pontos, e depois
vemos quais pontos devem ser acrescentados a ele.
h Encontra o fecho convexo da região 19 i ≡
h Inicializa fecho e p novo , de modo que pontos < pnovo não precisem mais ser analisados 68 i
while (p novo < N ) {
h Coloca pnovo no fecho se necessário, removendo pontos que devem sair 69 i;
lis ( );
++ p novo ;
/∗ Próximo ponto não analisado. ∗/
}
Código utilizado no trecho 9.
20. Vamos falar de bastante coisa agora, antes de voltarmos à inicialização do fecho e ao seu incremento. É bom
segurar o chapéu. Em algumas páginas estaremos de volta, quiçá mais experientes.
8
21.
Comparando com pontos do fecho
Para comparar pnovo com os pontos do fecho, vamos usar uma ordenação angular (figura 4), inspirada no algoritmo
de Graham. Queremos uma ordenação que coincida com a orientação em sentido horário do fecho. Diremos que
p precede o ponto q, denotado p ≺ q, se o ângulo α = pp\
baixo q, medido em sentido horário satisfaz 0 < α < 2π.
A definição é análoga para sucessão. Note que, quando comparamos pontos da coleção, sempre vale < 2π. Isso
pois pbaixo é o ponto de menor x-coordenadas entre os pontos de menor y-coordenada. Isso também quase sempre
equivale a dizer que, partindo de p, e passando por pontos do fecho em sentido horário, encontramos q antes de
chegar a pbaixo . (Você consegue identificar quando essa analogia pode furar?)
aumento
p
q
α
pbaixo
Figura 4: Ordenação angular. Na figura p ≺ q ⇐⇒ α > 0.
Que fazer quando α é 0? Como p e q se comparam nesse caso? Queremos preservar a analogia com a ordenação
horária do fecho, de modo que p ≺ q quando p precede q numa volta em sentido horário, partindo de pbaixo .
Vamos associar a cada vértice do fecho uma de suas arestas. A aresta associada é a o conecta ao ponto seguinte,
no sentido horário, no fecho. Assim a aresta do ponto i é (i, sucessor (i)). É essa aresta que usaremos para decidir
como comparar p e q quando α é 0. A partir de agora vamos assumir que p está no fecho, e que estamos comparando
p e q. Primeiro, note que se o α é zero, então p, q e pbaixo são colineares. Há dois casos a considerar:
• O próximo ponto do fecho, sucessor (p) = j, é colinear aos outros três pontos (pbaixo , p e q). Nesse caso,
→
− −
consideramos os vetores pj e →
pq.
– Se os vetores apontam para sentidos opostos, então q ≺ p;
– caso contrário, p ≺ q.
→
− −
• Se os vetores pj e →
pq não são paralelos (ou seja, j não é colinear aos outros três pontos), dizemos p ≺ q.
Segure as pontas, vamos tentar intuir melhor o que essa definição significa. Por agora, o importante é perceber
que, dois pontos satisfazem sempre uma das duas afirmações: p ≺ q ou p q.
Intuição do significado — adicionar!
Figura com os quadro casos: α 6= 0; sucessor (p) não-colinear; H[p] colinear e vetores com mesmo sentido;
sucessor (p) colinear e vetores com sentido oposto. Caso que não ocorre: sucessor (p) não-colinear e à esquerda
−−→
estrita de −
p−
baixo p.
Uma observação interessante: se p e q pertencem ao fecho (p, q 6= pbaixo ), então a única situação em que são
colineares a pbaixo é se eles estão no inı́cio ou no fim da sequência ordenada de pontos do fecho (podem estar no
inı́cio e no fim, se a sequência consiste de pontos colineares). Isso porque o fecho é convexo, e se se p, q e pbaixo são
colineares, e existem pontos a ≺ p, q ≺ b do fecho, então necessariamente a ou b é colinear a p e q. Trocando em
miúdos, se existem pontos no fecho colineares a pbaixo , então ocorre ao menos uma das duas coisas: todos os pontos
que sucedem qualquer desses dois são também colineares a pbaixo , ou todos os pontos que precedem qualquer desses
dois pontos são também colineares a pbaixo .
A vantagem mais significativa desta ordenação logo ficará clara. Perceba que, como pbaixo é um extremo da
coleção, sabemos que em nenhum passo do algoritmo incremental ele será removido do fecho. Uma consequência
desse fato é que, se v1 ≺ v2 são os extremos da parte do fecho que é vista pnovo (vide figura2), então pbaixo não é
nenhum dos vértices no interior do trecho. Ele pode ser um dos extremos, mas podemos cuidar desse caso à parte.
Ora, sabemos que a porção da fronteira do fecho que é vista por pnovo forma um único pedaço3 , de extremos v1 e v2 .
Logo, os vértices w que saem do fecho com a entrada de pnovo satisfazem v1 6= w, v2 6= w, e sobretudo
v1 ≺ w ≺ v2 !
3 Ou seja, se u e v são vértices que devem ser removidos, então todos os vértices no fecho entre eles também devem ser removidos
também.
9
Há ainda outra vantagem nessa ordenação. É que podemos comparar dois elementos sem grandes dores de
cabeça. Se os pontos são co-lineares, um pouco de geometria analı́tica nos ajudará a derivar o teste adequado. Se
−−→ −−−−→
α > 0, podemos comparar os pontos usando o sinal do produto interno (euclideano) dos vetores −
p−
baixo p e pbaixo q
(tomados no plano z = 0)
−
−−→ −−−−→
p−
baixo p × pbaixo q = 0, 0, (xp − xpbaixo ) · (yq − ypbaixo ) − (xq − xpbaixo ) · (yp − ypbaixo ) .
−−→
Essa fórmula resulta um valor negativo se q está à direita de −
p−
baixo p; zero se os pontos são colineares, e um valor
positivo se está à esquerda.
Podemos (e vamos) usar essa expressão também para testar se pnovo está à esquerda ou direita de uma aresta
do polı́gono.
Notação. Em breve vamos falar um pouco das arestas do fecho, que são as arestas entre dois pontos consecutivos
do fecho, e uma notação será útil: quando falarmos de uma aresta (i, j), em que i e j são pontos da coleção, deixamos
implı́cito que nos nos referimos à aresta percorrida a partir de i na direção de j. Isso será importante quando nos
falarmos de pontos à esquerda ou à direita de uma aresta: são os pontos que ficam à esquerda ou direita quando a
aresta é percorrida segundo essa orientação.
Voltamos a falar da comparação. Queremos construir uma primitiva menor (i, j) que diga se o ponto i é menor
do que o ponto j. Assumimos que j está no fecho. Então i ≺ j quando
−−−−→
1. α 6= 0 e temos que i está estritamente à esquerda do vetor pbaixo j;
2. α = 0 e valem
(a) i, j e sucessor (j) são colineares, e
→
− −−−−−−−−→
(b) os vetores ji e jsucessor (j) têm sentidos opostos.
No último item da lista está a comparação que falta detalhar. Simplificamos computacionalmente o teste (que
poderia ser feito com o produto escalar dos vetores) se notamos que ele só é relevante quando os pontos são colineares
(algo que já sabemos se testamos antes que α 6= 0). Bom, nesse caso, podemos inferir de que lado do ponto j estão
i e sucessor (j) comparando suas x-coordenadas com as de j. Se os pontos estão verticalmente alinhados, então
usamos a y-coordenada.
Paremos um pouco e vejamos o que temos. Criamos uma ordenação dos pontos do fecho que está de acordo com
a orientação de seus vértices em sentido sentido horário. Não só isso, essa ordem é estrita, no sentido de que dois
pontos distintos são sempre comparaáveis e um é menor do que o outro — igualdade não acontece.
Em termos práticos, o sucessor de um ponto i, é exatamente sucessor (i)! De modo análogo, antecessor (sucessor (i))
é i. Um tipo de mágica, isso.
Quer saber se um pnovo está dentro do polı́gono do fecho? Fazemos uma busca binária pelos vértices do fecho.
O último vértice p que virmos na busca é ou o menor dos vértices do fecho maior que pnovo , ou o maior dos vértices
do fecho menor que pnovo . O resultado da comparação de pnovo e p nos diz qual dos casos vale. E daı́?
Bom, digamos que p ≺ pnovo . Então, podemos decidir se pnovo está dentro, fora, ou na fronteira do polı́gono do
fecho observando sua posição relativa à aresta (p, sucessor (p)), já que p ≺ pnovo ≺ sucessor (p). A ideia é análoga
se p pnovo , só que usamos a aresta (antecessor (p), p). Seja e a aresta em questão.
Se o ponto está à sua esquerda (estrita), então ele está fora do polı́gono. Se é colinear à aresta, então temos
(de graça) que ele é um ponto interior da aresta — ou seja, pertence ao segmento de reta da aresta. E esses são
justamente os dois casos em que o ponto deve ser inserido no fecho.
Resumindo: nossa ordenação permite fazer uma busca binária no conjunto dos vértices que estão no fecho. Ao
término da busca, tomando o sucessor ou o antecessor do ponto em questão, conseguimos determinar (em tempo
constante) se o ponto deve ou não ser acrescentado ao fecho.
Definimos agora as operações que permitem comparar pontos, e testar colinearidade. As operações são implementadas usando macros por uma questão de eficiência. Como a maior parte das vezes estamos usando pbaixo (que
nunca muda) como referência, algumas dessas macros têm duas versões, uma das quais é geral , equanto a outra usa
as coordenadas de pbaixo como referência.
Como estaremos lidando com números em ponto flutuante, definimos uma constante eps que é a nossa precisão:
dois números que diferem por menos do que isso são iguais para nós.
10
#define eps 10 · 10−7
/∗ Não precisa ser grande, vamos arredondar bastante. ∗/
#define produto interno (i, j) ((X[i] − X[0]) ∗ (Y [j] − Y [0]) − (X[j] − X[0]) ∗ (Y [i] − Y [0]))
/∗ O produto interno que mais vamos calcular usa pbaixo como referência. ∗/
#define produto interno geral (ref , i, j)
/∗ ref é o ponto comum aos vetores. ∗/
((X[i] − X[ref ]) ∗ (Y [j] − Y [ref ]) − (X[j] − X[ref ]) ∗ (Y [i] − Y [ref ]))
/∗ α = 0 ∗/
#define colineares (i, j) (fabs (produto interno (i, j) < eps ))
/∗ pontos ref , i e j colineares? ∗/
#define colineares geral (ref , i, j)
(fabs (produto interno geral (ref , i, j) < eps ))
/∗ =⇒ α 6= 0 ∧ i ≺ j ∗/
#define direita estrita (i, j) (produto interno (i, j) < −eps )
#define direita estrita geral (ref , i, j)
/∗ ponto j à direita do segmento (ref , i), orientado de ref para i ∗/
(produto interno geral (ref , i, j) < −eps )
/∗ =⇒ α 6= 0 ∧ i j ∗/
#define esquerda estrita (i, j) (produto interno (i, j) > eps )
#define esquerda estrita geral (ref , i, j)
/∗ ponto j à esquerda do segmento (ref , i), orientado de ref para i ∗/
(produto interno geral (ref , i, j) > eps )
#define sentidos opostos (ref , p1 , p2 )
−−−→ −−−→
/∗ Assume que ref p1 e ref p2 são colineares. Têm sentidos opostos? ∗/
((X[p1 ] > X[ref ] + eps ∧ X[p2 ] + eps < X[ref ])
∨ ((fabs (X[p1 ] − X[p2 ]) < eps ) ∧ (Y [p1 ] > Y [ref ] + eps ∧ Y [p2 ] + eps < Y [ref ])))
#define menor (pto , no )
/∗ ponto [no ] está no fecho. ∗/
((esquerda estrita (pto , ponto [no ])) ∨ (((colineares (pto , ponto [no ])) ∧ (colineares (pto ,
ponto [H[no ]])) ∧ sentidos opostos (ponto [no ], pto , ponto [H[no ]]))))
22.
A função fabs ( ) está definida em math .h.
h Arquivos de cabeçalho 8 i +≡
#include <math.h>
23. Agora que estamos mais entendidos em comparações usando double, podemos terminar algo que deixamos
para trás.
h Ponto pnovo deve entrar no lugar de pbaixo 23 i ≡
(Y [p baixo ] > Y [p novo ] + eps ∨ (fabs (Y [p baixo ] − Y [p novo ]) < eps ∧ X[p baixo ] > X[p novo ] + eps ))
Código utilizado no trecho 11.
24. h Ponto pnovo deve entrar no lugar de palto 24 i ≡
(Y [p alto ] + eps < Y [p novo ] ∨ (fabs (Y [p alto ] − Y [p novo ]) < eps ∧ X[p alto ] + eps < X[p novo ]))
Código utilizado no trecho 11.
h O ponto 0 tem y-coordenada menor do que a do ponto 1, ou ambos têm mesma y-coordenada mas 0 tem
x-coordenada menor 25 i ≡
(Y [0] + eps < Y [1] ∨ (fabs (Y [0] − Y [1]) < eps ∧ X[0] + eps < X[1]))
25.
Código utilizado no trecho 10.
11
26.
Mı́nimo e máximo elemento com a propriedade P
A discussão que acabamos de fazer sugere que estaremos buscando “intervalos” de elementos em uma sequência
ordenada. E queremos fazer isso com um mı́nimo de eficiência (já viu um entomólogo aborrecido?).
Importante aqui é para quê queremos os intervalos: buscamos o intervalo de pontos que serão substituı́dos por
pnovo no fecho. Vamos digredir um pouco e abstrair o que queremos fazer.
Temos uma sequência ordenada, um elemento pnovo que queremos colocar nela, e uma dada propriedade P.
Queremos encontrar o menor elemento pmin e o maior elemento pmax na sequência (min ≺ pmax ) tais que
• ambos satisfazem P,
• se trocamos os elementos entre eles por pnovo , a sequência continua ordenada.
Note que nem toda ordenação nos ajuda a fazer essa busca. Isso depende de como a propriedade “aparece” na
sequência ordenada. Felizmente, a propriedade que nos interessa — ser visto por pnovo — é bem-comportada: ela
sempre vale para um único intervalo (possivelmente vazio) de elementos na sequência.
Voltando agora para nossos requisitos, o ponto crucial para a eficiência de nosso algoritmo é que a remoção e
inserção de elementos não pode demorar muito (e deve preservar a ordenação do fecho). Optamos por guardar a
informação da ordenação em uma árvore binária de busca balanceada. Além disso, como já dissemos, guardamos o
sucessor e o antecessor de um ponto. (Pode parecer que um deles basta, mas é importante que encontrar tanto um
como outro seja uma tarefa eficiente. Vamos discudir isso com algum detalhe logo.)
Como já discutimos, se sabemos que pnovo deve entrar no fecho, as propriedades da nossa ordenação facilitam
atualizar o fecho: encontramos o “maior” e o “menor” pontos do fecho que estão em arestas vistas por pnovo ,
removendo a seguir os pontos, e colocando pnovo em seu lugar.
Como os pontos do fecho estão em uma árvore binária de busca, os algoritmos para encontrar o maior e o
menor ponto que vêem pnovo ficam simples. Se buscamos o maior ponto em uma aresta vista por pnovo : partindo
da raiz, encontramos (recursivamente) o maior ponto em uma aresta vista por um ponto na sub-árvore dos pontos
maiores que a raiz, e retornamos esse ponto. Se não há ninguém satisfazendo a propriedade (ser visto por pnovo ),
então testamos se a raiz é vista por pnovo , retornando a raiz se é verdade. Por fim, se a raiz também não é vista,
retornamos o resultado recursivo da chamada na sub-árvore menor. O algoritmo é simétrico para a busca do menor
ponto visto por pnovo .
Por razões de eficiência, essa e outras rotinas serão implementadas em uma forma iterativa. Postergamos a
apresentação dos detalhes para depois, quando soubermos mais sobre a árvore.
12
27.
A árvore binária de busca balanceada
As próximas seções tratam basicamente do gerenciamento de memória e das primitivas para uso da árvore binária.
Há vários tipos de árvores por aı́, cada qual com seus pontos fortes. Correndo o risco de deixar boas soluções
de fora, restringimos nossa discussão à comparação entre árvore rubro-negra e AVL.
Sinceramente, devo dizer que não estou totalmente certo de que a decisão tomada esteja solidamente fundamentada. Por isso mesmo acho importante deixar claro qual a sua base.
O fato é que este algoritmo parece bastante sensı́vel à ordem em que os pontos são processados4 — além de ser,
claro, sensı́vel à proporção de pontos que está no fecho. A partir do ponto em que o fecho todo está na árvore, ela
não sofre mais inserções, só buscas. Por outro lado, é certo que para cada ponto testado, são feitas
• duas buscas para encontrar os extremos da região vista,
• no máximo uma inserção (de pnovo ), e
• uma remoção para cada ponto que sai do fecho intermediário com a entrada de pnovo .
Em geral, o fecho intermediário tem pontos “definitivos” (que não vão mais sair do fecho), e outros pontos, que
estão esperando a entrada de um ponto definitivo para serem removidos.
Parece que a árvore adequada depende criticamente de quantos pontos se espera que sejam removidos com a
entrada de um ponto no fecho. Se “poucos”, então a árvore sofre mais consultas do que inserções e remoções. . . ?
Não parece claro.
Num compromisso em que pesou a curiosidade, optamos por usar uma árvore rubro-negra inclinada para a
esquerda (left-leaning red-black tree), na esperança de retornar em breve, com mais conhecimento de causa, e pôr
as coisas preto no branco.
28. Guardamos o ponto que é a raiz da árvore em uma variável global raiz . Um ponteiro nulo tem o valor NIL.
Como a árvore é rubro-negra, e além disso as folhas de tais árvores são negras, definimos constantes e primitivas
para as cores também.
#define
#define
#define
#define
#define
NIL −1
rubro 0
negro 1
eh rubro (p) (p 6= NIL ∧ cor [p] 6= negro )
eh negro (p) (p ≡ NIL ∨ cor [p] 6= rubro )
/∗ Equivale a ¬eh rubro (p). ∗/
h Constantes e variáveis globais 6 i +≡
int raiz = NIL;
29.
Cada nó n da árvore tem sete campos
• ponto [n] guarda o ponto do fecho que representa,
• pai [n] ancestral direto (NIL se n é a raiz),
• filho menor [n] e filho maior [n], de modo que filho menor [n] ≺ n ≺ filho maior [n], e
• cor [n] é a cor do nó: rubro ou negro .
• H[n] é o (nó) sucessor de n se ele não é o maior nó da árvore; é NIL caso seja.
• antecessor em H [n] é o (nó) antecessor de n se ele não é o menor nó da árvore; é NIL caso seja.
Os vetores são alocados dinamicamente, mas quando o programa inicia os vetores associados à árvore apontam
para vetores estaticamente alocados. Com isso, só faremos alocação de memória quando o tamanho da árvore excede
o limite tamanho inicial arvore .
#define tamanho inicial arvore tamanho inicial fecho
4O
que sugere que talvez haja um ganho em aleatorizar a ordem em que os pontos são armazenados. . .
13
h Constantes e variáveis globais 6 i +≡
int ponto estatico [tamanho inicial arvore ], pai estatico [tamanho inicial arvore ],
filho menor estatico [tamanho inicial arvore ], filho maior estatico [tamanho inicial arvore ],
H estatico [tamanho inicial arvore ], antecessor em H estatico [tamanho inicial arvore ];
short cor estatico [tamanho inicial arvore ];
int ∗ponto = ponto estatico , ∗pai = pai estatico , ∗filho menor = filho menor estatico ,
∗filho maior = filho maior estatico , ∗H = H estatico , ∗antecessor em H = antecessor em H estatico ;
short ∗cor = cor estatico ;
int menor no = NIL, maior no = NIL;
30. Definimos também os “apelidos” de H e antecessor em H .
#define sucessor (x) (H[(x)] 6= NIL ? ponto [H[(x)]] : 0)
/∗ pbaixo é 0. ∗/
#define antecessor (x) (antecessor em H [(x)] 6= NIL ? ponto [antecessor em H [(x)]] : 0)
/∗ pbaixo é 0. ∗/
31. Gerenciamos o espaço livre com o auxı́lio das variáveis tamanho arvore e proxima posicao livre . A primeira
é o número de posições que existem em cada um dos vetores apontados por ponto , pai , etc., enquanto a segunda
aponta para o inı́cio de uma lista ligada de posições livres, em que os elementos estão ligados pelo seu campo pai ,
como veremos. A variável proxima posicao livre é mantida sempre < tamanho arvore , e a posição com esse ı́ndice
está livre (em todos os vetores). Além disso,
• ou pai [proxima posicao livre ] ≡ NIL,
• ou pai [proxima posicao livre ], aponta para uma posição livre (em todos os vetores), de modo que atribuir
proxima posicao livre = pai [proxima posicao livre ] mantém as propriedades da variável.
O pedido de um no livre ( ) retorna o ı́ndice de uma posição ainda não usada nos vetores, e avança o apontador
para uma posição livre. Se esse avanço invalida as propriedades do apontador (i.e., se com isso proxima posicao livre ≡
tamanho arvore ), fazemos uma chamada para aumenta tamanho arvore ( ), que dobra o espaço disponı́vel. O primeiro aumento é algo diferente dos demais, já que passamos da alocação estática para um regime de alocação
dinâmica, e o conteúdo dos vetores estáticos é copiado para os vetores alocados. Temos ainda inicializa arvore ( ) e
libera arvore ( ), com as funções óbvias de inicialização e liberação da estrutura de dados.
Com isso podemos escrever o código que gerencia a alocação e liberação de memória.
#define inicializa arvore () do
{
proxima posicao livre = 0;
pai [proxima posicao livre ] = NIL;
raiz = NIL;
menor no = maior no = NIL;
}
while (0)
#define aumenta tamanho arvore () do
{
if (tamanho arvore 6= tamanho inicial arvore ) {
/∗ A árvore já foi aumentada alguma vez. ∗/
tamanho arvore ∗= 2;
ponto = realloc (ponto , tamanho arvore );
pai = realloc (pai , tamanho arvore );
filho menor = realloc (filho menor , tamanho arvore );
filho maior = realloc (filho maior , tamanho arvore );
H = realloc (H, tamanho arvore );
antecessor em H = realloc (antecessor em H , tamanho arvore );
cor = realloc (cor , tamanho arvore );
}
else {
tamanho arvore ∗= 2;
ponto = malloc (sizeof (int) ∗ tamanho arvore );
pai = malloc (sizeof (int) ∗ tamanho arvore );
filho menor = malloc (sizeof (int) ∗ tamanho arvore );
filho maior = malloc (sizeof (int) ∗ tamanho arvore );
14
H = malloc (sizeof (int) ∗ tamanho arvore );
antecessor em H = malloc (sizeof (int) ∗ tamanho arvore );
cor = malloc (sizeof (short) ∗ tamanho arvore );
tamanho arvore /= 2;
memcpy (ponto , ponto estatico , sizeof (int) ∗ (tamanho arvore ));
memcpy (pai , pai estatico , sizeof (int) ∗ (tamanho arvore ));
memcpy (filho menor , filho menor estatico , sizeof (int) ∗ (tamanho arvore ));
memcpy (filho maior , filho maior estatico , sizeof (int) ∗ (tamanho arvore ));
memcpy (H, H estatico , sizeof (int) ∗ (tamanho arvore ));
memcpy (antecessor em H , antecessor em H estatico , sizeof (int) ∗ (tamanho arvore ));
memcpy (cor , cor estatico , sizeof (short) ∗ (tamanho arvore ));
tamanho arvore ∗= 2;
}
}
while (0)
#define libera arvore () do
{
if (tamanho arvore > tamanho inicial arvore ) {
free (ponto );
free (pai );
free (filho maior );
free (filho menor );
free (H);
free (antecessor em H );
free (cor );
tamanho arvore = tamanho inicial arvore ;
}
ponto = ponto estatico ;
pai = pai estatico ;
filho menor = filho menor estatico ;
filho maior = filho maior estatico ;
H = H estatico ;
antecessor em H = antecessor em H estatico ;
cor = cor estatico ;
}
while (0)
/∗ Memória foi alocada ∗/
h Constantes e variáveis globais 6 i +≡
int tamanho arvore = tamanho inicial arvore , proxima posicao livre = 0;
32. h Arquivos de cabeçalho 8 i +≡
#include <string.h>
/∗ Para memcpy ( ). ∗/
33. Obtendo nó livre, e liberando nó.
#define libera no (no ) do
{
double libera (no );
pai [no ] = proxima posicao livre ;
proxima posicao livre = no ;
}
while (0)
h Funções 33 i ≡
int no livre ( )
{
int resposta ;
15
resposta = proxima posicao livre ;
if (pai [proxima posicao livre ] ≡ NIL) {
++ proxima posicao livre ;
if (proxima posicao livre ≡ tamanho arvore ) aumenta tamanho arvore ( );
pai [proxima posicao livre ] = NIL;
}
else proxima posicao livre = pai [proxima posicao livre ];
return resposta ;
}
Veja também os trechoss 38, 47, 51, 52, 56, 60, 87, 89 e 91.
Código utilizado no trecho 5.
34. h Pré-declaração de funções 34 i ≡
int no livre ( );
Veja também os trechoss 48 e 90.
Código utilizado no trecho 5.
16
35.
Árvore rubro-negra
Uma implementação de árvore rubro-negra “inclinada para a esquerda”. Garantimos que todo nó é rubro ou negro ,
toda folha (NIL) é negra, os filhos de um nó rubro são negros, nenhum filho direito é rubro , e, por fim, o caminho
de um nó até qualquer de suas folhas tem o mesmo número de nós negros. Para compreender melhor esse tipo de
árvore, discutiremos um pouco suas propriedades.
Quando percorremos um caminho a partir da raiz da árvore (embora isso seja válido para qualquer nó, de modo
geral) até alguma das folhas da árvore, as restrições da árvore mencionadas acima implicam que nunca passaremos
por dois nós vermelhos em seguida. Como o número de nós negros pelos quais passamos é constante, não importa em
qual folha terminamos, o caminho mais longo até alguma folha é no máximo duas vezes mais longo que o caminho
mais curto.
Para entender o balanceamento de árvores rubro-negras, vamos virar o problema e observar outros tipos de
árvores, a árvore 2–3 e árvore 2–3–4. Veremos como esse tipo de árvore pode ser mantido perfeitamente balanceado,
e que árvores rubro-negras (em particular árvores rubro-negras inclinadas, digamos, à esquerda) possuem uma
correspondência com essas estruturas. Essa correspondência pode ser mantida sem grandes penas, e o resultado é
uma árvore com certas garantias de balanceamento — e, consequentemente, no tempo que leva para buscar, inserir
e remover elementos seus.
Esses tipos de árvore são generalizações de árvores binárias. Em uma árvore 2–3, os nós podem ter dois ou três
filhos, enquanto em uma árvore 2–3–4 podem ter dois, três ou quatro filhos. Esses nós são chamados 2-nós, 3-nós
ou 4-nós, dependendo da quantidade de filhos que têm. Um nó com k filhos têm k − 1 chaves. Por exemplo, um
3-nó p = (a, b) com chaves a e b (a < b) aponta para três filhos. Um deles é raiz de uma sub-árvore em que todas
as chaves têm valor < a; os nós de outra das sub-árvores têm chaves com valores entre a e b. A terceira sub-árvore,
não é surpresa, tem nós com chaves de valor maior do que b. Árvores 2–3–4 são definidas de modo análogo.
Acontece que é possı́vel manter essas árvores completamente balanceadas (qualquer caminho da raiz até alguma
folha passa pelo mesmo número de nós). Por enquanto, nos limitamos a descrever como é o mapeamento (um
para um!) desse tipo de árvores às árvores rubro-negras inclinadas para a esquerda (arnie). Desenvolvemos o
ferramental para manutenção da estrutura (preservando o mapeamento!) aos poucos, nas próximas seções. Ao fim
deste último mergulho, voltaremos quiçá um pouco mais sábios, e podemos cuidar das mariposas (as que ainda não
houverem fugido).
O mapeamento é o seguinte: cada 2-nó corresponde a um nó negro na arnie; um 3-nó está associado a um nó
negro com um filho menor rubro ; um 3 nó equivale a um nó negro com dois filhos rubros . As folhas e raiz da árvore
são negras.
36. Buscamos na arnie de modo análogo ao que farı́amos em uma árvore binária. Se a chave buscada não é a do
nó em que estamos, identificamos a qual intervalo definido pelas chaves do nó a chave pertence, e seguimos a busca
recursivamente pela sub-árvore associada a esse intervalo.
Aqui vamos frequentemente buscar um ponto que não está presente na árvore, com o objetivo de encontrar qual
seria seu sucessor ou antecessor se ele fosse acrescentado à árvore. Essa operação, contudo, só acontece em um
ponto do programa, e por isso vamos deixar o procedimento lá, conscientes de que em algum nı́vel isso parece ferir o
“encapsulamento” da árvore binária. (Mas, de fato, este programa já feriu o encapsulamento em alguns pontos. . . )
17
37.
Inserção
A inserção em árvores 2–3–4 ocorre na última folha encontrada em pela busca. Se o nó é um 2-nó ou um 3-nó
a inserção pode ser feita sem alterar o balanceamento da árvore. Para evitar que a folha seja um 4-nó, podemos
transformar (leia-se dividir ) os 4-nós que encontramos pelo caminho.
Se a raiz for um 4-nó, podemos transformá-la em três 2-nós (“subindo” sua chave do meio). Ou seja, a busca
sempre parte de um nó com menos de três chaves. Se, em algum passo intermediário, vamos passar de um 2-nó ou
de um 3-nó para um 4-nó, podemos “subir” uma chave desse 4-nó para o nó em que estamos, antes de avançar para
a sub-árvore do (ex-4)-nó. Assim, garantimos que nunca estamos em um 4-nó, e a inserção é simples.
Acontece que não precisamos fazer isso! Ao menos não quando descemos pela árvore. Numa etapa final, após a
inserção, podemos retornar pelo caminho percorrido, consertando os problemas que criamos. . . desde que consigamos
assegurar que qualquer problema criado de fato fica no caminho de volta.
O que chamamos acima de “subir” uma chave nada mais é do que dividir um nó que tem mais de uma chave.
As ferramentas que nos ajudam a fazer isso em nossa arnie são rotações e trocas de cor.
Não descreveremos aqui o que é uma rotação, mas vale comentar que tanto rotações quanto trocas de cor podem
destruir as propriedades da arnie pelas quais tanto zelamos. Podemos consertar as coisas, contudo, se depois de
inserido o nó (ou removido, já que a ideia é parecida) retrocedermos “geração por geração” na árvore, seguindo os
ponteiros pai [ ] do nó. Esse trabalho é feito por h Conserta o que foi bagunçado 45 i.
38. A inserção começa com uma busca pelo ponto de inserção. Essa busca continua até que os limites da árvore.
Nesse ponto, no atual aponta para o último vértice visitado antes de uma folha da árvore ter sido atingida — as
folhas são sempre NIL.
#define verdade 1
h Funções 33 i +≡
void insere (int p novo )
{
h Variáveis locais de insere 46 i
if (raiz 6= NIL) {
/∗ Árvore não está vazia. ∗/
no atual = raiz ;
while (verdade ) {
h Segue a busca, avançando no atual . Prepara a inserção em uma folha de no atual e escapa do loop 39 i
}
h Insere pnovo na folha 44 i
h Conserta o que foi bagunçado 45 i
}
else {
h Insere pnovo na árvore vazia 43 i
}
}
39. h Segue a busca, avançando no atual . Prepara a inserção em uma folha de no atual e escapa do loop 39 i ≡
if (h pnovo ≺ ponto [no atual ] 40 i) {
printf ("(%d) < (%d)\n", p novo , ponto [no atual ]);
if (filho menor [no atual ] ≡ NIL) {
filho menor [no atual ] = no livre ( ); proximo no = filho menor [no atual ];
h Altera apontadores de antecessor e sucessor para inclusão do filho menor 41 i
break;
}
no atual = filho menor [no atual ];
}
else {
printf ("(%d) > (%d)\n", p novo , ponto [no atual ]);
if (filho maior [no atual ] ≡ NIL) {
filho maior [no atual ] = no livre ( ); proximo no = filho maior [no atual ];
h Altera apontadores de antecessor e sucessor para inclusão do filho maior 42 i
break;
}
18
no atual = filho maior [no atual ];
}
Código utilizado no trecho 38.
40. h pnovo ≺ ponto [no atual ] 40 i ≡
menor (p novo , ponto [no atual ])
Código utilizado no trecho 39.
41. h Altera apontadores de antecessor e sucessor para inclusão do filho menor 41 i ≡
if (antecessor em H [no atual ] 6= NIL) {
H[antecessor em H [no atual ]] = proximo no ;
/∗ Altera sucessor do antecessor. ∗/
}
else {
/∗ O nó que estamos inserindo é o menor na árvore. ∗/
menor no = proximo no ;
}
antecessor em H [proximo no ] = antecessor em H [no atual ];
H[proximo no ] = no atual ;
antecessor em H [no atual ] = proximo no ;
Código utilizado no trecho 39.
42. h Altera apontadores de antecessor e sucessor para inclusão do filho maior 42 i ≡
if (H[no atual ] 6= NIL) {
/∗ Altera antecessor do sucessor. ∗/
antecessor em H [H[no atual ]] = proximo no ;
}
else {
/∗ O nó que estamos inserindo é o maior na árvore. ∗/
maior no = proximo no ;
}
H[proximo no ] = H[no atual ];
antecessor em H [proximo no ] = no atual ;
H[no atual ] = proximo no ;
Código utilizado no trecho 39.
43. h Insere pnovo na árvore vazia 43 i ≡
raiz = no livre ( );
ponto [raiz ] = p novo ;
cor [raiz ] = negro ;
filho menor [raiz ] = filho maior [raiz ] = NIL;
pai [raiz ] = NIL;
/∗ A raiz é o máximo e o mı́nimo. ∗/
H[raiz ] = antecessor em H [raiz ] = NIL;
menor no = maior no = raiz ;
Código utilizado no trecho 38.
44. h Insere pnovo na folha 44 i ≡
ponto [proximo no ] = p novo ;
cor [proximo no ] = rubro ;
filho menor [proximo no ] = filho maior [proximo no ] = NIL;
pai [proximo no ] = no atual ;
Código utilizado no trecho 38.
19
45. Subimos pela árvore, ancestral por ancestral, consertando as infrações às regras da arnie que foram deixadas
em nosso caminho. Dá algum trabalho verificar que todo estrago que pode ter sido feito vai ser encontrado nesse
processo. . . (quem sabe façamos isso um dia?) Mas ao menos vamos comentar os três tipos de infração.
Um tipo de infração é um nó com filho direito vermelho. Esse caso resolvemos com uma rotação na direção
do filho menor . Outros tipo é a ocorrência de dois filho menor vermelhos em seguida. Isso resolvemos com uma
rotação na direção do filho maior do primeiro ancestral comum5 . Finalmente, se ambos os filhos de um nó são
vermelhos, trocamos as cores dos filhos e do nó (isso é necessário para que que possamos “avançar” para o ancestral
sem medo de algum infração de sete cabeças).
h Conserta o que foi bagunçado 45 i ≡
printf ("O conserto está para começar.\n");
lis ( );
proximo no = no atual ;
while (proximo no 6= NIL) {
no atual = proximo no ;
#ifdef BLOBDIGNAG
printf ("no_atual = %d, ponto[no_atual] = %d, filho_maior[no_atual] = %d, filho_menor[no\
_atual] = %d, pai[no_atual] = %d\n", no atual , ponto [no atual ], filho maior [no atual ],
filho menor [no atual ], pai [no atual ]);
getchar ( );
#endif
if (eh rubro (filho maior [no atual ])) no atual = rotaciona menor (no atual );
if (eh rubro (filho menor [no atual ]) ∧ eh rubro (filho menor [filho menor [no atual ]]))
no atual = rotaciona maior (no atual );
if (eh rubro (filho menor [no atual ]) ∧ eh rubro (filho maior [no atual ])) troca cores (no atual );
proximo no = pai [no atual ];
}
raiz = no atual ;
cor [raiz ] = negro ;
printf ("O conserto terminou.\n");
Código citado no trecho 37.
Código utilizado nos trechos 38, 52, 56 e 64.
46. h Variáveis locais de insere 46 i ≡
int no atual , proximo no ;
Código utilizado no trecho 38.
47. A função rotaciona menor ( ) assume que filho maior [p] 6= NIL e cor [filho maior [p]] ≡ rubro , e rotaciona maior ( )
assume que filho menor [p] 6= NIL e cor [filho menor [p]] ≡ rubro .
h Funções 33 i +≡
int rotaciona menor (int p)
{
int q;
q = filho maior [p];
filho maior [p] = filho menor [q];
filho menor [q] = p;
pai [q] = pai [p];
pai [filho maior [p]] = p;
pai [p] = q;
cor [q] = cor [p];
cor [p] = rubro ;
return q;
}
5 Note
que isso significa que o concerto não pode iniciar com o pai de uma folha, não haveria nı́veis o suficiente para esse teste —
sendo assim, se houvesse algo que consertar para o pai da folha, isso tem que ser feito antes deste trecho.
20
int rotaciona maior (int p)
{
int q;
q = filho menor [p];
filho menor [p] = filho maior [q];
filho maior [q] = p;
pai [q] = pai [p];
pai [filho menor [p]] = p;
pai [p] = q;
cor [q] = cor [p];
cor [p] = rubro ;
return q;
}
48. h Pré-declaração de funções 34 i +≡
int rotaciona menor (int p);
int rotaciona maior (int p);
49.
Ajuste de cores. Se o nó p é interno, podemos usar:
#define troca cores (p) do
{
cor [p] = outra cor (cor [p]);
cor [filho menor [p]] = outra cor (cor [filho menor [p]]);
cor [filho maior [p]] = outra cor (cor [filho maior [p]]);
}
while (0)
#define outra cor (c) (1 − c)
21
50.
Remoção
Tornamos agora para a retirada de um nó da árvore. Vamos usar uma combinação de duas ideias. Primeiro, e
analogamente ao que acontece na inserção, notamos que existem nós cuja remoção é simples de fazer. Aqui, estamos
falando dos nós que contém a maior e a menor chaves de alguma sub-árvore, desde que esse nó não seja uma 2-nó.
Buscaremos um meio de garantir que o caso indesejado não aconteça, transformando a árvore à medida que buscamos
o nó que vamos remover (como na inserção, isso invalida algumas propriedades da arnie, que conseguimos consertar
exatamente como fizemos antes). A segunda ideia é remover um nó qualquer usando, por exemplo, a remoção do
menor elemento de sua sub-árvore filho maior .
Para remover o nó de maior chave, passamos de filho maior para filho maior , enquanto pudermos. Idealmente,
quando não pudermos mais prosseguir, estaremos em um 3-nó ou 4-nó, e a remoção do nó não estraga a árvore!
Trata-se então de garantir que nesse percurso o no atual nunca é um 2-nó. Podemos fazer isso combinando nósirmãos (caso tanto o nó para o qual se quer seguir “descendo” como seu irmão sejam 2-nós) ou, se o irmão do
nó tem mais do que uma chave, tomando emprestado dele uma das chaves. Como antes, usaremos as rotações e
trocas de cores para obter as transformações equivalentes da arnie, de modo que qualquer transgressão de suas
propriedades fique na linha de ancestrais do nó por onde continuamos procurando — assim podemos consertar o
estrago “na volta”.
O procedimento é análogo para a remoção do nó de menor chave, mas em geral precisamos bagunçar menos as
coisas, já que, por definição da arnie, os 3-nós e 4-nós são inclinados no sentido da sub-árvore das chaves menores.
Uma última palavra sobre o significado de carregarmos 3-nós e 4-nós à medida que prosseguimos. O invariante
que mantemos é que ou o no atual é rubro , ou o seu filho por onde pretendemos prosseguir é rubro (?). O único
caso em que não conseguimos carregar esses nós ocorre quando a árvore só tem um nó: a raiz. Esse caso podemos
tratar à parte sem problemas.
51. Usando rotações e trocas de cores, vamos construir agora duas novas primitivas: move rubro para menor (no )
e move rubro para maior (no ). São análogas, então vamos discutir apenas a segunda.
A ideia é assegurar o invariante (?) para o filho maior (em suma, estamos em um 3-nó ou 4-nó). Partimos do
pressuposto que no é rubro, pois se seu filho maior é rubro, esse método não terá sido chamado. Trocamos as cores
de no e de seus filhos com troca cores (no ). Mas isso pode ter causado uma violação das propriedades da arnie
no filho menor do nó. Isso acontece se filho menor [filho menor [no ]] é vermelho também. Nesse caso, eliminamos a
transgressão com uma rotação e ainda outra troca de cores.
h Funções 33 i +≡
int move rubro para maior (int no )
{
troca cores (no );
if (eh rubro (filho menor [filho menor [no ]])) {
no = rotaciona maior (no );
troca cores (no );
}
return no ;
}
int move rubro para menor (int no )
{
troca cores (no );
if (eh rubro (filho menor [filho maior [no ]])) {
filho maior [no ] = rotaciona maior (filho maior [no ]);
no = rotaciona menor (no );
troca cores (no );
}
return no ;
}
52. Conseguimos agora remover o máximo! Se o filho menor do nó é rubro, movemos a ligação rubra com uma
rotação no sentido do filho maior — e então podemos prosseguir para esse nó mantendo o invariante (?). Se tanto
o próximo nó na busca filho maior [no ] quanto seus filhos6 são negros, então movemos a ligação rubra do nó atual
para o seu filho maior usando a primitiva que acabamos de criar. Por fim, quando encontramos o máximo, podemos
removê-lo sem maiores pesares, passando depois disso à tarefa de “normalizar” os ancestrais na arnie.
6 Na
verdade só os filhos menores de nó e de seu filho maior precisam ser testados, graças à inclinação da arnie.
22
h Funções 33 i +≡
void remove maximo de subarvore (int no )
{
h Variáveis locais de remove maximo de subarvore 55 i
if (no 6= NIL) {
/∗ Sub-árvore não está vazia. ∗/
no atual = no ;
while (verdade ) {
h Segue a busca pelo máximo, garantindo nunca estar em um 2-nó. Sai do loop garantindo
proximo no ≡ filho maior [no atual ] é o máximo 53 i
}
h Remove o máximo (proximo no ) 54 i
h Conserta o que foi bagunçado 45 i
}
}
h Segue a busca pelo máximo, garantindo nunca estar em um 2-nó. Sai do loop garantindo
proximo no ≡ filho maior [no atual ] é o máximo 53 i ≡
if (eh rubro (filho menor [no atual ])) no atual = rotaciona maior (no atual );
if (filho maior [no atual ] ≡ NIL) {
/∗ Encontramos o nó com a maior chave! ∗/
proximo no = no atual ;
no atual = pai [no atual ];
break;
}
if (eh negro (filho maior [no ]) ∧ eh negro (filho menor [filho maior [no atual ]]))
no atual = move rubro para maior (no atual );
no atual = filho maior [no atual ];
53.
Código utilizado no trecho 52.
54. Testamos se no atual (que é o pai do nó a ser removido) é NIL. Isso acontece quando a árvore da qual
queremos remover o máximo tem apenas um nó.
h Remove o máximo (proximo no ) 54 i ≡
if (no atual 6= NIL) {
filho maior [no atual ] = NIL;
maior no = antecessor em H [proximo no ];
libera no (proximo no );
}
else maior no = menor no = NIL;
Código citado no trecho 58.
Código utilizado no trecho 52.
55. h Variáveis locais de remove maximo de subarvore 55 i ≡
int no atual , proximo no ;
Código utilizado no trecho 52.
56. Vamos cuidar do mı́nimo agora. A ideia básica é a mesma: garantir que não estamos em um 2-nó à medida
que a busca progride, remover o menor nó, arrumar a casa depois que a farra termina.
h Funções 33 i +≡
void remove minimo de subarvore (int no )
{
h Variáveis locais de remove minimo de subarvore 59 i
if (no 6= NIL) {
/∗ Sub-árvore não está vazia. ∗/
no atual = no ;
while (verdade ) {
h Segue a busca pelo mı́nimo, garantindo nunca estar em um 2-nó. Sai do loop garantindo
proximo no ≡ filho menor [no atual ] é o mı́nimo 57 i
23
}
h Remove o mı́nimo (proximo no ) 58 i
h Conserta o que foi bagunçado 45 i
}
}
h Segue a busca pelo mı́nimo, garantindo nunca estar em um 2-nó. Sai do loop garantindo
proximo no ≡ filho menor [no atual ] é o mı́nimo 57 i ≡
if (filho menor [no atual ] ≡ NIL) {
/∗ Dessa vez encontramos o nó com a menor chave! ∗/
proximo no = no atual ;
no atual = pai [no atual ];
break;
}
if (eh negro (filho menor [no ]) ∧ eh negro (filho menor [filho menor [no atual ]]))
no atual = move rubro para menor (no atual );
no atual = filho menor [no atual ];
57.
Código utilizado no trecho 56.
58.
Assim como em h Remove o máximo (proximo no ) 54 i, o teste é necessário.
h Remove o mı́nimo (proximo no ) 58 i ≡
if (no atual 6= NIL) {
filho menor [no atual ] = NIL;
menor no = H[proximo no ];
libera no (proximo no );
}
else maior no = menor no = NIL;
Código utilizado no trecho 56.
59. h Variáveis locais de remove minimo de subarvore 59 i ≡
int no atual , proximo no ;
Código utilizado no trecho 56.
60. Combinamos agora as ferramentas que construı́mos, para poder remover um elemento arbitrário psai da árvore.
A ideia é a seguinte: partindo da raiz, seguimos procurando o nó que queremos remover. Nesse processo, asseguramos
(usando move rubro para maior ( ) que estamos em um 3-nó ou em um 4-nó. Quando encontramos o elemento
buscado, substituı́mos o valor de sua chave pelo valor da chave de seu sucessor (o antecessor funcionaria igualmente
bem). A seguir, removemos sucessor, que é o nó de menor chave na sub-árvore filho maior do nó!
Note que não é preciso se preocupar em arrumar os nós que foram manipulados no inı́cio, já que o último passo
de remove minimo de subarvore ( ) é iniciar o concerto da árvore, que prossegue até a raiz da árvore.
h Funções 33 i +≡
void remove da arvore (int p sai )
{
h Variáveis locais de remove da arvore 67 i
if (raiz 6= NIL) {
/∗ Árvore não está vazia. ∗/
no atual = raiz ;
while (verdade ) {
h Caminha pela árvore buscando psai , e removendo-o se encontrado. Conserta a árvore e retorna. 61 i
}
}
}
24
61. Se o nó está à esquerda, use move rubro para menor , e analogamente, até encontrar o nó. . . Uma palavra
sobre a condição (? ?). Testamos apenas o filho maior para saber se o nó é uma folha. Por que? A condição anterior
garante que se o filho menor fosse vermelho, aconteceria uma rotação, e então o filho maior seria vermelho. Se o
nó vermelho é nulo, significa que a condição anterior resultou falsa, e o nó filho menor é negro também. Como para
qualquer nó a “altura negra” é igual, se o nó filho maior é NIL, então o filho menor tem que ser NIL também.
Sobre a consição (? ? ?): neste ponto, sabemos que a psai ⊀ ponto [no atual ], e que, se p sai ≡ ponto [no atual ],
então não estamos em uma folha (mais ainda, a sub-árvore maior do no atual tem pelo menos um nó não NIL).
Sendo assim, ou o nó atual é o nó buscado, ou o nó procurado está na sub-árvore maior. Em ambos os casos,
queremos garantir que a busca possa prosseguir por essa árvore.
h Caminha pela árvore buscando psai , e removendo-o se encontrado. Conserta a árvore e retorna. 61 i ≡
if (h psai ≺ ponto [no atual ] 62 i) {
printf ("(%d) < (%d)\n", p sai , ponto [no atual ]);
h “Empurra” um link rubro para o filho menor se necessário, e prossegue para esse filho. 63 i
}
else {
printf ("(%d) > (%d)\n", p sai , ponto [no atual ]);
if (eh rubro (filho menor [no atual ])) no atual = rotaciona maior (no atual );
if (ponto [no atual ] ≡ p sai ∧ filho maior [no atual ] ≡ NIL) {
/∗ (? ?) ∗/
h Estamos em uma folha (no atual ), que é o nó a ser removido. Remove no atual e percorre a árvore “ao
contrário”, consertando o que houver de errado; retorna da rotina 64 i
}
if (eh negro (filho maior [no atual ]) ∧ eh negro (filho menor [filho maior [no atual ]])) {
/∗ (? ? ?) ∗/
no atual = move rubro para maior (no atual );
}
if (ponto [no atual ] ≡ p sai ) {
h Estamos em um nó interno (no atual ), que é o nó a ser removido. Coloca o valor do sucessor de no atual
em no atual e atualiza sucessor, remove o mı́nimo do filho maior do no atual ; retorna da rotina 66 i
}
else {
no atual = filho maior [no atual ];
}
}
Código utilizado no trecho 60.
62. h psai ≺ ponto [no atual ] 62 i ≡
menor (p sai , ponto [no atual ])
Código utilizado no trecho 61.
63. h “Empurra” um link rubro para o filho menor se necessário, e prossegue para esse filho. 63 i ≡
if (eh negro (filho menor [no atual ]) ∧ eh negro (filho menor [filho menor [no atual ]])) {
no atual = move rubro para menor (no atual );
}
no atual = filho menor [no atual ];
Código utilizado no trecho 61.
64.h Estamos em uma folha (no atual ), que é o nó a ser removido. Remove no atual e percorre a árvore “ao
contrário”, consertando o que houver de errado; retorna da rotina 64 i ≡
/∗ O nó é folha, e é raiz da árvore. Vamos deixar a árvore vazia. . . ∗/
if (pai [no atual ] ≡ NIL) {
libera no (no atual );
raiz = maior no = menor no = NIL;
}
else {
if (filho menor [pai [no atual ]] ≡ no atual ) filho menor [pai [no atual ]] = NIL;
else filho maior [pai [no atual ]] = NIL;
h Liga antecessor em H [no atual ] a H[no atual ] e vice-versa 65 i
libera no (no atual );
25
no atual = pai [no atual ];
h Conserta o que foi bagunçado 45 i
}
return;
Código utilizado no trecho 61.
65. h Liga antecessor em H [no atual ] a H[no atual ] e vice-versa 65 i ≡
if (antecessor em H [no atual ] 6= NIL) H[antecessor em H [no atual ]] = H[no atual ];
else
/∗ O ponto removido é o menor na árvore. ∗/
menor no = H[no atual ];
if (H[no atual ] 6= NIL) antecessor em H [H[no atual ]] = antecessor em H [no atual ];
else
/∗ O ponto removido é o maior na árvore. ∗/
maior no = antecessor em H [no atual ];
Código utilizado no trecho 64.
66. Fazemos duas intervenções cirúrgicas, que não usam as primitivas já escritas para manipulação da árvore. A
saber: copiamos o valor do sucessor do ponto atual para ele (como é um nó interno, sabemos que não é o máximo,
donde o seu sucessor não é NIL); e também corrigimos o ponteiro do nó para o seu sucessor (que passa a ser
H[H[no atual ]]). Para o resto contamos com as funções que já escrevemos.
h Estamos em um nó interno (no atual ), que é o nó a ser removido. Coloca o valor do sucessor de no atual em
no atual e atualiza sucessor, remove o mı́nimo do filho maior do no atual ; retorna da rotina 66 i ≡
ponto [no atual ] = ponto [H[no atual ]];
H[no atual ] = H[H[no atual ]];
remove minimo de subarvore (filho maior [no atual ]);
return;
Código utilizado no trecho 61.
67. h Variáveis locais de remove da arvore 67 i ≡
int no atual , proximo no ;
Código utilizado no trecho 60.
26
68.
Inicialização e incremento do fecho
Lá e de volta outra vez. Cá estamos, depois de uma pequena incursão pelos bosques rubro-negros. Se você ainda se
recorda do que estávamos a fazer algumas páginas atrás, inicializar o fecho e colocar mais pontos nele não há de lhe
fazer coçar a cabeça. Se não, talvez seja uma boa ideia bater os olhos no vocabulário que estivemos construindo.
Vamos compor o fecho inicial com pbaixo e palto .
Um pouco estranhamente, se seguimos interpretando as coisas como temos feito a inicialização de H como uma
lista circular fica estranha (porque súbito pbaixo parece ser mı́nimo e máximo entre os vértices do fecho!). Mas
Lembre-se de que pbaixo nunca é inserido na árvore, e então jamais será comparado aos outros pontos. Isso é ao
mesmo tempo uma salvação e um alerta, porque pbaixo , apesar de tudo, pode ser um extremo da sequência de
vértices vista por pnovo . . . Vamos sair desse aparente aperto com testes explı́citos para pbaixo (mais sobre isso em
breve).
h Inicializa fecho e p novo , de modo que pontos < pnovo não precisem mais ser analisados 68 i ≡
inicializa arvore ( );
insere (1);
p novo = 2;
Código utilizado no trecho 19.
69. Vamos agora esmiuçar como fazer o incremento do fecho. Descobrimos se o ponto deve entrar no fecho; buscamos os extremos da aresta decisora; se pnovo deve entrar no fecho, removemos os pontos vistos por pnovo e inserimos
pnovo na árvore. Testamos explicitamente se as arestas (pbaixo , ponto [menor no ])) e (pbaixo , ponto [maior no ])) são
vistas por pnovo .
Dividimos o incremento em três casos. A aresta decisora define em qual deles estamos. Se o pnovo será vizinho
de pbaixo quando for acrescentado ao fecho, então alguma das extremidades da aresta decisora (menor no da aresta
ou maior no da aresta ) será NIL.
h Coloca pnovo no fecho se necessário, removendo pontos que devem sair 69 i ≡
printf ("Será que %d entra no fecho?\n", p novo );
h Encontra a aresta decisora 70 i
printf ("Pontos da aresta decisora: (%d %d)\n", menor no da aresta ≡ N ? 0 : ponto [menor no da aresta ],
maior no da aresta ≡ N ? 0 : ponto [maior no da aresta ]);
if (h Ponto não está à direita estrita da aresta decisora 74 i) {
while (menor no da aresta 6= NIL) {
if (h Aresta que termina em menor no da aresta é vista por pnovo 71 i) {
printf ("A aresta que termina em %d é vista por %d.\n", menor no da aresta , p novo );
no aux = antecessor em H [menor no da aresta ];
printf ("opa<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< # ## # . #
# ###\n");
remove da arvore (ponto [menor no da aresta ]);
menor no da aresta = no aux ;
}
else break;
}
if (menor no da aresta ≡ NIL ∧ h Aresta que começa em pbaixo é vista por pnovo 72 i)
remove da arvore (ponto [menor no da aresta ]);
while (maior no da aresta 6= NIL) {
if (h Aresta que inicia em maior no da aresta é vista por pnovo 73 i) {
no aux = H[maior no da aresta ];
remove da arvore (ponto [maior no da aresta ]);
maior no da aresta = no aux ;
}
else break;
}
if (maior no da aresta ≡ NIL ∧ h Aresta que termina em pbaixo é vista por pnovo 75 i)
remove da arvore (ponto [maior no da aresta ]);
printf ("O ponto %d vai entrar no fecho.\n", p novo );
insere (p novo );
}
else {
printf ("N~ao, n~ao entra.\n");
27
}
Código utilizado no trecho 19.
70. h Encontra a aresta decisora 70 i ≡
no atual = raiz ;
while (verdade ) {
if (menor (p novo , ponto [no atual ])) {
/∗ pnovo ≺ ponto [no atual ]. ∗/
if (filho menor [no atual ] 6= NIL) no atual = filho menor [no atual ];
else {
menor no da aresta = antecessor em H [no atual ];
maior no da aresta = no atual ;
break;
}
}
else {
/∗ pnovo ponto [no atual ]. ∗/
if (filho maior [no atual ] 6= NIL) no atual = filho maior [no atual ];
else {
menor no da aresta = no atual ;
maior no da aresta = H[no atual ];
break;
}
}
}
Código utilizado no trecho 69.
71. Sabemos que se pnovo é colinear à aresta que termina em menor no da aresta , ele não pertence ao segmento
da aresta. Isso acontece pelo modo como a ordenação foi definida. Se pnovo está em alguma aresta qr do polı́gono
(q ≺ r) então ponto [menor no da aresta ] q e também r ponto [maior no da aresta ]. Sendo assim, a “aresta que
termina em menor no da aresta ” só é vista por pnovo se o ponto estiver à sua esquerda estrita.
A dita aresta inicia no ponto [antecessor em H [menor no da aresta ]], geralmente. Isso não vale só quando o
menor nó da aresta é o menor nó na árvore. Nesse caso, usamos esquerda estrita ( . . . ) (não a versão geral) para
usar o ponto zero (pbaixo ) como referência. Vamos usar uma estratégia análoga para o teste da aresta que inicia em
maior no da aresta .
h Aresta que termina em menor no da aresta é vista por pnovo 71 i ≡
((antecessor em H [menor no da aresta ] 6= NIL ∧
esquerda estrita geral (ponto [antecessor em H [menor no da aresta ]], p novo ,
ponto [menor no da aresta ])) ∨ (antecessor em H [menor no da aresta ] ≡ NIL ∧ esquerda estrita (p novo ,
ponto [menor no da aresta ])))
Código utilizado no trecho 69.
72.
Esta é uma parte da condição do item acima.
h Aresta que começa em pbaixo é vista por pnovo 72 i ≡
(esquerda estrita (p novo , ponto [menor no da aresta ]))
Código utilizado no trecho 69.
73. Aqui testamos a direita estrita caso pbaixo esteja envolvido — e por isso alteramos a ordem dos parâmetros
da chamada.
h Aresta que inicia em maior no da aresta é vista por pnovo 73 i ≡
((H[maior no da aresta ] 6= NIL ∧ esquerda estrita geral (ponto [maior no da aresta ], p novo ,
ponto [H[maior no da aresta ]])) ∨ (H[maior no da aresta ] ≡ NIL ∧ direita estrita (p novo ,
ponto [maior no da aresta ])))
Código utilizado no trecho 69.
28
74.
Atente que alguma das extremidades da aresta decisora pode ser NIL.
h Ponto não está à direita estrita da aresta decisora 74 i ≡
(¬direita estrita geral (ponto [menor no da aresta ] 6= NIL ? ponto [menor no da aresta ] : 0
, p novo , ponto [maior no da aresta ] 6= NIL ? ponto [maior no da aresta ] : 0))
Código utilizado no trecho 69.
75. h Aresta que termina em pbaixo é vista por pnovo 75 i ≡
(direita estrita (p novo , ponto [maior no da aresta ]))
Código utilizado no trecho 69.
76. h Variáveis locais de main 12 i +≡
int menor no da aresta , maior no da aresta ;
int no atual , no aux ;
29
77.
Algumas coisas que vou deixar aqui por enquanto
Talvez para lembrar no que é que eu estava pensando quando escrevi colineares. . .
h pnovo está no segmento (0, H[0]) 77 i ≡
(colineares (p novo , H[0]) ∧ (h x-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 78 i
∨ (h x-coordenadas são iguais, e as y-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 79 i)))
78. h x-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 78 i ≡
((X[0] + eps < X[p novo ] ∧ X[p novo ] + eps < X[H[0]]) ∨ (X[0] > X[p novo ] + eps ∧ X[p novo ] > X[H[0]] + eps ))
Código utilizado no trecho 77.
79. h x-coordenadas são iguais, e as y-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 79 i ≡
((fabs (X[0] − X[H[0]]) < eps ) ∧ (fabs (X[0] − X[p novo ]) < eps )
∧ h y-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 80 i)
Código utilizado no trecho 77.
80. h y-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 80 i ≡
((Y [0] + eps < Y [p novo ] ∧ Y [p novo ] + eps < Y [H[0]]) ∨ (Y [0] > Y [p novo ] + eps ∧ Y [p novo ] > Y [H[0]] + eps ))
Código utilizado no trecho 79.
30
81.
Gerando a saı́da
A saı́da do programa não tem segredos. Imprimimos o número da região, e à medida que imprimimos os pontos
vamos calculando o perı́metro, que é, por fim, impesso também.
Abaixo, no aux e no aux 2 apontam para nós da árvore, mas nos referimos a eles (com alguma licença poética)
como pontos também, como em “distância entre no aux e no aux 2 ”.
#define distancia (p1 , p2 )
/∗ Distância entre pontos. ∗/
(sqrt ((X[p2 ] − X[p1 ]) ∗ (X[p2 ] − X[p1 ]) + (Y [p2 ] − Y [p1 ]) ∗ (Y [p2 ] − Y [p1 ])))
h Imprime a resposta para a região 81 i ≡
if (numero regiao > 1) printf ("\nRegion #%d:\n", numero regiao );
else printf ("Region #%d:\n", numero regiao );
printf ("(%.1f,%.1f)", X[0], Y [0]);
perimetro = 0;
no aux = 0;
no aux 2 = menor no ;
if (no aux 2 ≡ NIL) goto depois do while ;
/∗ Árvore vazia. ∗/
while (verdade ) {
h Imprime no aux 2 82 i
perimetro += distancia (ponto [no aux 2 ], ponto [no aux ]);
h Avança no aux . Sai do laço se no aux ≡ NIL, imprimindo o ponto 0 e incrementando o perı́metro com a
aresta que fecha o polı́gono 84 i
h Imprime no aux 83 i
perimetro += distancia (ponto [no aux 2 ], ponto [no aux ]);
h Avança no aux 2 . Sai do laço se no aux 2 ≡ NIL, imprimindo o ponto 0 e incrementando o perı́metro com a
aresta que fecha o polı́gono 85 i
}
depois do while :
printf ("\n%.2f\n", perimetro );
/∗ Perı́metro da região. ∗/
Código utilizado no trecho 7.
82. h Imprime no aux 2 82 i ≡
printf ("-(%.1f,%.1f)", X[ponto [no aux 2 ]], Y [ponto [no aux 2 ]]);
Código utilizado no trecho 81.
83. h Imprime no aux 83 i ≡
printf ("-(%.1f,%.1f)", X[ponto [no aux ]], Y [ponto [no aux ]]);
Código utilizado no trecho 81.
h Avança no aux . Sai do laço se no aux ≡ NIL, imprimindo o ponto 0 e incrementando o perı́metro com a
aresta que fecha o polı́gono 84 i ≡
/∗ Avança no aux . ∗/
no aux = H[no aux 2 ];
if (no aux ≡ NIL) {
printf ("-(%.1f,%.1f)", X[0], Y [0]);
perimetro += distancia (0, ponto [no aux 2 ]);
break;
}
84.
Código utilizado no trecho 81.
h Avança no aux 2 . Sai do laço se no aux 2 ≡ NIL, imprimindo o ponto 0 e incrementando o perı́metro com
a aresta que fecha o polı́gono 85 i ≡
no aux 2 = H[no aux ];
if (no aux 2 ≡ NIL) {
printf ("-(%.1f,%.1f)", X[0], Y [0]);
perimetro += distancia (0, ponto [no aux ]);
break;
}
85.
Código utilizado no trecho 81.
31
86. h Variáveis locais de main 12 i +≡
int no aux 2 ;
double perimetro ;
int i;
87.#define AB printf ("[");
imprime rac (raiz );
printf (" -> ");
#define BA imprime rac (raiz );
printf ("]\n");
#define C printf ("|%d", no atual );
#define c(x) (eh rubro ((x)) ? "R" : "N")
#define FIX printf ("{%d,%s%s%s}", no atual , c(no atual ), c(filho menor [no atual ]), c(filho maior [no atual ]));
h Funções 33 i +≡
void imprime rec (int no )
{
if (no ≡ NIL) printf (".");
else {
printf ("(");
if (eh rubro (no )) printf ("R");
else printf ("N");
imprime rec (filho menor [no ]);
imprime rec (filho maior [no ]);
printf (")");
}
}
void imprime rac (int no )
{
if (no ≡ NIL) printf (" %d ", no );
else {
printf ("(");
printf ("%d ", no );
imprime rec (filho menor [no ]);
imprime rec (filho maior [no ]);
printf (")");
}
}
void lis ( )
{
int i, livre , max livre = NIL;
printf ("A Árvore\n");
max livre = proxima posicao livre ;
printf ("proxima_posicao_livre: %d, pai[ppl]=%d\n", proxima posicao livre , pai [proxima posicao livre ]);
while (pai [max livre ] 6= NIL) max livre = pai [max livre ];
i = 0;
printf ("%7s", "i");
while (i < max livre ) {
h Incrementa o i enquanto é uma posição vazia 88 i
printf ("%3d", i);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "ponto");
while (i < max livre ) {
h Incrementa o i enquanto é uma posição vazia 88 i
printf ("%3d", ponto [i]);
32
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "menor");
while (i < max livre ) {
h Incrementa o i enquanto é uma posição vazia 88 i
printf ("%3d", filho menor [i]);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "maior");
while (i < max livre ) {
h Incrementa o i enquanto é uma posição vazia 88 i
printf ("%3d", filho maior [i]);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "pai");
while (i < max livre ) {
h Incrementa o i enquanto é uma posição vazia 88 i
printf ("%3d", pai [i]);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "cor");
while (i < max livre ) {
h Incrementa o i enquanto é uma posição vazia 88 i
printf ("%3s", eh rubro (i) ? "R" : "N");
++ i;
}
printf ("\n");
printf ("raiz: %d, menor nó: %d (%.1f,%.1f), maior nó: %d (%.1f,%.1f)\n", raiz , menor no ,
X[ponto [menor no ]], Y [ponto [menor no ]], maior no , X[ponto [maior no ]], Y [ponto [maior no ]]);
}
88. h Incrementa o i enquanto é uma posição vazia 88 i ≡
livre = proxima posicao livre ;
while (pai [livre ] 6= NIL) {
if (i ≡ livre ) {
++ i;
livre = proxima posicao livre ;
continue;
}
livre = pai [livre ];
}
Código utilizado no trecho 87.
89. h Funções 33 i +≡
void las ( )
{
int i, livre , max livre = 10;
33
printf ("A Árvore (las)\n");
printf ("proxima_posicao_livre: %d, pai[ppl]=%d\n", proxima posicao livre , pai [proxima posicao livre ]);
i = 0;
printf ("%7s", "i");
while (i < max livre ) {
printf ("%3d", i);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "ponto");
while (i < max livre ) {
printf ("%3d", ponto [i]);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "menor");
while (i < max livre ) {
printf ("%3d", filho menor [i]);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "maior");
while (i < max livre ) {
printf ("%3d", filho maior [i]);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "pai");
while (i < max livre ) {
printf ("%3d", pai [i]);
++ i;
}
printf ("\n");
i = 0;
printf ("%7s", "cor");
while (i < max livre ) {
printf ("%3d", cor [i]);
++ i;
}
printf ("\n");
printf ("raiz: %d, menor nó: %d (%.1f,%.1f), maior nó: %d (%.1f,%.1f)\n", raiz , menor no ,
X[ponto [menor no ]], Y [ponto [menor no ]], maior no , X[ponto [maior no ]], Y [ponto [maior no ]]);
}
90. h Pré-declaração de funções 34 i +≡
void imprime rec (int no );
void imprime rac (int no );
void lis ( );
void las ( );
void double libera ( );
91. h Funções 33 i +≡
void double libera (int no )
/∗ imprime mensagem de erro e aborta se dupla liberação. ∗/
34
{
int livre ;
livre = proxima posicao livre ;
while (pai [livre ] 6= NIL) {
if (no ≡ livre ) {
fprintf (stderr , "EI EI EI EI! Tentaram liberar um nó (4) que já estava livre! T^o fora.\n");
lis ( );
exit (1);
}
livre = pai [livre ];
}
}
35
Índice Remissivo
math : 22.
max livre : 87, 89.
memcpy : 31, 32.
menor : 21, 40, 62, 70.
menor no : 29, 31, 41, 43, 54, 58, 64, 65, 69,
81, 87, 89.
menor no da aresta : 69, 70, 71, 72, 74, 76.
move rubro para maior : 51, 53, 60, 61.
move rubro para menor : 51, 57, 61, 63.
N : 6.
negro : 28, 29, 35, 43, 45.
NIL: 28, 29, 30, 31, 33, 35, 38, 39, 41, 42, 43, 44,
45, 47, 52, 53, 54, 56, 57, 58, 60, 61, 64, 65, 66,
69, 70, 71, 73, 74, 81, 84, 85, 87, 88, 91.
no : 21, 33, 51, 52, 53, 56, 57, 87, 90, 91.
no atual : 38, 39, 40, 41, 42, 44, 45, 46, 50, 52,
53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64,
65, 66, 67, 70, 76, 87.
no aux : 69, 76, 81, 83, 84, 85.
no aux 2 : 81, 82, 84, 85, 86.
no livre : 31, 33, 34, 39, 43.
numero regiao : 6, 7, 81.
outra cor : 49.
p: 47, 48.
p alto : 10, 11, 16, 17, 24.
p baixo : 10, 11, 16, 17, 23.
p novo : 11, 12, 19, 23, 24, 38, 39, 40, 43, 44, 68, 69,
70, 71, 72, 73, 74, 75, 77, 78, 79, 80.
p sai : 60, 61, 62.
pai : 29, 31, 33, 37, 43, 44, 45, 47, 53, 57, 64,
87, 88, 89, 91.
pai estatico : 29, 31.
perimetro : 81, 84, 85, 86.
ponto : 21, 29, 30, 31, 39, 40, 43, 44, 45, 61, 62, 66,
69, 70, 71, 72, 73, 74, 75, 81, 82, 83, 84, 85, 87, 89.
ponto estatico : 29, 31.
printf : 7, 9, 39, 45, 61, 69, 81, 82, 83, 84, 85, 87, 89.
produto interno : 21.
produto interno geral : 21.
proxima posicao livre : 31, 33, 87, 88, 89, 91.
proximo no : 39, 41, 42, 44, 45, 46, 53, 54, 55,
57, 58, 59, 67.
pto : 21.
p1 : 21, 81.
p2 : 21, 81.
q: 47.
raiz : 28, 31, 38, 43, 45, 60, 64, 70, 87, 89.
realloc : 31.
ref : 21.
remove da arvore : 60, 69.
remove maximo de subarvore : 52.
remove minimo de subarvore : 56, 60, 66.
resposta : 33.
rotaciona maior : 45, 47, 48, 51, 53, 61.
rotaciona menor : 45, 47, 48, 51.
rubro : 28, 29, 35, 44, 47, 50.
rubros : 35.
scanf : 7, 9, 10, 11.
AB: 87.
antecessor : 9, 13, 21, 30.
antecessor em H : 9, 13, 29, 30, 31, 41, 42, 43,
54, 65, 69, 70, 71.
antecessor em H estatico : 29, 31.
argc : 7.
argv : 7.
aumenta tamanho arvore : 31, 33.
BA: 87.
BLOBDIGNAG: 45.
C: 87.
c: 87.
colineares : 21, 77.
colineares geral : 21.
cor : 28, 29, 31, 43, 44, 45, 47, 49, 89.
cor estatico : 29, 31.
depois do while : 81.
direita estrita : 21, 73, 75.
direita estrita geral : 21, 74.
distancia : 81, 84, 85.
double libera : 33, 90, 91.
eh negro : 28, 53, 57, 61, 63.
eh rubro : 28, 45, 51, 53, 61, 87.
eps : 21, 23, 24, 25, 78, 79, 80.
esquerda estrita : 21, 71, 72.
esquerda estrita geral : 21, 71, 73.
exit : 91.
fabs : 21, 22, 23, 24, 25, 79.
fflush : 7.
filho maior : 29, 31, 39, 43, 44, 45, 47, 49, 50, 51,
52, 53, 54, 60, 61, 64, 66, 70, 87, 89.
filho maior estatico : 29, 31.
filho menor : 29, 31, 35, 39, 43, 44, 45, 47, 49, 51,
52, 53, 57, 58, 61, 63, 64, 70, 87, 89.
filho menor estatico : 29, 31.
filhos menores : 52.
FIX: 87.
fprintf : 91.
free : 14, 31.
geral : 21.
getchar : 45.
H: 29.
H estatico : 29, 31.
i: 86, 87, 89.
imprime rac : 87, 90.
imprime rec : 87, 90.
inicializa arvore : 31, 68.
insere : 38, 68, 69.
las : 89, 90.
libera arvore : 18, 31.
libera no : 33, 54, 58, 64.
libera pontos : 13, 14, 18.
lis : 19, 45, 87, 90, 91.
livre : 87, 88, 89, 91.
main : 7.
maior no : 29, 31, 42, 43, 54, 58, 64, 65, 69, 87, 89.
maior no da aresta : 69, 70, 71, 73, 74, 75, 76.
malloc : 13, 31.
36
sentidos opostos : 21.
sqrt : 81.
stderr : 91.
stdin : 7.
sucessor : 9, 19, 21, 30.
tamanho arvore : 31, 33.
tamanho inicial arvore : 29, 31.
tamanho inicial fecho : 13, 29.
tamanho inicial pontos : 13, 14, 15.
tamanho pontos : 13, 14, 15.
troca cores : 45, 49, 51.
verdade : 38, 52, 56, 60, 70, 81.
X: 15.
x aux : 16, 17.
X estatico : 14, 15.
Y : 15.
y aux : 16, 17.
Y estatico : 14, 15.
37
Lista de trechos
h pnovo ≺ ponto [no atual ] 40 i Utilizado no trecho 39.
h psai ≺ ponto [no atual ] 62 i Utilizado no trecho 61.
h x-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 78 i Utilizado no trecho 77.
h x-coordenadas são iguais, e as y-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 79 i Utilizado no
trecho 77.
h y-coordenadas estão na projeção no eixo x do segmento (0,H[0]) 80 i Utilizado no trecho 79.
h Aloca espaço para X e Y ; pára o programa em caso de erro 13 i Utilizado no trecho 9.
h Altera apontadores de antecessor e sucessor para inclusão do filho maior 42 i Utilizado no trecho 39.
h Altera apontadores de antecessor e sucessor para inclusão do filho menor 41 i Utilizado no trecho 39.
h Aresta que começa em pbaixo é vista por pnovo 72 i Utilizado no trecho 69.
h Aresta que inicia em maior no da aresta é vista por pnovo 73 i Utilizado no trecho 69.
h Aresta que termina em pbaixo é vista por pnovo 75 i Utilizado no trecho 69.
h Aresta que termina em menor no da aresta é vista por pnovo 71 i Utilizado no trecho 69.
h Arquivos de cabeçalho 8, 22, 32 i Utilizado no trecho 5.
h Avança no aux 2 . Sai do laço se no aux 2 ≡ NIL, imprimindo o ponto 0 e incrementando o perı́metro com a
aresta que fecha o polı́gono 85 i Utilizado no trecho 81.
h Avança no aux . Sai do laço se no aux ≡ NIL, imprimindo o ponto 0 e incrementando o perı́metro com a aresta
que fecha o polı́gono 84 i Utilizado no trecho 81.
h Caminha pela árvore buscando psai , e removendo-o se encontrado. Conserta a árvore e retorna. 61 i Utilizado no
trecho 60.
h Coloca pnovo no fecho se necessário, removendo pontos que devem sair 69 i Utilizado no trecho 19.
h Conserta o que foi bagunçado 45 i Citado no trecho 37. Utilizado nos trechos 38, 52, 56 e 64.
h Constantes e variáveis globais 6, 15, 28, 29, 31 i Utilizado no trecho 5.
h Encontra a aresta decisora 70 i Utilizado no trecho 69.
h Encontra o fecho convexo da região 19 i Utilizado no trecho 9.
h Estamos em um nó interno (no atual ), que é o nó a ser removido. Coloca o valor do sucessor de no atual em
no atual e atualiza sucessor, remove o mı́nimo do filho maior do no atual ; retorna da rotina 66 i Utilizado no
trecho 61.
h Estamos em uma folha (no atual ), que é o nó a ser removido. Remove no atual e percorre a árvore “ao contrário”,
consertando o que houver de errado; retorna da rotina 64 i Utilizado no trecho 61.
h Funções 33, 38, 47, 51, 52, 56, 60, 87, 89, 91 i Utilizado no trecho 5.
h Imprime a resposta para a região 81 i Utilizado no trecho 7.
h Imprime no aux 2 82 i Utilizado no trecho 81.
h Imprime no aux 83 i Utilizado no trecho 81.
h Incrementa o i enquanto é uma posição vazia 88 i Utilizado no trecho 87.
h Inicializa fecho e p novo , de modo que pontos < pnovo não precisem mais ser analisados 68 i Utilizado no trecho 19.
h Insere pnovo na árvore vazia 43 i Utilizado no trecho 38.
h Insere pnovo na folha 44 i Utilizado no trecho 38.
h Lê o segundo ponto e inicializa ı́ndices pbaixo e palto 10 i Utilizado no trecho 9.
h Lê os demais pontos, mantendo pbaixo e palto apontando para os pontos certos 11 i Utilizado no trecho 9.
h Leitura e processamento do registro da região 9 i Utilizado no trecho 7.
h Libera memória alocada 18 i Utilizado no trecho 7.
h Liga antecessor em H [no atual ] a H[no atual ] e vice-versa 65 i Utilizado no trecho 64.
h O ponto 0 tem y-coordenada menor do que a do ponto 1, ou ambos têm mesma y-coordenada mas 0 tem
x-coordenada menor 25 i Utilizado no trecho 10.
h Ponto pnovo deve entrar no lugar de palto 24 i Utilizado no trecho 11.
h Ponto pnovo deve entrar no lugar de pbaixo 23 i Utilizado no trecho 11.
h Ponto não está à direita estrita da aresta decisora 74 i Utilizado no trecho 69.
h Pré-declaração de funções 34, 48, 90 i Utilizado no trecho 5.
h Remove o máximo (proximo no ) 54 i Citado no trecho 58. Utilizado no trecho 52.
h Remove o mı́nimo (proximo no ) 58 i Utilizado no trecho 56.
h Rotina principal 7 i Utilizado no trecho 5.
h Segue a busca pelo máximo, garantindo nunca estar em um 2-nó. Sai do loop garantindo proximo no ≡
filho maior [no atual ] é o máximo 53 i Utilizado no trecho 52.
h Segue a busca pelo mı́nimo, garantindo nunca estar em um 2-nó. Sai do loop garantindo proximo no ≡
filho menor [no atual ] é o mı́nimo 57 i Utilizado no trecho 56.
38
h Segue a busca, avançando no atual . Prepara a inserção em uma folha de no atual e escapa do loop 39 i Utilizado
no trecho 38.
h Troca pbaixo e 0 de posição e também palto e 1 em X[ ] e Y [ ] 16 i Utilizado no trecho 9.
h Variáveis locais de insere 46 i Utilizado no trecho 38.
h Variáveis locais de main 12, 17, 76, 86 i Utilizado no trecho 7.
h Variáveis locais de remove da arvore 67 i Utilizado no trecho 60.
h Variáveis locais de remove maximo de subarvore 55 i Utilizado no trecho 52.
h Variáveis locais de remove minimo de subarvore 59 i Utilizado no trecho 56.
h pnovo está no segmento (0, H[0]) 77 i
h “Empurra” um link rubro para o filho menor se necessário, e prossegue para esse filho. 63 i Utilizado no trecho 61.
39