B+ tree

Las claves de arriba siempre son copias de las claves de abajo

Como un tournament tree

Ejercicios del parcial

[11]. Tenemos una cola implementada usando listas doblemente enlazadas, cada “m” operaciones sobre la cola hacemos un backup de la misma, es decir copiamos la lista entera a una lista backup. a) Diseñe el struct que representa la lista. b) Indique y explique cómo calcula el costo amortizado de la operación dequeue()

T(n) = tiempo del algoritmo, en función de n

Costo amortizado = E(t) → esperanza

b) Costo total =

$$ 1 (n-(n/m)) + (n/m)n $$

porque n-n/m veces me cuesta 1 (no hago backup) y (n/m) me cuesta n (hago backup)

Costo amortizado = costo total / n =

$$ 1 - (1/m) + (n/m) $$

~ O (n)

[12] Queremos implementar una pila especial que soporte las siguientes operaciones: push(elem) // Agrega un elemento al stack. (idem a una pila común) pop() // Devuelve el último elemento y lo elimina del stack. (idem a una pila común) top() // Devuelve el elemento al tope de la pila, no lo remueve. (idem a una pila común) get_min() // Devuelve el mínimo elemento del stack. (no lo remueve) Todas (toooodas) las operaciones deben ser O(1). Indique qué estructura(s) de datos usaría y cómo implementaría push, pop, top y get_min usando dichas estructuras

Intentarlo y sino pedirle a los de la otra tutorial