performance - rojo - arboles b
Árbol binario de búsqueda sobre árbol AVL (4)
En primer lugar, obtener el mejor rendimiento posible no es el objetivo final de la programación. Por lo tanto, incluso si la opción B siempre fuera más rápida y consumiera menos memoria que A, no significa que siempre es la mejor opción, si es más complicada. El código más complicado toma más tiempo para escribir, es más difícil de entender y es más probable que contenga errores. Entonces, si la opción A más simple pero menos eficiente es lo suficientemente buena para ti, significa que es la mejor opción.
Ahora, si desea comparar el árbol AVL con el árbol de búsqueda binaria simple (BST) sin equilibrar, entonces AVL consumirá más memoria (cada nodo debe recordar su factor de equilibrio) y cada operación puede ser más lenta (porque necesita mantener el equilibrio factor y a veces realizar rotaciones).
Como dijiste, BST sin balance tiene un peor caso (malo) muy malo. Pero si sabe que este peor caso no le sucederá, o si está bien si la operación es lenta en casos raros, BST sin balance podría ser mejor que AVL.
Por lo que yo sé, la complejidad temporal entre los árboles AVL y los árboles binarios de búsqueda es la misma en el caso promedio, con AVL superando BST en el peor de los casos. Esto me da una pista de que las AVL siempre son superiores a las BST en todas las formas posibles de interactuar con ellas, lo que tal vez agrega un poco de complejidad cuando se trata de equilibrar las implementaciones.
¿Hay alguna razón por la que alguien debería usar BST en lugar de AVL en primer lugar?
Mi suposición es: cuando mencionas BST, te refieres a una BST sin equilibrar.
Podría argumentarse que si necesita una estructura de datos navegable y sabe que sus datos no estarán en el peor de los casos (ordenados) y son algo pequeños, una BST (sin equilibrio) sería adecuada.
Pero es más que probable que sea un caso raro.
El árbol AVL también es BST pero puede reequilibrarse. Este comportamiento lo hace más rápido en el peor de los casos. Se mantiene reequilibrándose así mismo, en el peor de los casos consume el tiempo O (log n) cuando el BST simple toma O (n). Entonces, la respuesta a su pregunta: siempre es mejor implementar el árbol AVL que simplemente BST.
Debido a que existe la sobrecarga adicional de verificar y actualizar los factores de equilibrio y los nodos rotativos, la inserción y eliminación en los árboles AVL puede ser bastante lenta en comparación con las BST no balanceadas.
Debido al equilibrio estrecho, la búsqueda nunca tendrá un tiempo lineal, por lo que es probable que desee utilizar árboles AVL en situaciones donde la búsqueda es una operación más frecuente que la actualización del árbol.