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 brinda 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.
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 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, permitiéndole 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 identificarse por los nodos a lo largo de su columna vertebral . La columna vertebral de un árbol puede considerarse como el tronco de la misma manera que los árboles tienen hojas y una 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 con el siguiente nivel de la columna hasta llegar a la raíz. [2]
El primer nivel del árbol contiene solo valores, los nodos de hoja del árbol, y tiene una profundidad 0. El segundo nivel tiene una profundidad 1. El tercero tiene una 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 anterior a ser un árbol de dedos) a los que apuntan los nodos. De esta manera, trabajar hacia abajo en el árbol va desde las hojas hasta la raíz del árbol, que es lo opuesto a la estructura de datos de árbol típica. Para conseguir esta bonita e inusual estructura, debemos asegurarnos de que el árbol original tenga una profundidad uniforme. Para garantizar que la profundidad sea uniforme, al declarar el objeto de nodo, se debe parametrizar por el tipo de hijo. Los nodos en la columna de profundidad 1 y superiores apuntan a árboles, y con esta parametrización pueden representarse mediante los nodos anidados. [3]
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 acceso eficiente a los nodos de un árbol cerca de una ubicación distinguida". [1] Para hacer un árbol de dedos necesitamos colocar los dedos en los extremos derecho e izquierdo del árbol y transformarlo como una cremallera . Esto nos da ese acceso constante en tiempo amortizado a los finales de una secuencia.
Para transformar, comience con el árbol equilibrado 2-3.
Tome los nodos internos más a la izquierda y 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 formar un árbol estándar de 2 a 3 dedos.
Esto se puede describir como: [1]
datos FingerTree a = Vacío | Soltero un | Profundo ( Dígito a ) ( FingerTree ( Nodo a )) ( Dígito a ) datos Nodo a = Nodo2 a a | Nodo3 a a a Los dígitos en los ejemplos mostrados son los nodos con letras. Cada lista está dividida por el prefijo o sufijo de cada nodo en el lomo. En un árbol transformado 2-3 parece que las listas de dígitos en el nivel superior pueden tener una longitud de dos o tres y los niveles inferiores solo tienen una longitud de uno o dos. Para que algunas aplicaciones de los á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 como esta: [1]
tipo Dígito a = Uno a | Dos a a | Tres a a a | cuatro a a a a Y así en la imagen, el nivel superior tiene elementos de tipo a , el siguiente tiene elementos de tipo Nodo a porque el nodo entre la columna y las hojas, y esto seguiría significando en general que el enésimo 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]
Los árboles de dedos también son eficientes deques . Ya sea que la estructura sea persistente o no, todas las operaciones toman Θ(1) tiempo amortizado. 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]
Los árboles de dedos se pueden utilizar para construir otros árboles. [4] Por ejemplo, se puede implementar una cola de prioridad etiquetando los nodos internos según la prioridad mínima de sus hijos en el árbol, o se puede implementar una lista/matriz indexada con un etiquetado de nodos según el recuento de hojas en sus niños. Otras aplicaciones son las secuencias de acceso aleatorio, que se describen a continuación, las secuencias ordenadas y los árboles de intervalos . [1]
Los árboles de dedos pueden proporcionar O(1) amortizado empujando, invirtiendo, haciendo estallar, O(log n) anexando y dividiendo; 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 más antiguas del árbol.
Los árboles de dedos pueden implementar eficientemente secuencias de acceso aleatorio. Esto debería admitir operaciones posicionales rápidas, incluido el acceso al enésimo elemento y dividir una secuencia en una posición determinada. Para hacer esto, anotamos el árbol de dedos con tamaños. [1]
nuevo tipo Tamaño = Tamaño { getSize :: N } derivando ( Eq , Ord ) instancia Tamaño monoide 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 Medido ( Elem a ) Tamaño donde || elemental || = Tamaño 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 en el tiempo de ejecución en Haskell porque en una biblioteca, los tipos Size y Elem estarían ocultos para el usuario con funciones contenedoras.
Con estos cambios, ahora se puede calcular la longitud de una secuencia en tiempo constante.
Los árboles de dedos fueron publicados por primera vez en 1977 por Leonidas J. Guibas , [5] y desde entonces se han perfeccionado periódicamente (por ejemplo, una versión que utiliza árboles AVL , [6] árboles de dedos no perezosos, aquí se muestran árboles más simples de 2 a 3 dedos, [1] B -Árboles y demás)
Desde entonces, los árboles de dedos se han utilizado en las bibliotecas principales 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 comprobadamente correcta . [8] También hay una implementación verificada en Isabelle (asistente de prueba) a partir de la cual se pueden generar programas en Haskell y otros lenguajes (funcionales). [9] Los árboles de dedos se pueden implementar con o sin evaluación diferida , [10] pero la pereza permite implementaciones más simples.