Diferencia entre los árboles de AVL y los árboles de separación

Question

Estoy estudiando sobre varios árboles, y encontré árboles de AVL y árboles. Quiero saber

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

Answer 1

1. Ambos árbol biselado y árboles AVL son árboles binarios de búsqueda con excelentes garantías de rendimiento, pero difieren en la forma en que logran los garantizan que el rendimiento. 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 existe una regla rígida al respecto. 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. inserción árbol AVL, deleción, y las búsquedas toman O tiempo cada (log n). 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.

Hope this helps!

Answer 2

1) ¿Cuál es la diferencia entre los árboles AVL y los árboles de separación?

Son similares en estructura y en las operaciones que les solicitamos. 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) ¿En base a qué seleccionamos estos árboles?

Los árboles de separación siempre son mejores que los árboles de búsqueda binaria 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?

Positivas para ambos es que se obtiene el registro (n) en ambas estructuras de datos teóricamente.

Como se ha mencionado, los árboles de separación tienen un registro promedio (n) en 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 los rendimientos de estos árboles en términos de la notación O grande?

Árbol de registro Log (n) en Promedio para un grupo de operaciones de árbol. Árbol binario Inicie sesión (n) solo si sus llaves van al azar.

Los resultados en el tiempo de ejecución son obvios aquí splay tree runtime profiling Puede ver la diferencia de tiempo de ejecución en la búsqueda con y sin expansión.