24
Estaba leyendo el article de Steve Yegge sobre singletons. En él menciona que su maestro le dijo que AVL Trees era malvado. ¿Es solo que los árboles rojos y negros son una mejor solución?Son AVL Trees Evil?
A
Respuesta
19
Mal de qué punto de vista?
Como siempre: no hay malas herramientas, solo malos artesanos.
En mi memoria, los árboles AVL tienen una inserción/extracción más lenta pero una recuperación más rápida que Red/black. Principalmente debido al algoritmo de equilibrio.
+4
Exactamente. Si necesita un mapa de escritura una vez lectura muchos, los árboles AVL son difíciles de superar. En mi opinión, también son más fáciles de implementar correctamente. – erickson
+5
Un mapa write-once-read-many suena más como una matriz ordenada para mí ... Un mapa write-rarely-read-many suena más que un árbol AVL. Sin embargo, incluso en esos casos, asegúrese de considerar una matriz ordenada. Los costos constantes son considerablemente más bajos, por lo que necesitará muchas entradas antes de que un árbol AVL supere tanto al árbol rojo/negro como a una matriz ordenada. –
+3
Los árboles AVL son sin embargo altamente comprensibles. Los implementadores no entienden los árboles RB, los RIM simplemente están siguiendo las reglas; no comprenden realmente lo que está pasando, conceptualmente. –
8
No, los árboles AVL ciertamente no son malvados en ningún aspecto. Son una estructura de árbol de auto-equilibrio completamente válida. Tienen características de rendimiento diferentes a los árboles Rojo-Negros y, por lo general, estas diferencias llevan a que las personas elijan un árbol rojo-negro sobre un árbol AVL. Pero esto no los hace malvados.
4
Estoy seguro de que los árboles de AVL son malvados de la misma manera que GOTO es malo o BURBULE SORT es malo.
Los algoritmos no son malos, pero los algoritmos tampoco saltan hacia arriba o hacia abajo para decirte cuándo son apropiados.
+6
Goto no es un algoritmo y realmente no es una comparación legítima. – Imagist
+2
El problema con el tipo de burbuja es que no hay compensaciones reales que lo hagan superior. No se puede decir eso para los árboles AVL. –
+5
:: snark :: La clasificación de burbuja usa muy poco código, y se realiza fácilmente en una máquina tradicional de Turing. – dmckee
1
Splay Trees son mucho más geniales. :)
1
No, no son malvados, solo un poco complicado de programar.
AVL Árboles http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
enlace árbol Negro Rojo desde allí también.
2
Aquí hay una gran cantidad de información sobre las diferencias entre Rojo-Negro y AVL-árboles:
http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948
y un documento de la comparación de las diferentes estructuras:
http://www.stanford.edu/~blp/papers/libavl.pdf
En pocas palabras - AVL es más rápido de buscar, Rojo-Negro más rápido de insertar.
+0
El enlace de fogcreek es malo. El contenido es engañoso Los árboles AVL no requieren rotaciones O (log n) para reequilibrar. Max 2. – Jesse
Cuestiones relacionadas
- 1. .NET built-in AVL-Tree?
- 2. ¿Por qué Class.newInstance() "evil"?
- 3. Django Includes - are they evil?
- 4. Diferencia entre B-Trees y 2-3-4 Trees
- 5. AVL diccionario árbol
- 6. Java Crit-bit Trees
- 7. Backbone.js y hierarchies/trees
- 8. Hash Table v/s Trees
- 9. balanceando un árbol AVL (C++)
- 10. Árbol AVL contra árbol B
- 11. Fusionando 2 árboles AVL DIFERENTES
- 12. El orden de b-trees
- 13. ¿Cómo funcionan los Suffix Trees?
- 14. Ejemplos de usos de Judy trees
- 15. Cómo configurar el bit Evil en el tráfico saliente
- 16. Concatenar/fusionar/unir dos árboles AVL
- 17. Equilibrio de un árbol binario (AVL)
- 18. Linq Expression Trees en Compact Framework
- 19. ¿Cuáles son las ventajas de los árboles T sobre árboles B +/-?
- 20. ¿Cuándo elegir el árbol RB, B-Tree o AVL?
- 21. ¿Cómo uso kd-trees para determinar la similitud de cadenas?
- 22. ¿Cómo es realmente desequilibrado el ejemplo de Wikipedia de un árbol AVL desequilibrado?
- 23. ¿Cómo generar un árbol AVL lo más desequilibrado posible?
- 24. Manejo duplica llaves dentro de un árbol AVL
- 25. ¿Cuál es exactamente el sentido de Expression Trees?
- 26. Resumen/manual de referencia para Open Firmware Device Trees
- 27. ¿Cómo crear un delegado vacío usando Expression Trees?
- 28. ¿Cómo cambiar el nivel de granularidad de deshacer en emacs evil-mode con undo-tree?
- 29. Diferencia entre los árboles de AVL y los árboles de separación
- 30. B-trees, bases de datos, inserciones secuenciales frente a aleatorios y velocidad. Aleatorio está ganando
OP rep de 666 confirma AVL Trees are Evil – SwDevMan81
Supongo que no podemos votar esta pregunta, ¿no? ;) –