Olá!
Não entendi o "algoritmo para consulta".
Alguem poderia explicar por favor?
Valeu!
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.
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.
Alvaro, valeu!!!
Só não entendi o que você quer dizer com p(v) ou p(v_div).
Só não entendi o que você quer dizer com p(v) ou p(v_div).
Olá Douglas,
p(v) é a chave de um nó v.
p(v) é a chave de um nó v.
Alvaro, como ficaria a árvore binária balanceada para 6 coordenadas, por exemplo?
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).
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).
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?
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?
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.
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.
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.
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.
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
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
HAUhAUhaUhaUha...
Suspeitei desde o princípio.
Então, qual a diferença entre uma árvore balanceada e uma AVL?
Vlw!
Suspeitei desde o princípio.
Então, qual a diferença entre uma árvore balanceada e uma AVL?
Vlw!
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
abraços,
--
carlinhos
Ahnnn.... ok!
Thx!
Thx!
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?
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.
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.
Eh, a arvore principal eh só O
mesmo, não tinha percebido, vlw
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
Olá,
Não se preocupe com os dados de entrada. Eles estarão corretos.
Não se preocupe com os dados de entrada. Eles estarão corretos.
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?
"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?
Olá,
Você deve usar o que achar melhor.
Você deve usar o que achar melhor.
O resultado de um percurso in-ordem em uma árvore de busca binária é sempre os dados ordenados, né?
Exatamente, Francisco.
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!
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).
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).
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 <).
O arquivo pode ser redirecionado. Mas lembre de seguir exatamente o formato da entrada.
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
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
Nao sei. Pergunte ao professor Carlinhos.
Não precisa implementar nenhum algoritmo de ordenação. Pode usar o QSORT da biblioteca
--
carlinhos
--
carlinhos
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)?
x(w1 ) ≤ p(vdiv ) < x(w2 )
Mas existe algum problema em p(vdiv) ser igual a x(w2)?
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).
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).
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.
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
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
Será que vocês podiam disponibilizar alguns arquivos de entrada e suas saídas correspondentes para testes?
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 ^^.
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).
No enunciado do ep, o ponto na janela 3 é (100, 50).
A ordem dos pontos na saída é importante?
Falha nossa! Não falamos sobre uma ordem para os pontos na saída. Mas seria ótimo se vocês ordenassem os pontos usando o símbolo <_x (menor x).
Ordenar os pontos é obrigatório?
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
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
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.
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.
Apanhando a 3 dias de uma lista ligada boba = /