algorithm - rojo - Diferencia entre los árboles AVL y los árboles splay

arboles b

Question

Estoy estudiando varios árboles, y encontré árboles AVL y árboles. quiero saber

1. ¿Cuál es la diferencia entre los árboles AVL y los árboles splay?
2. ¿Sobre qué base seleccionamos estos árboles?
3. ¿Qué son positivos y negativos de estos árboles?
4. ¿Cuáles son las actuaciones de estos árboles en términos de la notación O grande?

Answer 1

1. Tanto los árboles desplegables como los árboles AVL son árboles de búsqueda binarios con excelentes garantías de rendimiento, pero difieren en cómo logran esos resultados. En un árbol AVL, la forma del árbol está restringida en todo momento, de modo que la forma del árbol está equilibrada, lo que significa que la altura del árbol nunca excede O (log n). Esta forma se mantiene en las inserciones y eliminaciones, y no cambia durante las búsquedas. Los árboles de dispersión, por otro lado, se mantienen eficientes al remodelar el árbol en respuesta a búsquedas en él. De esta forma, los elementos a los que se accede con frecuencia se mueven hacia la parte superior del árbol y tienen mejores tiempos de búsqueda. La forma de los árboles desplegables no está restringida y varía según las búsquedas que se realicen.

2. No hay una regla rígida sobre esto. Sin embargo, una diferencia clave entre las estructuras es que los árboles AVL garantizan una búsqueda rápida (O (log n)) en cada operación, mientras que los árboles splay solo pueden garantizar que cualquier secuencia de n operaciones tome como máximo O (n log n) tiempo. Esto significa que si necesita búsquedas en tiempo real, es probable que el árbol AVL sea mejor. Sin embargo, los árboles de dispersión tienden a ser mucho más rápidos en promedio, por lo que si desea minimizar el tiempo de ejecución total de las búsquedas de árboles, es probable que el árbol de distribución sea mejor. Además, los árboles splay admiten algunas operaciones como la división y la fusión de manera muy eficiente, mientras que las operaciones de árbol AVL correspondientes son más complicadas y menos eficientes. Los árboles Splay son más eficientes en memoria que los árboles AVL, ya que no necesitan almacenar información de equilibrio en los nodos. Sin embargo, los árboles AVL son más útiles en entornos multiproceso con muchas búsquedas, ya que las búsquedas en un árbol AVL se pueden realizar en paralelo, mientras que no pueden desplegarse en los árboles. Debido a que los arboles se remodelan a sí mismos en base a búsquedas, si solo necesita acceder a un subconjunto pequeño de los elementos del árbol, o si accede a algunos elementos mucho más que otros, el árbol desplegable superará al árbol AVL. Finalmente, los árboles de cobertura tienden a ser más fáciles de implementar que los árboles AVL, ya que la lógica de rotación es mucho más fácil.

3. Ver (2)

4. La inserción, borrado y búsqueda del árbol AVL toman el tiempo O (log n) cada uno. Los árboles de cobertura tienen las mismas garantías, pero la garantía es solo en un sentido amortizado. Cualquier secuencia larga de operaciones tomará como máximo O (n log n) tiempo, pero las operaciones individuales pueden tomar tanto como O (n) tiempo.

¡Espero que esto ayude!

Answer 2

1) ¿Cuál es la diferencia entre los árboles AVL y los árboles splay?

Son similares en estructura y las operaciones que les pedimos. La diferencia es que en los árboles de cobertura, después de cada operación, tratamos de mantener el árbol casi perfectamente equilibrado para que las operaciones futuras tomen menos tiempo.

2) ¿Sobre qué base seleccionamos estos árboles?

Los árboles de dispersión siempre son mejores que los árboles de búsqueda binarios cuando su aplicación trata con una gran cantidad de datos en el árbol, pero necesitará acceder a un subconjunto de los datos con mucha frecuencia. En este caso, los datos a los que accede con frecuencia se acercarán a la raíz como resultado de la separación. Además, se puede acceder a cualquier nodo con menos tiempo que antes.

Como regla general para seleccionar estos árboles, si necesita un tiempo de registro (n) "promedio" durante un período de operaciones de árbol, utilice el árbol de splay. El árbol binario no puede garantizar esto.

3) ¿Qué son positivos y negativos de estos árboles?

Lo positivo para ambos es que obtienes log (n) en ambas estructuras de datos teóricamente.

Como se mencionó anteriormente, los árboles tienen log (n) promedio sobre varias operaciones. Esto significa que, tal vez tienes n complejidad de tiempo para una operación al menos una vez en ese conjunto. Pero esto se verá compensado al acceder a los artículos frecuentes.

Lo negativo del árbol de búsqueda binaria es que, debe tener la suerte de tener log (n) siempre. Si las claves no son aleatorias, el árbol se reducirá a una lista como formulario con un solo lado.

4) ¿Cuáles son las actuaciones de estos árboles en términos de la notación O grande?

Árbol de Splay Log (n) en Promedio para un grupo de operaciones de árbol. Registro de árbol binario (n) solo si tus claves van al azar.

Los resultados en el tiempo de ejecución son obvios aquí splay perfilado de tiempo de ejecución de árbol Puede ver la diferencia de tiempo de ejecución en la búsqueda con y sin despliegue.