EP2

EP2

por Douglas Alves dos Reis -
Número de respostas: 41
Olá!

Não entendi o "algoritmo para consulta".
Alguem poderia explicar por favor?

Valeu!
Em resposta à Douglas Alves dos Reis

Re: EP2

por Alvaro Junio Pereira Franco -
Primeiro encontre v_div. Nesse nó w1 (o menor ponto de uma janela W) deve ser menor ou igual a p(v_div) e w2 (o maior ponto de uma janela W) deve ser maior que p(v_div). Em um nó v na subárvore à esquerda de v_div:

Caso 1e: se x(w1) < = p(v) então continuamos a busca à esquerda e os pontos armazenados na subárvore à direita de v possuem x-coordenada entre x(w1) e x(w2). Portanto, devemos listar, dentre tais pontos, aqueles que possuem y-coordenada entre y(w1) e y(w2) (isso deve ser feito na árvore associada ao nó à direita de v da mesma forma).

Caso 2e: se x(w1) > p(v) então os pontos armazenados na subárvore à esquerda não podem estar em W e continuamos a busca à direita.

Em um nó v na subárvore à direita de v_div:

Caso 1d: se x(w2) > p(v) então continuamos a busca à direita e os pontos armazenados na subárvore à esquerda de v possuem x-coordenada entre x(w1) e x(w2). Portanto, devemos listar, ... (simétrico ao caso 1e acima).

Caso 2d: se x(w2) < = p(v) então ... (simétrico ao caso 2e acima).

Em p(v) você deve armazenar alguma informação capaz de realizar tais comparações. Tome cuidado com os pontos que possuem x-coordenadas ou y-coordaenadas iguais.
Em resposta à Alvaro Junio Pereira Franco

Re: EP2

por Douglas Alves dos Reis -
Alvaro, valeu!!!

Só não entendi o que você quer dizer com p(v) ou p(v_div).


Em resposta à Douglas Alves dos Reis

Re: EP2

por Alvaro Junio Pereira Franco -
Olá Douglas,

p(v) é a chave de um nó v.
Em resposta à Alvaro Junio Pereira Franco

Re: EP2

por Douglas Alves dos Reis -

Alvaro, como ficaria a árvore binária balanceada para 6 coordenadas, por exemplo?

Em resposta à Douglas Alves dos Reis

Re: EP2

por Alvaro Junio Pereira Franco -
Olá,

Com 6 pontos, uma árvore como descrita no enunciado do ep ficaria balanceada, com 6 folhas e 5 nós internos. Simule as inserções de cada ponto considerando uma AVL (que também deve ficar com 6 folhas e 5 nós internos).
Em resposta à Douglas Alves dos Reis

Re: EP2

por André Casimiro -
Olá,

Tenho uma dúvida com relação às árvores de segundo nível (y-coordenada).
Se para cada nó v, existe uma representação para P(v) em x-coordenada e em y-coordenada não estamos gastando memória proporcional a O(n²), onde n é o número total de nós.

Isso é um problema?


Ah, outra coisa... há necessidade da árvore ser AVL?
Em resposta à André Casimiro

Re: EP2

por Alvaro Junio Pereira Franco -
Olá André,

O consumo de espaço da árvore descrita no enunciado do ep é O(n log n), onde n é o número de pontos no plano. Assumindo n como sendo o número total de nós da árvore principal (a árvore do primeiro nível) o consumo de espaço continua O(n log n).

Esperamos uma implementação de uma árvore de busca binária e balanceada. A implementação de uma AVL seria muito legal. Mas se preferir pode implementar outra árvore desde que você garanta que ela seja balanceada.
Em resposta à Alvaro Junio Pereira Franco

Re: EP2

por André Casimiro -
Uma Árvore Balanceada é uma árvore que tem altura O( lg n ). Aleatoriamente?

Na minha implementação, se os dados são aleatórios ela fica balanceada mas se vêm ordenados a altura fica O( n ). Garantir que sua altura é sempre O( lg n ) seria algo semelhante a uma AVL? Posso supor dados aleatórios?


Obrigado. mostrando a língua
Em resposta à André Casimiro

Re: EP2

por Carlos E. Ferreira -
he he he...

Não. Os dados serão fornecidos por um monitor malvado, que certamente descobrirá um jeito de sua árvore ficar muito ruim. E aí sua nota cairá de forma inversamente proporcional com a altura da sua árvore.

:P

--
carlinhos
Em resposta à Carlos E. Ferreira

Re: EP2

por André Casimiro -
HAUhAUhaUhaUha...
Suspeitei desde o princípio.

Então, qual a diferença entre uma árvore balanceada e uma AVL?


Vlw!
Em resposta à André Casimiro

Re: EP2

por Carlos E. Ferreira -
Prá vocês até o momento nenhuma. A única árvore balanceada que vocês conhecem é a AVL. Mas, há outras como rubro-negras, árvores 2-3, B-árvores, etc. Uma árvore é balanceada se sua altura é O(log n), onde n é o número de elementos na estrutura.

abraços,

--
carlinhos
Em resposta à André Casimiro

Re: EP2

por Thiago Costa -
A arvore principal gasta espaço O(n log n). Mas no segundo nível, se cada uma dessas sub-arvores for diferente, o espaço vai aumentar para O(n log² n). Isso está certo ou é esperado um jeito de juntar essas árvores de segundo nível?
Em resposta à Thiago Costa

Re: EP2

por Alvaro Junio Pereira Franco -
Olá Thiago,

A árvore no total (considerando a árvore principal (T) e todas as árvores de segundo nível) consome espaço O(n log n). Para ver que isso é verdade note o seguinte. Primeiro, o número de nós da árvore principal é O(n) e sua altura é O(log n). Segundo, sejam v1, v2, ..., vk os nós de um nível em T. Cada vi, i = 1, ..., k aponta para uma árvore de segundo nível (Ty(vi)). Note que as subárvores com raiz em v1, v2, ..., vk particionam o conjunto de pontos. Com isso, as árvores Ty(vi) consome espaço O(n) no total. Como temos O(log n) níveis temos que o consumo de espaço total é O(n log n).

Não esperamos um jeito de juntar as árvores de segundo nível. Realmente queremos uma árvore de segundo nível para cada nó da árvore principal.
Em resposta à Douglas Alves dos Reis

Re: EP2

por Nicoli G -

Sobre o arquivo de entrada.

Em relação as coordenadas passadas posso assumir que o usuário sabe contar... ou seja, se na primeira linha ele informa 3 ele obrigatoriamente deve colocar 3 pontos ou devo trabalhar possíveis erros também.

Como:

3
10 15
2   1
1
2   3

Em resposta à Douglas Alves dos Reis

Re: EP2

por Everton Topan da Silva -
Eu não entendi muito bem, na parte da estrutura de dados, a informação dos nós internos, pq la diz:
"Os pontos de P são armazenados nas suas folhas e os nós internos direcionam uma busca no eixo x".

Como eu só terei os pontos nas folhas oq será guardado nos nós internos? seria um valor, no caso de uma arvore AVL, entre o valor da esquerda e o da direita?

Em resposta à Douglas Alves dos Reis

Re: EP2

por Francisco Zigmund Sokol -
O resultado de um percurso in-ordem em uma árvore de busca binária é sempre os dados ordenados, né?
Em resposta à Francisco Zigmund Sokol

Re: EP2

por Thiago Henrique Coraini -
Em resposta à Thiago Henrique Coraini

Re: EP2

por Fernando Akira Fujihara -

Olá pessoal!

Não entendi o arquivo de entrada ...

As últimas linhas são as coordenadas da janela a serem consultadas. Correto?

Uma janela não é definida pelos pontos w1 e w2? Pq tem 4 valores em cada linha?

Obrigado!

Em resposta à Fernando Akira Fujihara

Re: EP2

por Alvaro Junio Pereira Franco -
Olá Fernando,

w1 e w2 são pontos no plano. Logo, w1 e w2 possuem dois valores cada (um no eixo x e outro no y). Por exemplo, para a janela com os valores 10, 3, 20, 40, teremos w1=(10, 3) e w2=(20,40).
Em resposta à Alvaro Junio Pereira Franco

Re: EP2

por Geraldo Castro Zampoli -
Eu não entendi se deve se ler os dados do arquivo (com fsanf e afins), ou o arquivo pode ser redirecionado da linha de comado (com <).
Em resposta à Geraldo Castro Zampoli

Re: EP2

por Alvaro Junio Pereira Franco -
O arquivo pode ser redirecionado. Mas lembre de seguir exatamente o formato da entrada.
Em resposta à Alvaro Junio Pereira Franco

Re: EP2

por Geraldo Castro Zampoli -
Valeww,
mais uma duvida, usarei arvore limite para tal terei que ordenar o vetor na ordenação posso usar o qsort da libc ou devo implementar um sort

abss
Em resposta à Douglas Alves dos Reis

Re: EP2

por Francisco Zigmund Sokol -
No enunciado, o ancestral comum mais baixo está definido como:
x(w1 ) ≤ p(vdiv ) < x(w2 )

Mas existe algum problema em p(vdiv) ser igual a x(w2)?
Em resposta à Francisco Zigmund Sokol

Re: EP2

por Alvaro Junio Pereira Franco -
Ola Francisco.
Aqui estou considerando o uso de uma arvore limite construida como visto em sala de aula. Dependendo da implementacao, isso pode mudar.
Para que o algoritmo de busca funcione (o algoritmo descrito no enunciado do ep e dado na ultima monitoria), qualquer ponto armazenado em um no' `a esquerda de vdiv deve ser menor que x(w2). Se p(vdiv) for igual a w2, isso nao e' garantido.

Mais uma coisa, vdiv e' o ancestral comum mais perto da raiz (eu chamo isso de mais alto).


Em resposta à Alvaro Junio Pereira Franco

Re: EP2

por Francisco Zigmund Sokol -
Pra mim também fazia mais sentido chamar vdiv de ancestral comum mais alto, mas é que no enunciado do ep é chamado de mais baixo, acho que está errado.
Em resposta à Francisco Zigmund Sokol

Re: EP2

por Carlos E. Ferreira -
O ancestral comum mais alto de dois vértices quaisquer de uma árvore não é a raiz?

Bem, depende do que você orienta a árvore. Se a raiz está em cima, então o que estamos procurando é o primeiro ancestral comum a dois vértices, ou seja, se você parte lá de baixo, o primeiro vértice em que os caminhos deles até a raiz se encontram, ou seja, entre os ancestrais comuns, o mais baixo. É isso?

--
carlinhos
Em resposta à Douglas Alves dos Reis

Re: EP2

por Francisco Zigmund Sokol -
Será que vocês podiam disponibilizar alguns arquivos de entrada e suas saídas correspondentes para testes?
Em resposta à Francisco Zigmund Sokol

Re: EP2

por Felipe Simionato Solferini -
Voce mesmo pode gerar os arquivos de teste. É só gerar pontos aletórios e algumas janelas. Dai voce resolve pelo metodo lusitano mesmo. Ele é muito ineficiente e deve rodar muitas vezes mais lento que o EP, mas é excelente para produzir testes ^^.
Em resposta à Francisco Zigmund Sokol

Re: EP2

por Alvaro Junio Pereira Franco -
Aqui estão alguns exemplos de entrada e saída. A sua resposta deve coincidir com as respostas dadas nos arquivos, porém, a ordem em que aparecem os pontos (no arquivo de saída) pode ser diferente.
No enunciado do ep, o ponto na janela 3 é (100, 50).
Em resposta à Douglas Alves dos Reis

Re: EP2

por Alex Morinaga -
A ordem dos pontos na saída é importante?
Em resposta à Douglas Alves dos Reis

Re: EP2

por William Gnann -
Oi,

Seria possível mostrar como ficam algumas subárvores em relação ao exemplo?
(Por algum motivo estranho, quando meu programa mexe com as árvores Y - não notei um padrão mais significativo - dá segmentation fault). No entanto, ele funciona para o exemplo do enunciado...

Testei com esse:
4
0 0
0 1
1 0
1 1
1
0 0 2 2
Em resposta à William Gnann

Re: EP2

por Felipe Simionato Solferini -
Entra no msn q eu te falo Will, seu feio! = P


Precisa mesmo usar a lista ligada pra imprimir ?

O meu ep tá lindo, mas to apanhando faz 2 dias de uma lista ligada bem boba = /

Já consegui fazer um ajuste de algoritmo (aka POG) que imprime na hora q encontra a folha, e isso gera a saida esperada.