¿Hay un módulo para AVL o Rojo-Negro o algún otro tipo de árbol binario balanceado en la biblioteca estándar de Python? Intenté encontrar uno, pero sin éxito (soy relativamente nuevo en Python).Biblioteca estándar de Python: ¿hay algún módulo para árbol binario equilibrado?
No, no hay un árbol binario balanceado en el archivo stdlib. Sin embargo, a partir de sus comentarios, parece que usted puede tener algunas otras opciones:
O(log n). Si la búsqueda es todo lo que necesita y sus datos ya están ordenados, el módulo bisect proporciona un algoritmo de búsqueda binario para las listas.Si ninguna de las soluciones funciona bien para usted, tendrá que ir a un módulo de terceros o implementar uno propio.
¡Muchas gracias! Usar un juego resolvió mi problema. No tenía idea de que tienen O (1) búsquedas en Python (siempre he pensado que todo el conjunto debe atravesarse antes de encontrar el valor correcto, pero como he dicho, soy nuevo en Python). Gracias también por su explicación de las estructuras de datos habituales en Python. – aeter
no hay nada de este tipo en stdlib, as far as I can see, pero quick look at pypi brings up a few alternative:
También hay una implementación rápida como C pero pura de Python llamada [sortedcontainers] (http://www.grantjenks.com/docs/sortedcontainers /) Los documentos tienen una buena [comparación de rendimiento] (http://www.grantjenks.com/docs/sortedcontainers/performance.html) con las alternativas que enumera. – GrantJ
No, pero hay AVL Tree Objects for Python y (muy viejo!) un proyecto (cerrado) en SourceForge - avl-trees for Python.
Ha habido algunos casos en los que he encontrado heapq package (en la biblioteca estándar) para ser útil, especialmente si en un momento dado desea O (1) tiempo de acceso al elemento más pequeño en su colección.
Para mí, estaba haciendo un seguimiento de una colección de temporizadores y generalmente solo estaba interesado en comprobar si el tiempo más pequeño (el que se ejecutará primero) estaba listo todavía.
Hay un nuevo paquete llamado "bintrees" que admite árboles equilibrados, AVL y RB. Puede encontrarlo here.
Instalé el módulo bintrees (2.0.1), pero cuando lo importo, aparece el mensaje: 'Advertencia: FastBinaryTree no está disponible, usando la versión Python BinaryTree. ¿Alguna idea de cómo solucionar esto? Instalé Cython, pero todavía da ese error en la importación. – yaraju
Lo siento, no tengo idea :( –
Creo que en Windows, las versiones de FastXTree necesitan un compilador de C instalado como MSVC o Mingw32. No lo he probado, ya que lo más probable es que implemente un árbol personalizado para mi propósito. – yaraju
Eche un vistazo también al proyecto Sorted Containers.
Aquí hay una charla PyCon al respecto: https://www.youtube.com/watch?v=7z2Ki44Vs4E
sólo tiene que utilizar conjuntos o diccionarios. Si necesito usar una mejor rutina hash, defino '__hash __()'. ¿Necesitas algo más elegante? Si es así, ¿por qué? Por cierto, si no puede encontrarlo en docs.python.org, probablemente no sea un módulo estándar. –
@Mike - Estoy intentando resolver una tarea del Proyecto Euler. Creo que usar un árbol de búsqueda binaria equilibrada en lugar de una lista para uno de mis contenedores de datos aceleraría el algoritmo con una relación logarítmica (debido a las búsquedas O (logn)), lo que resolvería la tarea sin calentar mi computadora. Además, tenía curiosidad por eso. – aeter
¿Qué tal un set para O (1) búsquedas – Mark