Ok, supongo que no hubo muchas referencias o investigaciones para responder a esta pregunta. En cambio, me he tomado el tiempo de probar tus diferentes ideas y árboles. No encontré nada mucho mejor que los árboles RB, pero tal vez sea solo un sesgo de búsqueda.
El árbol de RB puede ser (inserción) equilibrada con cuatro reglas simples, como shown by 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 pueden equilibrarse de una manera el modelo a juego 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 a ser generalmente considerados inferiores a los árboles RB, es probable que no vale la pena la molestia adicional.
árboles AA en teoría podría 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 implementación menos estándar de árboles AA, sin usar rangos, pero algo más similar a R y B, funcione bien.
Los árboles de estrato son difíciles porque necesita centrarse en un solo nodo, en lugar de la estructura estática del árbol. Se puede hacer por merging insert and splay.
Treaps también son difíciles de hacer en un entorno funcional, ya que no tiene un generador aleatorio global, pero necesita mantener instancias en cada nodo.Esto se puede abordar con leaving the task of generating priorities to the client, pero incluso así, no puede hacer una comparación de prioridades mediante la coincidencia de patrones.
No es una respuesta directa, pero tiene una lectura de "Estructuras de datos puramente funcionales" para obtener algunas buenas ideas. –
Me gusta. No entra mucho en estructuras detalladas, pero ofrece un buen punto de vista general. –
¿Necesita un árbol de búsqueda o una representación en árbol de una secuencia (como fingertrees, con concatenación y división)? En este último caso, los 2-3 árboles puramente funcionales son triviales. – jkff