[Python-es] Implementación de Árbol de Búsqueda con Prioridad en Python
8 views
Skip to first unread message
Asdrúbal Iván Suárez Rivera
Mar 12, 2012, 10:02:18 AM3/12/12
to La lista de python en castellano
Buenos días amigos, les escribo ya que tengo dudas con una implementación de un árbol de búsqueda con prioridad. En el mismo se debería cumplir la condición de que para todos los puntos y el árbol sea un heap min-max, y para los puntos x debería ser un árbol binario de búsqueda a la hora de realizar el recorrido infijo.
Pues bien, en las pruebas que he hecho no es así. Sinceramente no sé que estoy haciendo mal. Según estaba leyendo en el artículo original donde se dió a conocer esta estructura de datos, durante la construcción del árbol, recursivamente debía calcularse la mediana de los puntos en x. Esto lo hago, y luego divido la lista entre valores menores y mayores que la mediana en X, según el artículo esto debería hacer que el árbol para x pasara a ser un árbol binario de búsqueda. Para y antes de construir el árbol he ordenado la lista decrecientemente según y.
No sé de verdad que estaré haciendo mal.
Si alguien me puede ayudar, estaré bastante agradecido.
El código lo tengo en el siguiente repositorio git. Saludos
--
El éxito de alguien que enseña no es que sepa mucho, sino que lo poco que sabe lo sepa hacer llegar.
Asdrúbal Iván Suárez Rivera
El éxito de alguien que enseña no es que sepa mucho, sino que lo poco que sabe lo sepa hacer llegar.
Òscar Vilaplana
Mar 12, 2012, 10:42:08 AM3/12/12
to La lista de python en castellano
2012/3/12 Asdrúbal Iván Suárez Rivera <asdrubal.ivan...@gmail.com>
Buenos días amigos, les escribo ya que tengo dudas con una implementación de un árbol de búsqueda con prioridad. En el mismo se debería cumplir la condición de que para todos los puntos y el árbol sea un heap min-max, y para los puntos x debería ser un árbol binario de búsqueda a la hora de realizar el recorrido infijo.Pues bien, en las pruebas que he hecho no es así. Sinceramente no sé que estoy haciendo mal. Según estaba leyendo en el artículo original donde se dió a conocer esta estructura de datos, durante la construcción del árbol, recursivamente debía calcularse la mediana de los puntos en x. Esto lo hago, y luego divido la lista entre valores menores y mayores que la mediana en X, según el artículo esto debería hacer que el árbol para x pasara a ser un árbol binario de búsqueda. Para y antes de construir el árbol he ordenado la lista decrecientemente según y.No sé de verdad que estaré haciendo mal.
Prueba a escribir tests:
- de la función que calcula la mediana.
- de la función que añade los nodos al árbol.
- prueba creando un árbol de 1 solo nodo (trivial), luego 2, luego 3... hasta un número suficientemente grande.
Para escribir tests, si usas py.test, puedes mirar http://oscarvilaplana.cat/post/pytest-tricks/ . Te será útil a la hora de generar los tests que añaden nodos al árbol. Si no, unittest también te vale.
Saludos,
Òscar
Chema Cortes
Mar 12, 2012, 9:18:07 PM3/12/12
to La lista de python en castellano
El día 12 de marzo de 2012 15:02, Asdrúbal Iván Suárez Rivera
<asdrubal.ivan...@gmail.com> escribió:
> Buenos días amigos, les escribo ya que tengo dudas con una implementación de
> un árbol de búsqueda con prioridad. En el mismo se debería cumplir la
> condición de que para todos los puntos y el árbol sea un heap min-max, y
> para los puntos x debería ser un árbol binario de búsqueda a la hora de
> realizar el recorrido infijo.
>
> Pues bien, en las pruebas que he hecho no es así. Sinceramente no sé que
> estoy haciendo mal. Según estaba leyendo en el artículo original donde se
> dió a conocer esta estructura de datos, durante la construcción del árbol,
> recursivamente debía calcularse la mediana de los puntos en x. Esto lo hago,
> y luego divido la lista entre valores menores y mayores que la mediana en X,
> según el artículo esto debería hacer que el árbol para x pasara a ser un
> árbol binario de búsqueda. Para y antes de construir el árbol he ordenado la
> lista decrecientemente según y.
>
> No sé de verdad que estaré haciendo mal.
>
> Si alguien me puede ayudar, estaré bastante agradecido.
>
> El código lo tengo en el siguiente repositorio git. Saludos
>
> https://bitbucket.org/asdrubalivan/arbolprioridad/src
<asdrubal.ivan...@gmail.com> escribió:
> Buenos días amigos, les escribo ya que tengo dudas con una implementación de
> un árbol de búsqueda con prioridad. En el mismo se debería cumplir la
> condición de que para todos los puntos y el árbol sea un heap min-max, y
> para los puntos x debería ser un árbol binario de búsqueda a la hora de
> realizar el recorrido infijo.
>
> Pues bien, en las pruebas que he hecho no es así. Sinceramente no sé que
> estoy haciendo mal. Según estaba leyendo en el artículo original donde se
> dió a conocer esta estructura de datos, durante la construcción del árbol,
> recursivamente debía calcularse la mediana de los puntos en x. Esto lo hago,
> y luego divido la lista entre valores menores y mayores que la mediana en X,
> según el artículo esto debería hacer que el árbol para x pasara a ser un
> árbol binario de búsqueda. Para y antes de construir el árbol he ordenado la
> lista decrecientemente según y.
>
> No sé de verdad que estaré haciendo mal.
>
> Si alguien me puede ayudar, estaré bastante agradecido.
>
> El código lo tengo en el siguiente repositorio git. Saludos
>
> https://bitbucket.org/asdrubalivan/arbolprioridad/src
Yo diría que la rama de la derecha se diferencia de la izquierda en
que deberías escoger el mínimo valor de 'y', que al ser una lista
ordenada es equivalente a escoger el último de la lista.
--
Hyperreals *R: http://ch3m4.org/blog
Quarks, bits y otras criaturas infinitesimales
_______________________________________________
Python-es mailing list
Pyth...@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/
Reply all
Reply to author
Forward
0 new messages