Lista de árbol concéntrico

Un árbol conc ^{[ 1 ] [ 2 ]} es una estructura de datos que almacena secuencias de elementos y proporciona operaciones de adición y anteposición amortizadas en tiempo O (1), operaciones de inserción y eliminación en tiempo O (log n ) y concatenación en tiempo O (log n ). Esta estructura de datos es particularmente viable para la programación paralela de tareas funcionales y de datos, y es relativamente simple de implementar en comparación con otras estructuras de datos con complejidad asintótica similar. ^{[ 1 ]} Los árboles conc fueron diseñados para mejorar la eficiencia de las operaciones paralelas de datos que no requieren un orden de iteración secuencial de izquierda a derecha, ^{[ 3 ]} y mejorar los factores constantes en estas operaciones al evitar copias innecesarias de los datos. ^{[ 2 ]} Ortogonalmente, se utilizan para agregar datos de manera eficiente en algoritmos paralelos de tareas de estilo funcional , como una implementación de la abstracción de datos de lista conc . ^{[ 4 ]} Conc-list es una contraparte de programación paralela de las listas cons funcionales , y fue introducida originalmente por el lenguaje Fortress .

La operación básica de un árbol conc es la concatenación. Los árboles conc funcionan con los siguientes tipos de datos básicos:

rasgo Conc [ T ] { def izquierda : Conc [ T ] def derecha : Conc [ T ] def nivel : Int def tamaño : Int }case class Empty [ T ] extends Conc [ T ] { def level = 0 def size = 0 }case class Single [ T ]( elem : T ) extends Conc [ T ] { def level = 0 def size = 1 }case class <> [ T ]( left : Conc [ T ], right : Conc [ T ]) extends Conc [ T ] { val level = 1 + math . max ( left . level , right . level ) val size = left . size + right . size }

El tipo <> representa nodos internos y se pronuncia conc , inspirado en :: (el tipo cons ) en listas funcionales, utilizado para programación secuencial.

La concatenación en tiempo O(log n) funciona asegurando que la diferencia de niveles (es decir, alturas) entre dos árboles hermanos cualesquiera sea uno o menos, de forma similar a los invariantes que se mantienen en los árboles AVL . Este invariante garantiza que la altura del árbol (longitud del camino más largo desde la raíz hasta alguna hoja) sea siempre logarítmica en el número de elementos del árbol. La concatenación se implementa de la siguiente manera:

def concat ( xs : Conc [ T ], ys : Conc [ T ]) { val diff = ys . level - xs . nivel si ( math.abs ( diff ) < = 1 ) nuevo < > ( xs , ys ) else if ( diff < -1 ) { if ( xs.left.level > = xs.right.level ) { val nr = concat ( xs.right , ys ) nuevo < > ( xs.left , nr ) } else { val nrr = concat ( xs.right.right , ys ) if ( nrr.level == xs.level - 3 ) { val nr = nuevo < > ( xs.right.left , nrr ) nuevo < > ( xs.left , nr ) } else { val nl = nuevo < > ( xs.left , xs.right.left ) nuevo < > ( nl , nrr ) } } } else​​​​​​​​​​​​​​​​​​​​​​​​​​​{ // caso simétrico } }

Las adiciones (o anteposiciones) amortizadas en tiempo O(1) se logran introduciendo un nuevo tipo de nodo interno llamado Append y usándolo para codificar una lista de árboles concéntricos de longitud logarítmica, cuya altura disminuye estrictamente. Cada nodo Append ap debe satisfacer los siguientes invariantes:

1. El nivel de ap.left.right es siempre estrictamente mayor que el nivel de ap.right .

2. El árbol ap.right nunca contiene ningún nodo Append (es decir, está en forma normalizada, compuesto únicamente por <> , Single y Empty ).

Con estas invariantes, la adición es isomorfa a la suma de números binarios : dos árboles adyacentes de la misma altura pueden enlazarse en tiempo constante, con un número logarítmico de operaciones de acarreo como máximo. Esto se ilustra en la siguiente figura, donde se añade un elemento a un árbol conc que corresponde al número binario 11:

Esta representación numérica binaria es similar a la de las listas de acceso aleatorio puramente funcionales de Okasaki, ^{[ 5 ]} con la diferencia de que las listas de acceso aleatorio requieren que todos los árboles sean árboles binarios completos , mientras que los árboles conc son más flexibles y solo requieren árboles balanceados. Estos invariantes más flexibles permiten que los árboles conc mantengan la concatenación en tiempo logarítmico, mientras que las listas de acceso aleatorio solo permiten la concatenación en O ( n ).

A continuación se muestra una implementación de un método de adición que tiene un tiempo de ejecución en el peor de los casos de O (log n ) y un tiempo amortizado de O (1):

case class Append [ T ]( left : Conc [ T ], right : Conc [ T ]) extends Conc [ T ] { val level = 1 + math . max ( left . level , right . level ) val size = left . size + right . size }private def append [ T ] ( xs : Append [ T ] , ys : Conc [ T ] ) = if ( xs.right.level > ys.level ) new Append ( xs , ys ) else { val zs = new < > ( xs.right , ys ) xs.left match { case ws @ Append ( _ , _ ) = > append ( ws , zs ) case ws = > if ( ws.level < = xs.level ) concat ( ws , zs ) else new Append ( ws , zs ) } } }​​​​​​​

El árbol concéntrico construido de esta manera nunca tiene más de O (log n ) nodos Append , y se puede convertir de nuevo a la forma normalizada (una que usa solo nodos <> , Single y Empty ) en un tiempo de O (log n ).

Una demostración detallada de estas operaciones se puede encontrar en recursos en línea, ^{[ 6 ] [ 7 ]} o en el artículo original de conc-tree. ^{[ 1 ]} Se demostró que estas operaciones básicas se pueden extender para admitir operaciones de deque en el peor de los casos O(1) , ^{[ 2 ]} manteniendo el límite de tiempo de concatenación O(log n), a costa de aumentar los factores constantes de todas las operaciones.