algorithm - precio - red black tree python
¿Son AVL Trees Evil? (6)
Estaba leyendo el article de Steve Yegge sobre singletons. En él menciona que su maestro le dijo que los árboles AVL eran malos. ¿Es solo que los árboles rojos y negros son una mejor solución?
¿Mal desde qué punto de vista?
Como siempre: no hay malas herramientas, solo malos artesanos.
En mi memoria, los árboles AVL tienen una inserción / eliminación más lenta pero una recuperación más rápida que el rojo / negro. Principalmente por el algoritmo de equilibrio.
Aquí hay mucha información sobre las diferencias entre Red-Black y AVL-Trees:
http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948
y un artículo comparando las diferentes estructuras:
http://www.stanford.edu/~blp/papers/libavl.pdf
En resumen: AVL es más rápido de buscar, Rojo-Negro más rápido de insertar.
Estoy seguro de que los árboles AVL son malvados de la misma manera que GOTO es malvado o BURBUJA ORDEN es malvado.
Los algoritmos no son malos, pero los algoritmos tampoco saltan hacia arriba y hacia abajo para decirte cuándo son apropiados.
No, los árboles AVL ciertamente no son malvados en ningún aspecto. Son una estructura de árbol de equilibrio propio completamente válida. Tienen características de rendimiento diferentes a las de los árboles rojo-negro y, por lo general, estas diferencias hacen que las personas elijan un árbol rojo-negro sobre un árbol AVL. Pero esto no los hace malos.
No, no son malvados, solo un poco difíciles de programar.
Árboles AVL http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Red black tree link desde allí también.
Splay Los árboles son mucho más frescos. :)