resueltos ejercicios dibujar codigo busqueda binarios binario avl arboles arbol python tree standard-library

ejercicios - Biblioteca estándar de Python: ¿hay algún módulo para árbol binario equilibrado?



arboles binarios en python (6)

¿Hay algún módulo para AVL o Red-Black u otro tipo de árbol binario balanceado en la biblioteca estándar de Python? Intenté encontrar uno, pero sin éxito (soy relativamente nuevo en Python).

Hay un nuevo paquete llamado "bintrees" que admite árboles equilibrados, AVL y RB. Puedes encontrarlo here .

Hubo algunos casos en los que he encontrado que el paquete heapq (en la biblioteca estándar) es ú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, por lo general, solo me interesaba comprobar si el tiempo más pequeño (el que debía ejecutarse primero) estaba listo todavía.

No, no hay un árbol binario balanceado en el stdlib. Sin embargo, de sus comentarios, parece que puede tener otras opciones:

  • Usted dice que quiere una BST en lugar de una lista para búsquedas 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.
  • Mike DeSimone recomendó sets y dicts y explicó por qué las listas son demasiado lentas algorítmicamente. Los conjuntos y los dictados se implementan como tablas hash, que tienen una búsqueda O (1). La solución para la mayoría de los problemas en Python es "usar un dict".

Si ninguna de las soluciones funciona bien para usted, tendrá que ir a un módulo de terceros o implementar el suyo propio.