b'\n_START_ARTICLE_\nEstructuras de datos persistentes\n_START_PARAGRAPH_\nEn computaci\xc3\xb3n, una estructura de datos persistente es una estructura de datos que siempre preserva sus versiones anteriores, despu\xc3\xa9s de ser modificada. Este tipo de estructura son objetos inmutables, ya que sus operaciones no modifican la estructura actual, sino que crean una nueva estructura modificada. (Este art\xc3\xadculo utiliza el t\xc3\xa9rmino Persistencia de datos para referirse a datos obsoletos; no confundir con el significado de almacenamiento de informaci\xc3\xb3n en un medio persistente, como un disco duro.)_NEWLINE_Una estructura es parcialmente persistente si se puede acceder a todas sus versiones, pero solo se puede modificar la \xc3\xbaltima.  Una estructura es completamente persistente si todas las versiones pueden ser accedidas y modificadas. Si tambi\xc3\xa9n existe la posibilidad de mezclar dos versiones de la estructura, se dice que esta es confluently persistent.  Las estructuras que no son persistentes son llamadas transitorias.\xe2\x80\x8b_NEWLINE_Este tipo de estructuras son comunes particularmente en programaci\xc3\xb3n l\xc3\xb3gica y programaci\xc3\xb3n funcional. En un lenguaje de programaci\xc3\xb3n puramente funcional todos los datos son inmutables, as\xc3\xad que todas las estructuras son completamente persistentes.\xe2\x80\x8b_NEWLINE_La persistencia se puede lograr simplemente copiando las estructuras completas, pero esto puede ser muy ineficiente en cuanto a c\xc3\xa1lculos del CPU y consumo de memoria RAM, debido a que generalmente solo se hacen peque\xc3\xb1os cambios. Lo mejor ser\xc3\xada explotar la similitud que existe entre la nueva versi\xc3\xb3n y sus versiones anteriores, y compartir parte de su estructura con ellas, como por ejemplo, utilizar algunos sub-\xc3\xa1rboles que no se modificaron para el caso de las estructuras formadas por \xc3\xa1rboles. De todas formas, debido a que r\xc3\xa1pidamente se vuelve no factible determinar cuantas versiones anteriores comparten partes en com\xc3\xban con la estructura actual y a que a veces se hace necesario descartar versiones anteriores, es necesario contar con recolector de basura.\n_START_SECTION_\nParcialmente Persistente\n_START_PARAGRAPH_\nEn el modelo de persistencia parcial, se puede acceder a la informaci\xc3\xb3n de versiones anteriores pero solo se puede modificar la \xc3\xbaltima versi\xc3\xb3n. Esto implica un orden total entre las versiones._NEWLINE_Tres m\xc3\xa9todos para \xc3\x81rbol binario de b\xc3\xbasqueda auto-balanceable:\n_START_SECTION_\nNodo Grueso\n_START_PARAGRAPH_\nEl m\xc3\xa9todo del nodo gordo consiste en almacenar todos los cambios hechos a propiedades de un nodo de la estructura, en el mismo nodo, si borrar los valores anteriores de sus propiedades. Esto requiere que los nodos puedan ser arbitrariamente \xe2\x80\x9cgruesos\xe2\x80\x9d. Cada nodo debe permitir guardar cualquier cantidad de campos adicionales. Cada campo adicional tiene una propiedad, un valor y una marca de tiempo que indica la versi\xc3\xb3n en la cual dicha propiedad tom\xc3\xb3 ese valor. Adem\xc3\xa1s cada nodo tiene una marca de tiempo que indica la versi\xc3\xb3n en la que dicho nodo fue creado. El motivo de que los nodos tengan marcas de tiempo es para asegurar que cada nodo tenga un solo valor para cada propiedad para cada versi\xc3\xb3n. Para poder recorrer la estructura, cada campo original tiene cero como marca de tiempo.\n_START_SECTION_\nComplejidad de Nodo Grueso\n_START_PARAGRAPH_\nUtilizando el m\xc3\xa9todo Nodo Grueso, se requiere O(1) de espacio por cada modificaci\xc3\xb3n: solo almacenar el nuevo valor. Cada modificaci\xc3\xb3n necesita O(1) de tiempo adicional para almacenar el cambio al final de la lista de cambios. Esto es una cota Costo amortizado, asumiendo que guardamos la lista de modificaci\xc3\xb3n en un vector (inform\xc3\xa1tica) que puede crecer. Para el acceso, debemos encontrar la versi\xc3\xb3n correcta en cada nodo mientras recorremos la estructura. Si hacemos m modificaciones, entonces cada operaci\xc3\xb3n de acceso tiene un factor O(log m) que resulta de buscar la modificaci\xc3\xb3n m\xc3\xa1s cercana en el historial de modificaciones.\n_START_SECTION_\nCopia de Camino\n_START_PARAGRAPH_\nCopia de camino consiste en copiar todos los nodos en el camino desde la ra\xc3\xadz del \xc3\xa1rbol hasta el nodo que vamos actualizar, insertar o borrar. Despu\xc3\xa9s hay que actualizar en cascada el cambio: todos los nodos que apuntaban a un nodo viejo deben apuntar a el nodo nuevo. Estas modificaciones provocan m\xc3\xa1s cambios en cascada, y as\xc3\xad sucesivamente, hasta que lleguemos a la ra\xc3\xadz. Se mantiene adem\xc3\xa1s una lista de ra\xc3\xadces indexadas por marcas de tiempo, de forma tal, que la estructura que tiene como ra\xc3\xadz t es exactamente la t-\xc3\xa9sima versi\xc3\xb3n.\n_START_SECTION_\nComplejidad de Copia de Camino\n_START_PARAGRAPH_\nEl costo de modificaci\xc3\xb3n temporal y espacial est\xc3\xa1 dado por el tama\xc3\xb1o de la estructura, debido a que una modificaci\xc3\xb3n puede afectarla completamente. En el caso de los \xc3\xa1rboles que tengan altura logar\xc3\xadtmica, se puede garantizar que el costo de modificaci\xc3\xb3n ser\xc3\xa1 O(log n) donde n es la cantidad de nodos del \xc3\xa1rbol, ya que solo cambian los que est\xc3\xa1n en el camino de la ra\xc3\xadz al nodo que se va a modificar.\n_START_SECTION_\nUna combinaci\xc3\xb3n\n_START_PARAGRAPH_\nSleator, Tarjan et al. proponen una combinaci\xc3\xb3n que aprovecha las ventajas de los nodos gruesos y de copiar el camino, obteniendo O(1) de costo adicional temporal y O(1) de costo adicional espacial para el acceso y la modificaci\xc3\xb3n._NEWLINE_En cada nodo se guarda una campo de modificaci\xc3\xb3n. Este campo puede almacenar una modificaci\xc3\xb3n de una propiedad del nodo o una modificaci\xc3\xb3n de uno de sus punteros, con una marca de tiempo que indica la versi\xc3\xb3n en la que se hizo la modificaci\xc3\xb3n. Inicialmente el campo de modificaci\xc3\xb3n de cada nodo est\xc3\xa1 vac\xc3\xado._NEWLINE_Cada vez que se accede a un nodo, se chequea el campo de modificaci\xc3\xb3n, y se compara la marca de tiempo con la versi\xc3\xb3n que se est\xc3\xa1 accediendo. Si el campo de modificaci\xc3\xb3n est\xc3\xa1 vac\xc3\xado, o la versi\xc3\xb3n de acceso es anterior a la marca de tiempo, entonces se ignora el campo de modificaci\xc3\xb3n. De lo contrario, si la versi\xc3\xb3n de acceso es posterior a la marca de tiempo, entonces se utiliza el valor que est\xc3\xa1 en el campo de modificaci\xc3\xb3n. Por ejemplo, si el campo de modificaci\xc3\xb3n tiene un nuevo puntero al hijo izquierdo (en el caso de un \xc3\xa1rbol binario), entonces se considera que este es el hijo izquierdo del nodo._NEWLINE_Para modificar un nodo (se asume que una modificaci\xc3\xb3n cambia un puntero o una propiedad de un nodo), si el campo de modificaci\xc3\xb3n del nodo est\xc3\xa1 vac\xc3\xado, lo llenamos con la modificaci\xc3\xb3n. De lo contrario, se crea una copia del nodo, pero utilizando solo los \xc3\xbaltimos valores, o sea sobrescribiendo la propiedad o puntero que se encuentra en el campo de modificaci\xc3\xb3n, y se hace la modificaci\xc3\xb3n directamente en el nuevo nodo, sin utilizar el campo de modificaci\xc3\xb3n, o sea, se sobrescribe la propiedad o el puntero directamente y el campo de modificaci\xc3\xb3n se queda vac\xc3\xado. Finalmente se propaga en cascada este cambio al padre del nodo, de la misma forma que se hace en copia del camino. Si el nodo no tiene padre, o sea, es la ra\xc3\xadz, y hay que copiarla, se a\xc3\xb1ade en una lista ordenada de ra\xc3\xadces._NEWLINE_Con este algoritmo, dado una versi\xc3\xb3n t, a lo sumo un campo de modificaci\xc3\xb3n existe con tiempo t. Por lo tanto, una modificaci\xc3\xb3n en el tiempo t, divide el \xc3\xa1rbol en tres partes: una parte contiene los datos antes del tiempo t, otra contiene los datos despu\xc3\xa9s del tiempo t, y la otra parte no fue afectada por la modificaci\xc3\xb3n.\n_START_SECTION_\nComplejidad de la combinaci\xc3\xb3n\n_START_PARAGRAPH_\nEl costo temporal y espacial requiere un an\xc3\xa1lisis amortizado. Una modificaci\xc3\xb3n toma costo espacial amortizado O(1), y costo temporal amortizado O(1). Para demostrarlo, se utiliza una funci\xc3\xb3n potencial \xcf\x95, donde \xcf\x95(T) es el n\xc3\xbamero de nodos llenos vivos en T. Los nodos vivos de T, son aquellos que son accesibles desde la ra\xc3\xadz actual, en el tiempo actual, o sea, despu\xc3\xa9s de la \xc3\xbaltima modificaci\xc3\xb3n. Los nodos llenos vivos, son los nodos vivos que tienen algo en su campo de modificaci\xc3\xb3n._NEWLINE_Cada modificaci\xc3\xb3n conlleva cierto n\xc3\xbamero de copias, digamos k, seguidas de 1 cambio en un campo de modificaci\xc3\xb3n. Cada una de las k copias tiene O(1) costo temporal y espacial, pero disminuye la funci\xc3\xb3n potencial en uno, debido a que el nodo que se copia debe estar lleno y vivo, por lo tanto contribuye a la funci\xc3\xb3n potencial, pero al copiarlo y cambiar el puntero de su padre dejar\xc3\xa1 de estar vivo, y la copia tiene el campo de modificaci\xc3\xb3n vac\xc3\xado as\xc3\xad que no est\xc3\xa1 llena, por lo tanto se reemplaz\xc3\xb3 un nodo lleno vivo, por uno que no est\xc3\xa1 lleno). El \xc3\xbaltimo paso llena un campo de modificaci\xc3\xb3n, esto tiene O(1) de costo temporal y aumenta \xcf\x95 en uno._NEWLINE_En resumen, el cambio en \xcf\x95 es \xce\x94\xcf\x95 = 1 \xe2\x88\x92 k, por lo tanto el costo espacial total es O(k +\xce\x94\xcf\x95) = O(1) y el costo temporal total es O(k +\xce\x94\xcf\x95 +1) = O(1).\n_START_SECTION_\nEjemplos de estructuras persistentes\n_START_PARAGRAPH_\nProbablemente la estructura persistente m\xc3\xa1s sencilla sea la lista enlazada, una simple lista de objetos, donde cada uno tiene una referencia el siguiente. Para que sea persistente cuando se modifica un nodo, la nueva versi\xc3\xb3n puede compartir con la anterior, los nodos que estaban despu\xc3\xa9s de \xc3\xa9l, o sea, la cola._NEWLINE_Muchas de las estructuras basadas en enlaces, como red-black trees,\xe2\x80\x8b stacks,\xe2\x80\x8b y treaps,\xe2\x80\x8b  pueden ser adaptadas f\xc3\xa1cilmente para crear una versi\xc3\xb3n persistente de la misma. Otras necesitan demasiado esfuerzo por ejemplo un min-deque.\n_START_SECTION_\nListas enlazadas\n_START_PARAGRAPH_\nLa lista enlazada es las estructuras m\xc3\xa1s utilizada en los lenguajes de programaci\xc3\xb3n funcionales._NEWLINE_Considere las dos listas:_NEWLINE_xs = [0, 1, 2]_NEWLINE_ys = [3, 4, 5]_NEWLINE_Estas deben ser representadas en memoria de la siguiente forma:_NEWLINE_donde un c\xc3\xadrculo significa un nodo de la lista, y las flechas referencias hacia el nodo que apuntan_NEWLINE_Concatenar las dos listas:_NEWLINE_zs = xs ++ ys_NEWLINE_resulta en la siguiente estructura en memoria:_NEWLINE_Notar que los nodos en la lista xs han sido copieados, pero los nodos en ys son compartidos. Como resultado, las listas originales (xs y ys) persisten y no han sido modificadas._NEWLINE_La raz\xc3\xb3n de la copia es que el \xc3\xbaltimo nodo en xs no puede ser modificado para apuntar el inicio de ys, porque eso cambiar\xc3\xada el valor de xs.\n_START_SECTION_\n\xc3\x81rboles\n_START_PARAGRAPH_\nConsideremos un \xc3\xa1rbol binario utilizado para buscar de forma r\xc3\xa1pida,_NEWLINE_donde cada nodo tiene la invariante recursiva de que los valores de los nodos a la izquierda son menores que su valor, y los de la derecha son mayores._NEWLINE_Por ejemplo:_NEWLINE_xs = [a, b, c, d, f, g, h]_NEWLINE_puede ser representado por el siguiente \xc3\xa1rbol binario:_NEWLINE_Despu\xc3\xa9s de ejecutar de insertar "e" en xs obtenemos lo siguiente:_NEWLINE_Notemos que el \xc3\xa1rbol original xs persiste y muchos nodos son compartidos entre ambas versiones. Este tipo de persistencia es muy dif\xc3\xadcil de manejar sin recolector de basura, para que libere la memoria de los nodos que ya no pueden ser accedidos, es por esto que esta caracter\xc3\xadstica es muy com\xc3\xban en la programaci\xc3\xb3n funcional'