Árbol de dedos

En informática , un árbol de dedos es una estructura de datos puramente funcional que se puede utilizar para implementar de forma 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 tiempo de concatenación y desdoblamiento 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 "sumarios" almacenados en los nodos internos se pueden utilizar para proporcionar la funcionalidad de estructuras de datos distintas a los árboles.

Descripción general

Árbol de dedos utilizado como una cola simple con operaciones de inserción y extracción O(1) amortizadas. Los números enteros del 1 al 21 se insertan a la derecha y se extraen desde la izquierda. Los bloques cuadrados representan valores, "Dígito" (azul cielo) puede tener de 1 a 4 hijos, "Nodo" (azul oscuro) puede tener de 2 a 3 hijos, el círculo blanco es para "Vacío", el nodo rojo representa el valor "Único" y los nodos verdes representan los valores "Profundos". Tenga en cuenta que para cada paso que damos hacia abajo en la columna vertebral, los valores únicos y los hijos de dígitos se anidan con un nuevo nivel de nodos.

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 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, una cola de prioridad, un árbol de búsqueda o una cola de búsqueda de prioridad, entre otras variedades de tipos de datos abstractos. ^[1]

Un dedo es un punto desde el que se puede acceder a una 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 hoja. Los dedos se agregan al árbol original para permitir un acceso constante a los dedos en el tiempo. En las imágenes que se muestran a continuación, los dedos son las líneas que salen de la columna vertebral hacia los nodos.

Un árbol de dedos se compone de diferentes capas que se pueden identificar 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 vertebral y las ramas que salen de los lados, en realidad hay dos nodos en la columna vertebral en cada nivel que se han emparejado para formar esta columna vertebral central. El prefijo está a la izquierda de la columna vertebral, mientras que el sufijo está a la derecha. Cada uno de esos nodos tiene un vínculo con el siguiente nivel de la columna vertebral hasta que llegan a la raíz. ^[2]

El primer nivel del árbol contiene sólo valores, los nodos de hoja del árbol, y tiene una profundidad de 0. El segundo nivel tiene una profundidad de 1. El tercero tiene una profundidad de 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 en el árbol va desde las hojas hasta la raíz del árbol, que es lo opuesto a la estructura de datos típica del árbol. Para obtener esta bonita e inusual estructura, tenemos que asegurarnos de que el árbol original tenga una profundidad uniforme. Para garantizar que la profundidad sea uniforme, al declarar el objeto nodo, debe parametrizarse por el tipo del hijo. Los nodos en la columna vertebral de profundidad 1 y superior apuntan a árboles, y con esta parametrización pueden representarse por los nodos anidados. ^[3]

Transformando un árbol en un árbol de dedos

Comenzaremos este proceso con un árbol equilibrado de 2 a 3. 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 poner dedos en los extremos derecho e izquierdo del árbol y transformarlo como una cremallera . Esto nos da ese acceso en tiempo amortizado constante a los extremos de una secuencia.

Para transformar, comience con el árbol equilibrado 2-3.

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 formar un árbol estándar de 2 a 3 dedos.

Esto se puede describir como: ^[1]

datos FingerTree a = Vacío | Único a | 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 que se muestran son los nodos con letras. Cada lista está dividida por el prefijo o sufijo de cada nodo en la columna vertebral. 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 funcionen 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 de la siguiente manera: ^[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 está entre la columna vertebral y las hojas, y esto continuaría significando 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 ). Mejor aún, un elemento a d lugares del extremo más cercano se almacena a una profundidad de Θ(log d) en el árbol. ^[1] $Nodo^{n}$

Reducciones

${\begin{aligned}\mathrm {instancia} &\ Reducir\ Nodo\ \mathrm {donde} &&\\&reductor\ (\prec )\ (Nodo2\ a\ b)\ z&=&\ a\ \prec (b\ \prec \ z)\\&reductor\ (\prec )\ (Nodo3\ a\ b\ c)\ z&=&\ a\ \prec (\ b\prec (c\ \prec \ z))\\\\&reducel\ (\succ )\ z\ (Nodo2\ b\ a)\ &=&\ (z\ \succ \ b)\ \succ \ a\\&reducel\ (\succ )\ z\ (Nodo3\ c\ b\ a)\ &=&\ ((z\ \succ \ c)\succ \ b)\succ \ a\\\end{aligned}}$

${\begin{aligned}\mathrm {instancia} &\ Reduce\ FingerTree\ \mathrm {donde} &&\\&reductor\ (\prec )\ (Vacío)\ z\ &=&\ z\\&reductor\ (\prec )\ (Única\ x)\ z&=&\ x\ \prec \ z\\&reductor\ (\prec )\ (Profundo\ pr\ m\ sf)\ z&=&\ pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\&\ \ \ \ donde\\&\ \ \ \ \ \ \ (\prec ')\ =reductor\ (\prec )\\&\ \ \ \ \ \ \ (\prec '')\ =reductor\ (reductor\ (\prec ))\\\\&reducel\ (\succ )\ z\ (Vacío)\ &=&\ z\\&reducel\ (\succ )\ z\ (Sencillo\ \ x)\ &=&\ z\ \succ \ x\\&reducel\ (\succ )\ z\ (Profundo\ \ pr\ m\ sf)\ &=&\ ((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\\&\ \ \ \ donde\\&\ \ \ \ \ \ \ (\succ ')\ =reducel\ (\succ )\\&\ \ \ \ \ \ \ \ (\succ '')\ =reducel\ (reducel\ (\succ ))\\\end{aligned}}$

Operaciones deque

Los árboles de dedos también crean deques eficientes . 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]

Solicitud

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 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 sus hijos. 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 inserción, inversión, extracción, adición y división O(1) amortizadas; y pueden adaptarse para ser secuencias indexadas u ordenadas. Y como todas las estructuras de datos funcionales, es inherentemente persistente ; es decir, las versiones anteriores del árbol siempre se conservan.

Secuencias de acceso aleatorio

Los árboles de dedos pueden implementar secuencias de acceso aleatorio de manera eficiente. Esto debería permitir operaciones posicionales rápidas, incluido el acceso al elemento n -ésimo y la división de una secuencia en una posición determinada. Para ello, anotamos el árbol de dedos con tamaños. ^[1]

newtype Tamaño = Tamaño { 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 corresponde a los números naturales. El nuevo tipo es necesario porque es portador de diferentes monoides. Aún se necesita otro tipo nuevo para los elementos de la secuencia que se muestra a continuación.

nuevo tipo Elem a = Elem { getElem :: a } nuevo tipo Seq a = Seq ( FingerTree Size ( Elem a ))        
        

instancia Medido ( Elem a ) Tamaño donde || Elem || = Tamaño 1

Estas líneas de código muestran que la instancia funciona como un caso base para medir los tamaños y que los elementos son de tamaño uno. El uso de newtype no causa una penalización en 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.

Primera publicación

Los árboles de dedos fueron publicados por primera vez en 1977 por Leonidas J. Guibas , ^[5] y periódicamente refinados desde entonces (por ejemplo, una versión que utiliza árboles AVL , ^[6] árboles de dedos no perezosos, árboles de 2-3 dedos más simples que se muestran aquí, ^[1] árboles B, etc.)

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 de Coq probada y 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 perezosa , ^[10] pero la pereza permite implementaciones más simples.

Véase también

Referencias

^ abcdefghi Hinze, Ralf; Paterson, Ross (2006), "Árboles de dedos: una estructura de datos simple y de propósito general" (PDF) , Journal of Functional Programming , 16 (2): 197–217, doi :10.1017/S0956796805005769, S2CID 6881581.
^ ab Gibiansky, Andrew. "Árboles con 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 - The ultimate data structure?". abhiroop.github.io . Archivado desde el original el 2017-10-26 . Consultado el 2017-10-26 .
^ Guibas, LJ ; McCreight, EM; Plass, MF; Roberts, JR (1977), "Una nueva representación para listas lineales", Acta de la conferencia del noveno simposio anual de la ACM sobre teoría de la computación , págs. 49-60.
^ Tsakalidis, AK (1985), "Árboles AVL para búsqueda localizada", Información y 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
^ Nordhoff, Benedikt; Körner, Stefan; Lammich, Pedro. "Árboles de dedos". Archivo de Pruebas Formales . Consultado el 26 de noviembre de 2021 .
^ Kaplan, H.; Tarjan, RE (1995), "Listas persistentes con concatenación mediante desaceleración recursiva", Actas del vigésimo séptimo simposio anual de la ACM sobre la 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 de Hinze/Paterson en Java
Ejemplo de árboles de dedos Hinze/Paterson en C#
Monoides y árboles de dedos en Haskell
Biblioteca de árboles de dedos para Clojure
Árbol de los dedos en Scalaz

[:0-1] Hinze, Ralf; Paterson, Ross (2006), "Árboles de dedos: una estructura de datos simple y de propósito general" (PDF) , Journal of Functional Programming , 16 (2): 197–217, doi :10.1017/S0956796805005769, S2CID 6881581.

[:1-2] Gibiansky, Andrew. "Árboles con dedos - Andrew Gibiansky". andrew.gibiansky.com . Consultado el 26 de octubre de 2017 .

[3] "Árboles de dedos bien hechos (espero)". Buenas matemáticas, malas matemáticas . Consultado el 26 de octubre de 2017 .

[4] Sarkar, Abhiroop. "Finger Tree - The ultimate data structure?". abhiroop.github.io . Archivado desde el original el 2017-10-26 . Consultado el 2017-10-26 .

[5] Guibas, LJ ; McCreight, EM; Plass, MF; Roberts, JR (1977), "Una nueva representación para listas lineales", Acta de la conferencia del noveno simposio anual de la ACM sobre teoría de la computación , págs. 49-60.

[6] Tsakalidis, AK (1985), "Árboles AVL para búsqueda localizada", Información y Control , 67 (1–3): 173–194, doi : 10.1016/S0019-9958(85)80034-6.

[7] Noticias semanales de Caml

[8] Matthieu Sozeau :: Árboles de dedos dependientes en Coq

[9] Nordhoff, Benedikt; Körner, Stefan; Lammich, Pedro. "Árboles de dedos". Archivo de Pruebas Formales . Consultado el 26 de noviembre de 2021 .

[10] Kaplan, H.; Tarjan, RE (1995), "Listas persistentes con concatenación mediante desaceleración recursiva", Actas del vigésimo séptimo simposio anual de la ACM sobre la teoría de la computación , págs. 93-102.