Estructuras Persistentes

Mauro Jaskelioff

05/04/2016

Estructuras de Datos Funcionales vs. Imperativas

I Muchos de los algoritmos tradicionales estan pensados paraestructuras efımeras.

I En las estructuras efımeras, los cambios son destructivos.

I Las estructuras efımeras soportan una sola version y soncoherentes con un modelo secuencial.

I Las estructuras persistentes, soportan varias versiones y sonmas facilmente paralelizables.

I La flexibilidad de las estructuras persistentes tienen un costo:I Debemos adaptar las estructuras y algoritmos al modelo

persistente (de ser posible).I Hay ciertas cotas de las estructuras efımeras que no siempre se

van a poder alcanzar.

Persistencia y Sharing

I En un lenguaje funcional puro, todas las estructuras sonpersistentes.

I Las estructuras persistentes no se destruyen al hacer uncambio.

I Mas bien, se copian los datos y se modifica la copia.

I Los nodos que no cambian pueden ser compartidos por lasdiferentes versiones (sharing).

I Notar que el manejo automatico de la memoria (garbagecollection) es practicamente esencial.

Ejemplo: Listas simplemente enlazadas efımeras

I Concatenacion zs = xs ++ ys.

I Antes

I Despues

I La operacion destruye las listas xs e ys.

I La operacion zs = xs ++ ys es O(1).

Ejemplo: Listas simplemente enlazadas persistentes

I Concatenacion zs = xs ++ ys.

I Antes

I Despues

I Luego de la concatenacion tenemos las tres listas: xs, ys, y zs.I Hubo que copiar todos los nodos de xs.

I La operacion zs = xs ++ ys es O(|xs|).

Listas en Haskell

I Las listas en Haskell vienen predefinidas, pero bien podrıamosdefinirlas nosotros:

data List a = Nil| Cons a (List a)

I Preferimos usar la version predefinida con [ ] para la listavacıa, y (:) para la operacion cons.

I La concatenacion es

(++) :: [a ]→ [a ]→ [a ][ ] ++ ys = ys(x : xs) ++ ys = x : (xs ++ ys)

Ejercicio

I Considere la siguiente funcion que modifica un solo elementode la lista:

update :: [a ]→ Int → a→ [a ]update [ ] = [ ]update (x : xs) 0 x ′ = x ′ : xsupdate (x : xs) i x ′ = x : update xs (i − 1) x ′

I Dibujar la memoria luego de ejecutar

ys = update xs 2 7 y zs = update xs 0 8

donde

Arboles Binarios en Haskell

I Un arbol binario es un arbol en el que cada nodo tieneexactamente dos hijos.

I En Haskell representamos un arbol binario con la siguientedefinicion recursiva:

data Bin a = Hoja | Nodo (Bin a) a (Bin a)

I Definimos funciones sobre los arboles mediantepattern-matching y recursion:

member :: Eq a⇒ a→ Bin a→ Boolmember a Hoja = Falsemember a (Nodo l b r) = (a == b) ∨ member a l ∨ member a r

I ¿Cual es la complejidad de member?

Arboles Binarios de Busqueda

I Un arbol binario de busqueda es un arbol binario t tal queI o bien t es una hoja,I o bien t es un Nodo l a r , y se cumple que

I l y r son arboles binarios de busqueda, yI si y es una clave en algun nodo de l entonces y 6 a.I Si y es una clave en algun nodo de r entonces a< y .

254 Chapter 12 Binary Search Trees

5

2 5

3

8

7

5

(a)

5 8

7

3

2

(b)

Figure 12.1 Binary search trees. For any node x , the keys in the left subtree of x are at most key[x],and the keys in the right subtree of x are at least key[x]. Different binary search trees can representthe same set of values. The worst-case running time for most search-tree operations is proportionalto the height of the tree. (a) A binary search tree on 6 nodes with height 2. (b) A less efficient binarysearch tree with height 4 that contains the same keys.

contains fields left, right, and p that point to the nodes corresponding to its leftchild, its right child, and its parent, respectively. If a child or the parent is missing,the appropriate field contains the value NIL. The root node is the only node in thetree whose parent field is NIL.

The keys in a binary search tree are always stored in such a way as to satisfy thebinary-search-tree property:

Let x be a node in a binary search tree. If y is a node in the left subtreeof x , then key[y] ≤ key[x]. If y is a node in the right subtree of x , thenkey[x] ≤ key[y].

Thus, in Figure 12.1(a), the key of the root is 5, the keys 2, 3, and 5 in its leftsubtree are no larger than 5, and the keys 7 and 8 in its right subtree are no smallerthan 5. The same property holds for every node in the tree. For example, the key 3in Figure 12.1(a) is no smaller than the key 2 in its left subtree and no larger thanthe key 5 in its right subtree.

The binary-search-tree property allows us to print out all the keys in a binarysearch tree in sorted order by a simple recursive algorithm, called an inorder treewalk. This algorithm is so named because the key of the root of a subtree is printedbetween the values in its left subtree and those in its right subtree. (Similarly,a preorder tree walk prints the root before the values in either subtree, and apostorder tree walk prints the root after the values in its subtrees.) To use thefollowing procedure to print all the elements in a binary search tree T , we callINORDER-TREE-WALK(root[T ]).

Operaciones sobre BSTs

I Re-implementamos member para BSTs.

member :: Ord a⇒ a→ Bin a→ Boolmember a Hoja = Falsemember a (Nodo l b r) | a == b = True

| a < b = member a l| a > b = member a r

I Recorrido inorder en un BST

inorder :: Bin a→ [a ]inorder Hoja = [ ]inorder (Nodo l a r) = inorder l ++ [a ] ++ inorder r

Operaciones sobre BSTs

I El mınimo valor en un BST:

minimum :: Bin a→ aminimum (Nodo Hoja a r) = aminimum (Nodo l a r) = minimum l

I Ejercicio: implementar maximum.

I Ejercicio: implementar checkBST :: Bin a→ Bool .

I En member , minimum y maximum solo recorremos (a losumo) un camino entre la raız y una hoja.

TeoremaLas operaciones member , minimum y maximum son O(h), dondeh es la altura del arbol.

Insercion en BSTs

I Para insertar, recorremos el arbol hasta encontrar una hoja,que transformamos en un nuevo nodo.

insert :: Ord a⇒ a→ Bin a→ Bin ainsert a Hoja = Nodo Hoja a Hojainsert a (Nodo l b r) | a 6 b = Nodo (insert a l) b r

| otherwise = Nodo l b (insert a r)262 Chapter 12 Binary Search Trees

2 9

5

13 17

15 19

18

12

Figure 12.3 Inserting an item with key 13 into a binary search tree. Lightly shaded nodes indicatethe path from the root down to the position where the item is inserted. The dashed line indicates thelink in the tree that is added to insert the item.

Deletion

The procedure for deleting a given node z from a binary search tree takes as anargument a pointer to z. The procedure considers the three cases shown in Fig-ure 12.4. If z has no children, we modify its parent p[z] to replace z with NIL as itschild. If the node has only a single child, we “splice out” z by making a new linkbetween its child and its parent. Finally, if the node has two children, we spliceout z’s successor y, which has no left child (see Exercise 12.2-5) and replace z’skey and satellite data with y’s key and satellite data.

The code for TREE-DELETE organizes these three cases a little differently.

TREE-DELETE(T, z)1 if left[z] = NIL or right[z] = NIL

2 then y ← z3 else y ← TREE-SUCCESSOR(z)4 if left[y] "= NIL

5 then x ← left[y]6 else x ← right[y]7 if x "= NIL

8 then p[x] ← p[y]9 if p[y] = NIL

10 then root[T ] ← x11 else if y = left[p[y]]12 then left[p[y]] ← x13 else right[p[y]] ← x14 if y "= z15 then key[z] ← key[y]16 copy y’s satellite data into z17 return y

Sharing en BSTs

I Veamos que sucede en memoria al insertar un nodo a un BST.

ys=insert "e" xs−−−−−−−−−−→

Borrado en BSTs

delete :: Ord a⇒ a→ Bin a→ Bin adelete Hoja = Hojadelete z (Nodo l b r) | z < b = Nodo (delete z l) b rdelete z (Nodo l b r) | z > b = Nodo l b (delete z r)delete z (Nodo l b r) | z == b = ...

I Una vez encontrado el elemento tenemos que considerar trescasos.

Borrado en BSTs

a) El nodo tiene hojas como subarboles12.3 Insertion and deletion 263

3

10 13

12

5

18 23

20

16

15

6

7

z

(a)

3

10

12

5

18 23

20

16

15

6

7

3

10 13

12

5

18 23

20

16

15

6

7

z

(b)

3

10 13

12

5

18 23

20

15

6

7

3

10 13

12

5

18 23

20

16

15

6

7

z

(c)

y

3

10 13

12

5

18 23

20

16

156

7

z

y

3

10 13

12

6

18 23

20

16

15

7

Figure 12.4 Deleting a node z from a binary search tree. Which node is actually removed dependson how many children z has; this node is shown lightly shaded. (a) If z has no children, we justremove it. (b) If z has only one child, we splice out z. (c) If z has two children, we splice out itssuccessor y, which has at most one child, and then replace z’s key and satellite data with y’s key andsatellite data.

In lines 1–3, the algorithm determines a node y to splice out. The node y is eitherthe input node z (if z has at most 1 child) or the successor of z (if z has twochildren). Then, in lines 4–6, x is set to the non-NIL child of y, or to NIL if y hasno children. The node y is spliced out in lines 7–13 by modifying pointers in p[y]and x . Splicing out y is somewhat complicated by the need for proper handling ofthe boundary conditions, which occur when x = NIL or when y is the root. Finally,in lines 14–16, if the successor of z was the node spliced out, y’s key and satellitedata are moved to z, overwriting the previous key and satellite data. The node y isreturned in line 17 so that the calling procedure can recycle it via the free list. Theprocedure runs in O(h) time on a tree of height h.

delete z (Nodo Hoja b Hoja) | z == b = Hoja

Borrado en BSTs

b) El nodo tiene un solo subarbol con datos

12.3 Insertion and deletion 263

3

10 13

12

5

18 23

20

16

15

6

7

z

(a)

3

10

12

5

18 23

20

16

15

6

7

3

10 13

12

5

18 23

20

16

15

6

7

z

(b)

3

10 13

12

5

18 23

20

15

6

7

3

10 13

12

5

18 23

20

16

15

6

7

z

(c)

y

3

10 13

12

5

18 23

20

16

156

7

z

y

3

10 13

12

6

18 23

20

16

15

7

Figure 12.4 Deleting a node z from a binary search tree. Which node is actually removed dependson how many children z has; this node is shown lightly shaded. (a) If z has no children, we justremove it. (b) If z has only one child, we splice out z. (c) If z has two children, we splice out itssuccessor y, which has at most one child, and then replace z’s key and satellite data with y’s key andsatellite data.

In lines 1–3, the algorithm determines a node y to splice out. The node y is eitherthe input node z (if z has at most 1 child) or the successor of z (if z has twochildren). Then, in lines 4–6, x is set to the non-NIL child of y, or to NIL if y hasno children. The node y is spliced out in lines 7–13 by modifying pointers in p[y]and x . Splicing out y is somewhat complicated by the need for proper handling ofthe boundary conditions, which occur when x = NIL or when y is the root. Finally,in lines 14–16, if the successor of z was the node spliced out, y’s key and satellitedata are moved to z, overwriting the previous key and satellite data. The node y isreturned in line 17 so that the calling procedure can recycle it via the free list. Theprocedure runs in O(h) time on a tree of height h.

delete z (Nodo Hoja b r) | z == b = rdelete z (Nodo l b Hoja) | z == b = l

Borrado en BSTs

c) El nodo tiene dos subarboles con datos

12.3 Insertion and deletion 263

3

10 13

12

5

18 23

20

16

15

6

7

z

(a)

3

10

12

5

18 23

20

16

15

6

7

3

10 13

12

5

18 23

20

16

15

6

7

z

(b)

3

10 13

12

5

18 23

20

15

6

7

3

10 13

12

5

18 23

20

16

15

6

7

z

(c)

y

3

10 13

12

5

18 23

20

16

156

7

z

y

3

10 13

12

6

18 23

20

16

15

7

Figure 12.4 Deleting a node z from a binary search tree. Which node is actually removed dependson how many children z has; this node is shown lightly shaded. (a) If z has no children, we justremove it. (b) If z has only one child, we splice out z. (c) If z has two children, we splice out itssuccessor y, which has at most one child, and then replace z’s key and satellite data with y’s key andsatellite data.

In lines 1–3, the algorithm determines a node y to splice out. The node y is eitherthe input node z (if z has at most 1 child) or the successor of z (if z has twochildren). Then, in lines 4–6, x is set to the non-NIL child of y, or to NIL if y hasno children. The node y is spliced out in lines 7–13 by modifying pointers in p[y]and x . Splicing out y is somewhat complicated by the need for proper handling ofthe boundary conditions, which occur when x = NIL or when y is the root. Finally,in lines 14–16, if the successor of z was the node spliced out, y’s key and satellitedata are moved to z, overwriting the previous key and satellite data. The node y isreturned in line 17 so that the calling procedure can recycle it via the free list. Theprocedure runs in O(h) time on a tree of height h.

delete z (Nodo l b r) | z == b = let y = minimum rin Nodo l y (delete y r)

Arboles balanceados

I Las operaciones de busqueda, insercion y borrado son delorden de la altura del arbol.

I En el mejor caso son O(lg n),I pero en el peor caso pueden ser O(n)

I Por ejemplo, al insertar datos ordenados, el arbol degenera enuna lista.

I La solucion es mantener el arbol balanceadoI Ejemplos: AVL, Red-Black Trees.

Red-Black Trees

I Es un arbol binario de busqueda con nodo “coloreados” rojoso negros,

data Color = R | Bdata RBT a = E | T Color (RBT a) a (RBT a)

I y ademas se cumplen las siguiente invariantes:

INV1 Ningun nodo rojo tiene hijos rojos.INV2 Todos los caminos de la raız a una hoja tienen el mismo

numero de nodos negros (altura negra).

I En un RBT, el camino mas largo es a lo sumo el doble que elcamino mas corto.

I Esto significa que la altura esta siempre en O(lg n).

Operaciones sobre RBTs

I Implementamos member para RBTs.

memberRBT :: Ord a⇒ a→ RBT a→ BoolmemberRBT a E = FalsememberRBT a (T l b r) | a == b = True

| a < b = memberRBT a l| a > b = memberRBT a r

I El codigo es el mismo que para BSTsI Simplemente ignoramos el color.

Insercion en RBTs

insert :: Ord a⇒ a→ RBT a→ RBT ainsert x t = makeBlack (ins x t)

where ins x E = T R E x Eins x (T c l y r) | x < y = balance c (ins x l) y r

| x > y = balance c l y (ins x r)| otherwise = T c l y r

makeBlack E = EmakeBlack (T l x r) = T B l x r

I Notar que el nodo nuevo se inserta como un nodo rojo, por loque se mantiene la altura negra (INV2).

I Pero se puede violar INV1, por lo que hay que rebalancear.

I Luego de rebalanceo puede quedar una raız roja, por lo que secolorea de negro la raız.

Rebalanceo de RBTs

I Luego de una insertar el nuevo nodo rojo hay a lo sumo unaunica violacion de INV1 que ocurre cuando el padre es rojo.

I Por lo tanto la violacion siempre ocurre en un camino B-R-R.

I La funcion balance va arreglando y propagando hacia arribaesta violacion.

I La (unica) violacion, puede aparecer en cuatroconfiguraciones.

I En todos los casos la solucion es la misma: reescribir el nodocomo un padre rojo con dos hijos negros.

Configuraciones de violacion de invariante en RBTs

Implementacion de balance

I La implementacion de balance se puede hacer facilmentemediante pattern-matching.

balance :: Color → RBT a→ a→ RBT a→ RBT abalance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)balance c l a r = T c l a r

I Wbalance ∈ O(1). Como el arbol esta balanceadoWinsert ∈ O(lg n).

I La implementacion es simple.I Comparar con las implementaciones imperativas.I De yapa, esta implementacion es persistente.

Heaps

I Los heaps (o montıculos) son arboles que permiten un accesoeficiente al mınimo elemento.

I Mantienen la invariante de que todo nodo es menor a todoslos valores de sus hijos.

I Por lo tanto, el mınimo esta siempre en la raız.I Hay diferentes variantes de heaps:

I Heaps tradicionales, Leftist, Binomial, Splay, y Pairing Heaps.

I Un heap debe soportar eficientemente las operaciones

insert :: Ord a⇒ a→ Heap a→ Heap afindMin :: Ord a⇒ Heap a→ adeleteMin :: Ord a⇒ Heap a→ Heap a

I Algunas variantes tambien soportan eficientemente la unionde dos heaps: merge :: Ord a⇒ Heap a→ Heap a→ Heap a.

Leftist Heaps

I Variante de heap que es facil de implementar en formapersistente.

I El rango de un heap es la longitud de la espina derecha (elcamino hacia la derecha hasta un nodo vacıo.)

I Invariante Leftist: el rango de cualquier hijo izquierdo esmayor o igual que el de su hermano de la derecha.

I Consecuencias:I La espina derecha es el camino mas corto a un nodo vacıo.I La longitud de la espina derecha es a lo sumo lg(n + 1).I Los elementos de la espina derecha estan ordenados (como

consecuencia de la invariante de heap.)

Implementacion de leftist heaps

I Definimos el siguiente tipo de datos

type Rank = Intdata Heap a = E | N Rank a (Heap a) (Heap a)

I La operacion mas importante es merge:

merge :: Ord a⇒ Heap a→ Heap a→ Heap amerge h1 E = h1merge E h2 = h2merge h1@(N x a1 b1) h2@(N y a2 b2) =

if x 6 y then makeH x a1 (merge b1 h2)else makeH y a2 (merge h1 b2)

I Las espinas derechas se mezclan para seguir ordenadas ypreservar la invariante leftist.

I La funcion makeH se encarga de preservarla.

Implementacion de leftist heaps (cont.)

I Definimos la funcion que devuelve el rango

rank :: Heap a→ Rankrank E = 0rank (N r ) = r

I Definimos makeH

makeH x a b = if rank a > rank b then N (rank b + 1) x a belse N (rank a + 1) x b a

I Tanto Wrank como WmakeH estan en O(1).

I Como la espina derecha es a lo sumo logarıtmica,

Wmerge ∈ O(lg n).

Implementacion de leftist heaps (cont.)

I Una vez definido un merge eficiente, el resto de lasoperaciones son sencillas

insert :: Ord a⇒ a→ Heap a→ Heap ainsert x h = merge (N 1 x E E ) h

findMin :: Ord a⇒ Heap a→ afindMin (N x a b) = x

deleteMin :: Ord a⇒ Heap a→ Heap adeleteMin (N x a b) = merge a b

I Dado que Wmerge ∈ O(lg n), tenemos que Winsert y WdeleteMin

estan en O(lg n).

I WfindMin ∈ O(1).

Referencias

I Programming in Haskell. Graham Hutton, CUP 2007.

I Introduccion a la Programacion Funcional con Haskell.Richard Bird, Prentice Hall 1997.

I Purely Functional Data Structures. Chris Okasaki. CUP 1998.

I Introduction to Algorithms. Thomas H. Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein