En informática , un árbol de dedos es una estructura de datos puramente funcional que se puede utilizar para implementar de manera eficiente otras estructuras de datos funcionales. Un árbol de dedos da acceso en tiempo constante amortizado a los "dedos" (hojas) del árbol, que es donde se almacenan los datos, y la concatenación y división del tiempo logarítmico en el tamaño de la pieza más pequeña. También almacena en cada nodo interno el resultado de aplicar alguna operación asociativa a sus descendientes. Estos datos de "resumen" almacenados en los nodos internos se pueden utilizar para proporcionar la funcionalidad de estructuras de datos distintas de los árboles.
Descripción general
Ralf Hinze y Ross Paterson afirman que un árbol de dedos es una representación funcional de secuencias persistentes que pueden acceder a los extremos en un tiempo constante amortizado. La concatenación y la división se pueden realizar en tiempo logarítmico en el tamaño de la pieza más pequeña. La estructura también se puede convertir en una estructura de datos de propósito general definiendo la operación de división en una forma general, lo que le permite actuar como una secuencia, cola de prioridad, árbol de búsqueda o cola de búsqueda de prioridad, entre otras variedades de tipos de datos abstractos. [1]
Un dedo es un punto donde se puede acceder a parte de una estructura de datos; en lenguajes imperativos, esto se llama puntero. [2] En un árbol de dedos, los dedos son estructuras que apuntan a los extremos de una secuencia, o los nodos de las hojas. Los dedos se agregan al árbol original para permitir un acceso constante a los dedos. En las imágenes que se muestran a continuación, los dedos son las líneas que se extienden desde la columna hasta los ganglios.
Un árbol de dedos se compone de diferentes capas que pueden ser identificadas por los nodos a lo largo de su columna . La columna vertebral de un árbol se puede considerar como el tronco de la misma manera que los árboles tienen hojas y raíz. Aunque los árboles de dedos a menudo se muestran con la columna y las ramas saliendo de los lados, en realidad hay dos nodos en la columna en cada nivel que se han emparejado para formar esta columna central. El prefijo está a la izquierda del lomo, mientras que el sufijo está a la derecha. Cada uno de esos nodos tiene un enlace al siguiente nivel de la columna hasta que llegan a la raíz. [2]
El primer nivel del árbol contiene sólo valores, los nodos de las hojas del árbol, y es de profundidad 0. El segundo nivel es de profundidad 1. El tercero es de profundidad 2 y así sucesivamente. Cuanto más cerca de la raíz, más profundos son los subárboles del árbol original (el árbol antes de que fuera un árbol de dedos) a los que apuntan los nodos. De esta manera, trabajar hacia abajo del árbol va desde las hojas hasta la raíz del árbol, que es lo opuesto a la estructura de datos típica de un árbol. Para obtener esta estructura agradable e inusual, debemos asegurarnos de que el árbol original tenga una profundidad uniforme. Para asegurar que la profundidad sea uniforme, al declarar el objeto nodo, debe parametrizarse por el tipo de hijo. Los nodos en el lomo de profundidad 1 y superior apuntan a árboles, y con esta parametrización pueden ser representados por los nodos anidados. [3]
Transformar un árbol en un árbol de dedos
Comenzaremos este proceso con un árbol 2-3 equilibrado . Para que el árbol de dedos funcione, todos los nodos de las hojas también deben estar nivelados.
Un dedo es "una estructura que proporciona un acceso eficiente a los nodos de un árbol cerca de una ubicación distinguida". [1] Para hacer un árbol de dedos, debemos colocar los dedos en los extremos derecho e izquierdo del árbol y transformarlo como una cremallera . Esto nos da ese acceso constante de tiempo amortizado a los extremos de una secuencia.
Para transformar, comience con el árbol 2-3 equilibrado.
Tome los nodos internos más a la izquierda y más a la derecha del árbol y tire de ellos hacia arriba para que el resto del árbol cuelgue entre ellos como se muestra en la imagen de la derecha.
Combina las espinas para hacer un árbol estándar de 2-3 dedos.
Esto se puede describir como: [1]
datos FingerTree a = Vacío | Soltero a | Profundo ( Dígito a ) ( Árbol de dedos ( Nodo a )) ( Dígito a ) datos Nodo a = Nodo2 a a | Nodo3 a a a
Los dígitos de los ejemplos mostrados son los nodos con letras. Cada lista está dividida por el prefijo o sufijo de cada nodo en la columna. En un árbol 2-3 transformado, parece que las listas de dígitos en el nivel superior pueden tener una longitud de dos o tres, mientras que los niveles inferiores solo tienen una longitud de uno o dos. Para que algunas aplicaciones de árboles de dedos se ejecuten de manera tan eficiente, los árboles de dedos permiten entre uno y cuatro subárboles en cada nivel. Los dígitos del árbol de dedos se pueden transformar en una lista así: [1]
tipo Dígito a = Uno a | Dos a un | Tres a a a | Cuatro a a a a
Y así, en la imagen, el nivel superior tiene elementos de tipo una , el siguiente tiene elementos de tipo nodo A debido a que el nodo de entre la columna y las hojas, y esto iría en lo que significa, en general, que el n º nivel del árbol tiene elementos de tipo a , o 2-3 árboles de profundidad n. Esto significa que una secuencia de n elementos está representada por un árbol de profundidad Θ (log n ). Aún mejor, un elemento d lugares desde el extremo más cercano se almacena a una profundidad de Θ (log d) en el árbol. [1]
Reducciones
Operaciones deque
Los árboles de dedos también son deques eficientes . Tanto si la estructura es persistente como si no, todas las operaciones toman Θ (1) tiempo de amortización. El análisis se puede comparar con los deques implícitos de Okasaki, la única diferencia es que el tipo FingerTree almacena nodos en lugar de pares. [1]
Solicitud
Los árboles de dedos se pueden usar para construir otros árboles. [4] Por ejemplo, se puede implementar una cola de prioridad etiquetando los nodos internos por la prioridad mínima de sus hijos en el árbol, o se puede implementar una lista / matriz indexada con un etiquetado de nodos por el recuento de hojas en su niños. Otras aplicaciones son secuencias de acceso aleatorio, que se describen a continuación, secuencias ordenadas y árboles de intervalos . [1]
Los árboles de dedos pueden proporcionar O (1) empujar, invertir, hacer estallar, O (log n) agregar y dividir; y se puede adaptar para ser secuencias indexadas u ordenadas. Y como todas las estructuras de datos funcionales, es inherentemente persistente ; es decir, siempre se conservan las versiones anteriores del árbol.
Secuencias de acceso aleatorio
Los árboles de dedos pueden implementar de manera eficiente secuencias de acceso aleatorio. Esto debería apoyar las operaciones rápido de posición incluyendo el acceso a la n -ésimo elemento y la división de una secuencia en una posición determinada. Para hacer esto, anotamos el árbol de dedos con tamaños. [1]
newtype Size = Size { getSize :: N } derivando ( Eq , Ord )instancia Monoide Tamaño donde ∅ = Tamaño 0 Tamaño m ⊕ Tamaño n = Tamaño ( m + n )
La N es para números naturales. El nuevo tipo es necesario porque el tipo es portador de diferentes monoides. Todavía se necesita otro tipo nuevo para los elementos de la secuencia, que se muestra a continuación.
newtype Elem a = Elem { getElem :: a } newtype Seq a = Seq ( Tamaño del árbol de dedos ( Elem a )) instancia Medida ( Elem a ) Tamaño donde || Elem || = Talla 1
Estas líneas de código muestran que la instancia funciona como un caso base para medir los tamaños y los elementos son de tamaño uno. El uso de newtype s no causa una penalización de tiempo de ejecución en Haskell porque en una biblioteca, los tipos Size y Elem estarían ocultos al usuario con funciones contenedoras.
Con estos cambios, la longitud de una secuencia ahora se puede calcular en tiempo constante.
Primera publicacion
Los árboles de dedos fueron publicados por primera vez en 1977 por Leonidas J. Guibas , [5] y desde entonces fueron refinados periódicamente (por ejemplo, una versión que usa árboles AVL , [6] árboles de dedos no perezosos, árboles de dedos 2-3 más simples que se muestran aquí, [1] B -Árboles y así sucesivamente)
Implementaciones
Desde entonces, los árboles de dedos se han utilizado en las bibliotecas centrales de Haskell (en la implementación de Data.Sequence ), y existe una implementación en OCaml [7] que se derivó de una implementación Coq probada y correcta . [8] Los árboles de dedos se pueden implementar con o sin evaluación perezosa , [9] pero la pereza permite implementaciones más simples.
Ver también
Referencias
- ^ a b c d e f g h i Hinze, Ralf; Paterson, Ross (2006), "Árboles de dedos: una estructura de datos simple de propósito general" (PDF) , Journal of Functional Programming , 16 (2): 197–217, doi : 10.1017 / S0956796805005769.
- ^ a b Gibiansky, Andrew. "Árboles de dedos - Andrew Gibiansky" . andrew.gibiansky.com . Consultado el 26 de octubre de 2017 .
- ^ "Árboles de dedos bien hechos (espero)" . Buenas matemáticas, malas matemáticas . Consultado el 26 de octubre de 2017 .
- ^ Sarkar, Abhiroop. "Finger Tree - ¿La estructura de datos definitiva?" . abhiroop.github.io . Consultado el 26 de octubre de 2017 .
- ^ Guibas, LJ ; McCreight, EM; Plass, MF; Roberts, JR (1977), "Una nueva representación para listas lineales", Registro de la Conferencia del Noveno Simposio Anual de ACM sobre Teoría de la Computación , págs. 49–60.
- ^ Tsakalidis, AK (1985), "AVL-trees for localized search", Information and Control , 67 (1-3): 173-194, doi : 10.1016 / S0019-9958 (85) 80034-6.
- ^ Noticias semanales de Caml
- ^ Matthieu Sozeau :: Árboles de dedos dependientes en Coq
- ^ Kaplan, H .; Tarjan, RE (1995), "Listas persistentes con catenciones mediante desaceleración recursiva", Actas del Vigésimo Séptimo Simposio Anual de ACM sobre Teoría de la Computación , págs. 93-102.
enlaces externos
- http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
- http://hackage.haskell.org/packages/archive/EdisonCore/1.2.1.1/doc/html/Data-Edison-Concrete-FingerTree.html
- Ejemplo de 2-3 árboles en C #
- Ejemplo de árboles de dedos Hinze / Paterson en Java
- Ejemplo de árboles de dedos Hinze / Paterson en C #
- "Monoides y árboles de dedos en Haskell"
- "Biblioteca de árbol de dedos para Clojure"
- "Árbol de dedos en Scalaz"
- "Árboles de dedos verificados en Isabelle / HOL"