Lo autobalanceo árbol es el más simple de programación funcional?

Question

Estoy diseñando un árbol de auto equilibrio en Haskell. A modo de ejercicio y porque es bueno tener en su mano.

Anteriormente en C y Python I preferidos Treaps y Splay árboles debido a sus simples equilibrio de reglas. Siempre me gustó R / B árboles, ya que parecían más trabajo de lo que valían.

Ahora, debido a la naturaleza funcional de Haskell, las cosas parecen haber cambiado. Puedo escribir una función de inserción R / B en 10 líneas de código. Treaps por el contrario requiere de embalaje para almacenar el generador de números aleatorios, y Splay Los árboles son un dolor para hacer de arriba hacia abajo.

Así que estoy preguntando si tiene experiencia con otros tipos de árboles? Cuáles son mejores en la utilización de la coincidencia de patrones y la naturaleza de los lenguajes funcionales de arriba hacia abajo?

Answer 1

Ok, supongo que no había una gran cantidad de referencias o de investigación para responder a esta pregunta. En su lugar he tomado el tiempo para probar sus diferentes ideas y árboles. No he encontrado nada mucho mejor que los árboles RB, pero tal vez eso es sólo busco sesgo.

El árbol de RB puede ser (inserción) equilibrada con cuatro reglas simples, como mostrado por Chris Okasaki :

balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance T (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance T a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance T a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance T a x b = T B a x b

árboles AVL puede equilibrarse de una manera coincidencia de patrones similar. Sin embargo, las reglas no se comprimen, así:

balance T (T (T a x b   dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d  0) 0
balance T a x (T b y (T c z d   dz)   1 )   2  = T (T a x b  0) y (T c z d dz) 0
balance T (T a x (T b y c   1 )   1 ) z d (-2) = T (T a x b -1) y (T c z d  0) 0
balance T (T a x (T b y c (-1))   1 ) z d (-2) = T (T a x b  0) y (T c z d  1) 0
balance T (T a x (T b y c   _ )   1 ) z d (-2) = T (T a x b  0) y (T c z d  0) 0
balance T a x (T (T b y c   1 ) z d (-1))   2  = T (T a x b -1) y (T c z d  0) 0
balance T a x (T (T b y c (-1)) z d (-1))   2  = T (T a x b  0) y (T c z d  1) 0
balance T a x (T (T b y c   _ ) z d (-1))   2  = T (T a x b  0) y (T c z d  0) 0
balance t = t

Como AVL árboles costuras que se considera generalmente inferiores a los árboles RB, que son, probablemente, no vale la pena la molestia adicional.

árboles AA teóricamente podrían ser agradable equilibrada y fácilmente por:

balance T n (T n a x b) y c = T n a x (T n b y c) -- skew
balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split
balance T n a x b = T n a x b

Pero, por desgracia Haskell no les gusta la sobrecarga de n. Es posible que una aplicación menos estándar de los árboles AA, no utilizando filas, sino algo más similar a R y B, que funcionan bien.

árbol biselado son difíciles porque hay que centrarse en un solo nodo, en lugar de la estructura estática del árbol. Se puede hacer por fusión de inserción y ensanchamiento .

Treaps también son incómodos de hacer en un entorno funcional, ya que no tiene un generador aleatorio global, pero necesidad de mantener casos en cada nodo. Esto puede ser abordado por dejando la tarea de generar prioridades a la cliente, pero aún así, no se puede hacer la comparación prioridad usando coincidencia de patrones.

Answer 2

Como usted dice árbol rojo-negro no es que son difíciles de usar. ¿Usted ha dado un vistazo ? Quizás se encuentre interesado en el aumento de la estructura de datos de base con algo así como un cremallera. Otro árbol que puede encontrar interesante es la href="http://en.wikipedia.org/wiki/AA_tree" rel="nofollow"> árbol AA se es una simplificación de la Red árboles Negro.

Answer 3

Es la única que ya está implementado.

Hay buenas implementaciones en Haskell de árboles equilibrados como Data.Map y Data.Set. No cumplen sus necesidades? No reimplementar, reutilización.

Answer 4

La biblioteca estándar OCaml utiliza un árbol AVL por su funtor map. Parece que es más fácil de implementar que un RB-árbol si se incluye una operación remove.