¿Qué árbol binario de equilibrio automático recomendarías?

18

Estoy aprendiendo Haskell y como ejercicio estoy haciendo árboles binarios. Habiendo hecho un árbol binario regular, quiero adaptarlo para que sea auto equilibrado. Entonces:

  • ¿Cuál es más eficiente?
  • ¿Cuál es más fácil de implementar?
  • ¿Cuál se usa con más frecuencia?

Pero crucialmente, ¿cuál me recomiendan?

Supongo que esto pertenece aquí porque está abierto a debate.

dan_waterworth
fuente
En términos de eficiencia y facilidad de implementación, las eficiencias generales están bien definidas, pero para su implementación, creo que lo mejor sería implementar tantas como pueda encontrar y luego háganos saber cuál funciona mejor ...
glenatron

Respuestas:

15

Le recomendaría que comience con un árbol Rojo-Negro o un árbol AVL .

El árbol rojo-negro es más rápido para insertar, pero el árbol AVL tiene una ligera ventaja para las búsquedas. El árbol AVL es probablemente un poco más fácil de implementar, pero no mucho en base a mi propia experiencia.

El árbol AVL asegura que el árbol esté equilibrado después de cada inserción o eliminación (ningún subárbol tiene un factor de equilibrio mayor que 1 / -1, mientras que el árbol Rojo-negro asegura que el árbol esté razonablemente equilibrado en cualquier momento.

Quick Joe Smith
fuente
1
Personalmente, encuentro el inserto rojo-negro más fácil que el inserto AVL. La razón es a través de la analogía (imperfecta) de los árboles B. Las inserciones son complicadas, pero las eliminaciones son malas (hay muchos casos a considerar). De hecho, ya no tengo una implementación de eliminación de rojo y negro de C ++ propia: la eliminé cuando me di cuenta de que (1) nunca la estaba usando; cada vez que quería eliminar estaba eliminando varios elementos, por lo que convertí de árbol a lista, eliminar de la lista, luego convertir de nuevo a un árbol, y (2) se rompió de todos modos.
Steve314
2
@ Steve314, los árboles rojo-negros son más fáciles, pero ¿no ha podido hacer una implementación que funcione? ¿Cómo son entonces los árboles AVL?
dan_waterworth 01 de
@dan_waterworth: aún no he realizado una implementación con un método de inserción que funcione, tenga notas, entienda el principio básico, pero nunca obtuve la combinación correcta de motivación, tiempo y confianza. Si solo quería versiones que funcionen, eso es solo copiar-pseudocódigo-de-libro de texto-y-traducir (y no olvide que C ++ tiene contenedores de biblioteca estándar), pero ¿dónde está la diversión en eso?
Steve314
Por cierto, creo (pero no puedo proporcionar la referencia) que un libro de texto bastante popular incluye una implementación defectuosa de uno de los algoritmos de árbol binario equilibrado, no estoy seguro, pero podría ser una eliminación rojo-negro. Así que no soy solo yo ;-)
Steve314
1
@ Steve314, lo sé, los árboles pueden ser endiabladamente complicados en lenguaje imperativo, pero sorprendentemente, implementarlos en Haskell ha sido muy fácil. He escrito un árbol AVL regular y también una variante espacial 1D durante el fin de semana y ambos tienen solo 60 líneas.
dan_waterworth
10

Consideraría una alternativa si está bien con estructuras de datos aleatorias : Saltar listas .

Desde un punto de vista de alto nivel, es una estructura de árbol, excepto que no se implementa como un árbol sino como una lista con múltiples capas de enlaces.

Obtendrá O (log N) inserciones / búsquedas / eliminaciones, y no tendrá que lidiar con todos esos casos difíciles de reequilibrio.

Sin embargo, nunca he considerado implementarlos en un lenguaje funcional, y la página de wikipedia no muestra ninguno, por lo que puede no ser fácil (wrt a inmutabilidad)

Matthieu M.
fuente
Realmente disfruto de las listas de omisión y las he implementado antes, aunque no en un lenguaje funcional. Creo que los intentaré después de esto, pero en este momento estoy en árboles auto equilibrados.
dan_waterworth 01 de
Además, las personas a menudo usan listas de salto para estructuras de datos concurrentes. Puede ser mejor, en lugar de forzar la inmutabilidad, usar las primitivas de concurrencia de Haskell (como MVar o TVar). Sin embargo, esto no me enseñará mucho sobre cómo escribir código funcional.
dan_waterworth 01 de
2
@ Fanatic23, una lista de salto no es un ADT. El ADT es un conjunto o una matriz asociativa.
dan_waterworth 01 de
@dan_waterworth mi mal, tienes razón.
Fanatic23
5

Si desea comenzar con una estructura relativamente fácil (tanto los árboles AVL como los árboles rojo-negros son complicados), una opción es un treap, denominado como una combinación de "árbol" y "montón".

Cada nodo obtiene un valor de "prioridad", a menudo asignado aleatoriamente a medida que se crea el nodo. Los nodos se colocan en el árbol de modo que se respete el orden de las claves y se respete el orden de los valores de prioridad en forma de montón. La ordenación de tipo montón significa que ambos hijos de un padre tienen prioridades más bajas que el padre.

EDITAR eliminado "dentro de los valores clave" arriba: la prioridad y el orden de las claves se aplican juntos, por lo que la prioridad es importante incluso para las claves únicas.

Es una combinación interesante. Si las claves son únicas y las prioridades son únicas, existe una estructura de árbol única para cualquier conjunto de nodos. Aun así, las inserciones y eliminaciones son eficientes. Estrictamente hablando, el árbol puede estar desequilibrado hasta el punto en que es efectivamente una lista vinculada, pero esto es extremadamente improbable (como con los árboles binarios estándar), incluso en casos normales como claves insertadas en orden (a diferencia de los árboles binarios estándar).

Steve314
fuente
1
+1. Treaps es mi elección personal, incluso escribí una publicación de blog sobre cómo se implementan.
P Shved
5

¿Cuál es más eficiente?

Vago y difícil de responder. Las complejidades computacionales están bien definidas. Si eso es lo que quiere decir con eficiencia, no hay un debate real. De hecho, todos los buenos algoritmos vienen con pruebas y factores de complejidad.

Si quiere decir "tiempo de ejecución" o "uso de memoria", deberá comparar las implementaciones reales. Luego, el lenguaje, el tiempo de ejecución, el sistema operativo y otros factores entran en juego, lo que hace que la pregunta sea difícil de responder.

¿Cuál es más fácil de implementar?

Vago y difícil de responder. Algunos algoritmos pueden parecerle complejos, pero triviales para mí.

¿Cuál se usa con más frecuencia?

Vago y difícil de responder. Primero está el "¿por quién?" parte de esto? ¿Haskell solo? ¿Qué pasa con C o C ++? En segundo lugar, está el problema del software propietario en el que no tenemos acceso a la fuente para realizar una encuesta.

Pero crucialmente, ¿cuál me recomiendan?

Supongo que esto pertenece aquí porque está abierto a debate.

Correcto. Dado que sus otros criterios no son muy útiles, esto es todo lo que obtendrá.

Puede obtener el origen de una gran cantidad de algoritmos de árbol. Si desea aprender algo, simplemente puede implementar cada uno que pueda encontrar. En lugar de pedir una "recomendación", simplemente recopile todos los algoritmos que pueda encontrar.

Aquí está la lista:

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Hay seis populares definidos. Comience con esos.

S.Lott
fuente
3

Si está interesado en los árboles Splay, hay una versión más simple de los que creo que fue descrita por primera vez en un artículo de Allen y Munroe. No tiene las mismas garantías de rendimiento, pero evita complicaciones al tratar con el reequilibrio "zig-zig" frente a "zig-zag".

Básicamente, al buscar (incluidas las búsquedas de un punto de inserción o nodo para eliminar), el nodo que encuentra se gira directamente hacia la raíz, de abajo hacia arriba (por ejemplo, cuando sale una función de búsqueda recursiva). En cada paso, selecciona una rotación única hacia la izquierda o hacia la derecha, dependiendo de si el niño al que desea subir otro paso hacia la raíz era el niño derecho o el izquierdo (si recuerdo mis direcciones de rotación correctamente, eso es, respectivamente).

Al igual que los árboles Splay, la idea es que los elementos a los que se haya accedido recientemente siempre estén cerca de la raíz del árbol, por lo que es rápido acceder nuevamente. Siendo más simple, estos árboles Allen-Munroe de rotación a raíz (lo que yo llamo, no sé el nombre oficial) pueden ser más rápidos, pero no tienen la misma garantía de rendimiento amortizada.

Una cosa: dado que esta estructura de datos, por definición, muta incluso para las operaciones de búsqueda, probablemente deba implementarse de forma monádica. IOW tal vez no sea una buena opción para la programación funcional.

Steve314
fuente
Los juegos son un poco molestos dado que modifican el árbol incluso cuando se encuentran. Esto sería bastante doloroso en entornos de subprocesos múltiples, que es una de las grandes motivaciones para usar un lenguaje funcional como Haskell en primer lugar. Por otra parte, nunca he usado lenguajes funcionales antes, así que quizás esto no sea un factor.
Quick Joe Smith
@ Rápido: depende de cómo vaya a utilizar el árbol. Si lo estuviera utilizando en un código de estilo funcional verdadero, dejaría caer la mutación en cada hallazgo (haciendo que un árbol Splay sea un poco tonto), o terminaría duplicando una parte sustancial del árbol binario en cada búsqueda, y haga un seguimiento del estado del árbol con el que está trabajando a medida que avanza su trabajo (la razón por la que probablemente use un estilo monádico). El compilador podría optimizar esa copia si ya no hace referencia al estado del árbol viejo después de que se crea el nuevo (suposiciones similares son comunes en la programación funcional), pero puede que no.
Steve314
Ninguno de los dos enfoques parece que valga la pena. Por otra parte, tampoco lo hacen los lenguajes puramente funcionales en su mayor parte.
Quick Joe Smith
1
@Quick: duplicar el árbol es lo que hará para cualquier estructura de datos de árbol en un lenguaje funcional puro para algoritmos de mutación tales como inserciones. En términos fuente, el código no será tan diferente del código imperativo que realiza actualizaciones en el lugar. Las diferencias ya se han manejado, presumiblemente, para árboles binarios desequilibrados. Mientras no intente agregar enlaces primarios a los nodos, los duplicados compartirán subárboles comunes como mínimo, y la optimización profunda en Haskell es bastante dura, si no perfecta. Soy anti-Haskell en principio, pero esto no es necesariamente un problema.
Steve314
2

Un árbol equilibrado muy simple es un árbol AA . Su invariante es más simple y, por lo tanto, más fácil de implementar. Debido a su simplicidad, su rendimiento sigue siendo bueno.

Como ejercicio avanzado, puede intentar utilizar GADT para implementar una de las variantes de árboles equilibrados cuya invariante se aplica mediante el tipo de sistema de tipos.

Petr Pudlák
fuente