Diferencia entre árboles AVL y árboles splay

Estoy estudiando sobre varios árboles, y me encontré con árboles AVL y árboles splay. Quiero saber

  1. ¿Cuál es la diferencia entre los árboles AVL y los árboles splay?
  2. ¿Sobre qué base seleccionamos estos árboles?
  3. ¿Cuáles son los positivos y los negativos de estos árboles?
  4. ¿Cuáles son las actuaciones de estos árboles en términos de notación big O?
Author: templatetypedef, 2011-09-19
Source

2 answers

  1. Tanto los árboles splay como los árboles AVL son árboles de búsqueda binarios con excelentes garantías de rendimiento, pero difieren en cómo logran garantizar ese rendimiento. En un árbol AVL, la forma del árbol está limitada en todo momento de tal manera 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 inserciones y eliminaciones, y no cambia durante las búsquedas. Splay árboles, por otro lado, mantener eficiente por remodelando el árbol en respuesta a las búsquedas en él. De esa manera, 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 de splay no está restringida, y varía según las búsquedas que se realicen.

  2. No hay una regla dura y rápida 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 las operaciones toman 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 splay 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 splay sea mejor. Además, los árboles de splay soportan algunas operaciones como dividir y fusionar de manera muy eficiente, mientras que las operaciones de árboles AVL correspondientes son más involucradas y menos eficientes. Los árboles Splay son más memoria eficiente que los árboles AVL, porque no necesitan almacenar información de balance en los nodos. Sin embargo, los árboles AVL son más útiles en entornos multihilo con muchas búsquedas, porque las búsquedas en un árbol AVL se pueden hacer en paralelo mientras que no se pueden hacer en árboles splay. Debido a que los árboles de splay se remodelan a sí mismos en función de las búsquedas, si solo necesita acceder a un pequeño subconjunto de los elementos del árbol, o si accede a algunos elementos mucho más que a otros, el árbol de splay superará al AVL arbol. Finalmente, los árboles splay 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. Véase (2)

  4. La inserción, la eliminación y las búsquedas en el árbol AVL toman O (log n) tiempo cada una. Los árboles Splay tienen estas 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!

 64
Author: templatetypedef,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-02-04 22:06:39

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

Son similares en estructura y en las operaciones que les llamamos. La diferencia es que en los árboles splay, 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 Splay 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á acceso a un subconjunto de los datos con mucha frecuencia que otros. En este caso, los datos a los que accede con frecuencia se acercarán a la raíz como resultado del splay. Además, se puede acceder a cualquier nodo con menos tiempo que antes.

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

3) ¿Cuáles son los positivos y los negativos de estos árboles?

Lo positivo para ambos es que obtener alrededor de registro (n) en ambas estructuras de datos teóricamente.

Como se mencionó, los árboles de splay tienen un log(n) promedio sobre un número de 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 compensará al acceder a los elementos frecuentes.

El negativo del árbol de búsqueda binario es que, debe tener suerte de tener log(n) siempre. Si las claves no son aleatorias, entonces el árbol se reducirá a una forma de lista con solo una lado.

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

Splay tree Log(n) en promedio para un grupo de operaciones de árbol. Registro de árbol binario (n) solo si sus claves 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 splaying.

 3
Author: Harisankar Krishna Swamy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-01-18 03:40:56