Download Pauta Auxiliar 3 - U

CC4102/CC40A/CC53A - Diseño y Análisis de Algoritmos
Auxiliar 3
Prof. Jérémy Barbay, Aux. Mauricio Quezada
13 de Abril, 2011
1
B-Árboles
1. Un B-Árbol T es un árbol con las siguientes propiedades:
• Cada nodo x posee
– n[x] el número de llaves en x
– las n[x] llaves, en orden no-decreciente: key1 [x] ≤ . . . ≤ keyn[x] [x]
– leaf [x] un valor booleano que indica si x es un nodo interno o no
• Cada nodo interno además posee n[x] + 1 punteros c1 [x], . . . , cn[x]+1 [x] a sus hijos. Las
hojas no tienen hijos, por lo que sus ci están indefinidos
• Las llaves keyi [x] separan los rangos de llaves almacenadas en cada subárbol. Si ki es
una llave almacenada en el subárbol con raíz ci [x], entonces
k1 ≤ key1 [x] ≤ k2 ≤ key2 [x] ≤ . . . ≤ keyn[x] [x] ≤ kn[x]+1
• Todas las hojas tienen la misma profundidad, la cual es la altura del árbol h
• El grado de T , t ≥ 2 es tal que
– cada nodo distinto de la raíz debe tener al menos t − 1 llaves.
– cada nodo puede tener a lo más 2t − 1 llaves
2. Pruebe que, si n ≥ 1, para cualquier B-Árbol de n llaves, altura h y grado t ≥ 2, h ≤ logt
n+1
2
3. De el algoritmo de inserción en un B-Árbol
2
van Emde Boas Trees
1. Nos gustaria crear una estructura de datos con las siguientes propiedades
• Mantener un conjunto dinámico S de tamaño n de un dominio U = {0, . . . , u−1}, |U| = u
• Que soporte las siguientes operaciones:
(a)
(b)
(c)
(d)
Insert (x ∈ U, x 6∈ S): Agregar x a S
Delete (x ∈ S): Eliminar x de S
Succ (x ∈ U): Encontrar el menor elemento z ∈ S tal que z > x
Pred (x ∈ U): Encontrar el mayor elemento z ∈ S tal que z < x
1
Describa un van Emde Boas Tree (o vEB Priority Queue)
2. Muestre que un van Emde Boas Tree soporta estas operaciones en tiempo O(lg lg u). ¿En qué
casos las operaciones funcionan en O(lg lg n)?
3. Pruebe que esta estructura utiliza espacio Θ(u)
4. (Propuesto) Determine un algoritmo Find (x ∈ U) que busca x en S en tiempo O(lg lg u)
3
3.1
Soluciones :EX:
P1.2
Si el árbol tiene altura h, la raíz contiene al menos una llave y todos los demás nodos contienen al
menos t − 1 llaves. Luego, hay al menos 2 nodos a profundidad 1, al menos 2t nodos a profunididad
2, al menos 2t2 nodos de profundidad 3,. . . Hasta la profundidad h donde hay al menos 2th−1
nodos, por lo tanto
n ≥ 1 + (t − 1)
h
X
2ti−1
i=1
th − 1 = 1 + 2(t − 1)
t−1
= 2th − 1
Obtenemos que th ≤ (n + 1)/2, y finalmente h ≤ logt
3.2
n+1
2
P1.3
• Al momento de insertar, verificar si la raíz está llena de llaves (n[root[T ]] == 2t − 1)
– Si es así, hacer un split de la raíz, aumentando la altura del árbol en 1
• Insertar el elemento donde corresponda:
– Descender en el árbol hasta llegar a un nodo hoja y verificar si el nodo está lleno
∗ Si es así, hacer un split del nodo recursivamente hasta preservar la condición del
árbol
∗ Insertar la llave en el nodo hoja correspondiente
3.3
P2.1
Considere al universo U como una estructura de tamaño
p u. En general, suponga que tenemos un
conjunto de elementos Sp
de tamaño |S|. Divídalo en |S| subestructuras (que a su vez
p también son
estructuras) de tamaño |S|. Cada subestructura es llamada sub[S][0], . . . , sub[S][ |S| − 1].
Como además necesitamos almacenar cuáles subestructuras están vacías,ppodemos, recursivamente, definir otra subestructura llamada summary[S]p
(o aux[S]) de tamaño |S|. Cada elemento
de summary corresponde a la vacuidad de una de las |S| subestructuras. Es decir, aux[S][i] = 0
si la subestructura i-ésima de la estructura S está vacía (1 si no).
Además, por cada estructura S, almacenaremos su valor mínimo (y/o máximo) en min(T ) (y/o
max(T )).
2
Para indizar cada elemento x en una estructura, definimos
j x k
high(x) = xh = p
|S|
p
low(x) = xl = x mod |S|
p
Es decir, xh representa en cuál de las
p |S| subestructuras se encuentra x, mientras que xl
representa en qué posición de una de las |S| subestructuras está x
3.4
P2.2
La idea está en hacer las operaciones con una sola llamada recursiva en las subestructuras de tamaño
√
n, luego
√
T (u) = T ( u) + O(1)
√
T 0 (lg u) = T 0 (lg u) + O(1)
1
T 0 (lg u) = T 0 ( lg u) + O(1)
2
0
T ∈ O(lg lg u)
3.5
P2.3
√
√
Como un árbol T tiene u vEB árboles, más un conjunto de u elementos de los bits de orden
superior y la información del min(T ) y max(T ), tenemos la siguiente relación de recurrencia:
√
√
S(u) = ( u + 1)S( u) + O(1)
Por inducción sobre u, probaremos que S(u) ∈ Θ(u):
• S(u) ≤ c1 u − c2 : Asuma por inducción que S(k) ≤ c1 k − c2 para todo k < u, luego
√
√
S(u) ≤ ( u + 1)(c1 u − c2 ) + O(1)
√
√
= c1 u + c1 u − c2 u − c2 + O(1)
√
= c1 u − c2 + u(c1 − c2 ) + O(1)
< c1 u − c2
eligiendo un c2 tal que c2 > c1
• S(u) ≥ cu: Asuma por inducción que S(k) ≥ ck para todo k < u, luego
√
√
S(u) ≥ ( u + 1)c u + O(1)
√
= cu + c u + O(1)
≥ cu
3