AVL Trees y el mundo REAL

14

en la escuela se nos enseña cómo podemos equilibrar un árbol AVL en una inserción o eliminación.

¿Por qué este tipo de conocimiento realmente será útil en el mundo real? ¿Puede alguien dar un ejemplo sobre cuándo este tipo de conocimiento sería realmente útil?

Por lo que he visto, en el lugar de trabajo tales detalles casi nunca surgen ...

Puedo ver cómo el conocimiento detallado sobre algoritmos y algunas estructuras de datos puede ser importante, pero no detalles como las rotaciones de árbol AVL (y conceptos similares similares).

gracias!

    
pregunta rrazd 02.07.2011 - 20:00
fuente

3 respuestas

13

El estudio de los árboles AVL puede ser útil por los siguientes motivos:

  • Es una gran práctica para razonar sobre datos abstractos. No tienes que pensar en un árbol en particular, debes considerar todas las posibilidades. La práctica con este tipo de razonamiento también puede ayudar con casos más simples.

  • Es una gran práctica para comprender predicados y contratos. Asegurarse de que un árbol esté equilibrado, y las herramientas que utiliza para probar cada operación de equilibrio conservado, pueden, por ejemplo, aplicarse a cuestiones de seguridad y al código paralelo.

  • Le permite escribir sus propias variantes o incluso crear tipos de estructuras de datos completamente nuevos.

  • Es posible que tenga que implementar un árbol AVL para una nueva biblioteca o plataforma.

Puede debatir los méritos particulares de aprender cada tipo de algoritmo de clasificación o cada tipo de árbol equilibrado. Realmente no importa cuáles los que termines aprendiendo, pero debes asegurarte de obtener la cobertura completa de los temas más importantes.

Si desea ver la importancia de los algoritmos de conocimiento en el mundo real, lea " ¡Cómo matar a una gran idea! ", un artículo en Inc sobre la caída de Friendster, y cómo la más mínima aplicación de principios fundamentales para mejorar la eficiencia podría haberlos ayudado.

    
respondido por el Macneil 02.07.2011 - 20:45
fuente
5

Además de los puntos de Macneils ...

Los árboles rojo-negro son quizás más directamente útiles porque existen operaciones eficientes útiles que no son ampliamente compatibles en implementaciones de bibliotecas estándar como C ++ std::map (al menos AFAIK). Los árboles rojo-negro pueden admitir "dividir" (cortar un árbol en dos, uno que contiene claves menos que una clave específica y otro que contiene claves mayores) y "unir" (al revés, que combina un árbol de teclas grandes con un árbol pequeño) Las teclas) se pueden hacer en O (log n), pero si son compatibles con las bibliotecas de contenedor estándar, parece ser una cosa bien oculta.

Sin embargo, "aumentar" las estructuras de datos es común. Un ejemplo simple es agregar información de tamaño de subárbol a los nodos en casi cualquier estructura de datos de árbol para admitir los subíndices O (log n). Los ejemplos más sofisticados incluyen árboles de intervalo.

Una vez que tenga la idea de aumentar las estructuras de datos, hay muchas variaciones que pueden ser útiles para aplicaciones particulares, y muy pocas están disponibles preempaquetadas como una biblioteca. Las estructuras de datos de la biblioteca estándar existentes (por ejemplo, como std::map ) no pueden aumentarse antes de copiar el código fuente y modificarlo directamente, no puede aumentarlas utilizando parámetros de plantilla.

Por supuesto, para desarrollar una estructura de datos aumentada, debe comprender la estructura de datos no aumentada subyacente.

Los árboles AVL pueden ser más rápidos que los árboles rojo-negro si realiza muchas más búsquedas que inserciones / eliminaciones (y siempre que no necesite esas operaciones de división / combinación), por lo tanto, dependiendo de la aplicación, pueden ser muy Buena base para aumentar.

    
respondido por el Steve314 03.07.2011 - 02:20
fuente
5

No

Realmente no es útil en el mundo real ...

Excepto que te haga pensar .

El mundo real tiene problemas mucho más difíciles , muchos de los cuales no ya tienen soluciones conocidas.

    
respondido por el Steven A. Lowe 03.07.2011 - 05:30
fuente

Lea otras preguntas en las etiquetas