Pregunta
Dado un universo de enteros fijo con claves de 0 a U-1, implementa un árbol de van Emde Boas que soporte inserción, eliminación, pertenencia, mínimo, máximo, predecesor y sucesor. Explica la descomposición en high y low, la estructura summary, el manejo de clústeres vacíos y por qué las operaciones toman O(log log U) en lugar de O(log U).
Qué está evaluando el entrevistador
- Si comprendes que un árbol vEB asume un universo de enteros fijo y operaciones a nivel de bits, por lo que no reemplaza directamente a un árbol de comparación para objetos arbitrarios.
- Si puedes calcular índices de clúster y desplazamientos correctamente y mantener summary al tanto de los clústeres no vacíos.
- Si manejas el árbol vacío, el caso singleton, las claves límite, la eliminación del mínimo y la limpieza después de que un clúster queda vacío.
- Si puedes enunciar la complejidad teórica y el costo espacial de O(U), y luego indicar cuándo es preferible un y-fast trie, un arreglo ordenado o un árbol balanceado ordinario.
Respuesta modelo
Sea U una potencia de dos con ancho de bits w. Cada nodo vEB posee un subuniverso de tamaño u y divide una clave en un índice de clúster high y un desplazamiento low. En la definición recursiva habitual, ambas mitades usan aproximadamente la mitad de los bits, por lo que un nodo tiene cerca de sqrt(u) clústeres. Cada clúster es otro vEB de tamaño sqrt(u), y un summary de tamaño sqrt(u) registra qué clústeres no están vacíos.
El nodo también almacena min y max para que las operaciones comunes no hagan recursión hasta las hojas. Insertar el primer elemento establece ambos valores; una inserción posterior intercambia la clave menor en min e inserta el min anterior en su clúster. La eliminación debe manejar la remoción de min o max, encontrar el siguiente clúster no vacío a través de summary y eliminar un clúster de summary cuando quede vacío.
La recurrencia es T(u)=T(sqrt(u))+O(1). Las raíces cuadradas repetidas reducen a la mitad el exponente en cada nivel, por lo que la profundidad es O(log log U). Con un diseño ingenuo, los punteros a clústeres y los summaries a lo largo de los nodos recursivos utilizan un espacio de O(U). Los diseños dispersos reducen las constantes pero no eliminan la dependencia del universo por sí mismos.
Esquema de implementación
El pseudocódigo utiliza high, low y index para la descomposición y recombinación, omitiendo los grupos de memoria (memory pools) y la validación de argumentos.
high(x, bits) = x >> ceil(bits / 2)
low(x, bits) = x & ((1 << floor(bits / 2)) - 1)
index(h, l, bits) = (h << floor(bits / 2)) | l
insert(v, x):
if v.min is empty:
v.min = x; v.max = x; return
if x < v.min:
swap(x, v.min)
if v.bits > 1:
h = high(x, v.bits); l = low(x, v.bits)
if v.cluster[h].min is empty:
insert(v.summary, h)
insert(v.cluster[h], l)
if x > v.max:
v.max = x
successor(v, x):
if v.min is empty or x >= v.max: return empty
if v.bits == 1:
return v.max if v.max > x else empty
if x < v.min: return v.min
h = high(x, v.bits); l = low(x, v.bits)
c = v.cluster[h]
if c is not empty and l < c.max:
return index(h, successor(c, l), v.bits)
next_h = successor(v.summary, h)
if next_h is empty: return empty
return index(next_h, v.cluster[next_h].min, v.bits)Una implementación real de eliminación debe mantener las reglas simétricas de clústeres vacíos. Los nodos hoja pueden usar un pequeño mapa de bits o dos valores en lugar de asignar objetos recursivamente. Fija primero el ancho de bits y luego compara secuencias de operaciones aleatorias con un conjunto ordenado para que los resultados de predecesor y sucesor coincidan.
Errores comunes
- Tratar U como el número de elementos n y afirmar que cada operación es O(log log n). El parámetro es el tamaño del universo U.
- Ignorar el redondeo cuando U no es una potencia de dos, de modo que high, low e index ya no sean operaciones inversas.
- Implementar pertenencia y mínimo pero nunca remover los clústeres vacíos de summary tras una eliminación.
- Asumir que vEB siempre es más rápido que un árbol rojinegro ignorando el espacio O(U), la localidad de caché y la distribución real de las claves.
- Darle a summary la misma estructura recursiva sin especificar su límite de universo ni su representación vacía.
Compensaciones de complejidad
Para enteros del tamaño de una palabra de máquina, un universo conocido y cargas de trabajo centradas en predecesor y sucesor, O(log log U) resulta atractivo en teoría. Si U está cerca del rango de la palabra pero el conjunto es disperso, un diseño ingenuo desperdicia memoria. Los tries x-fast o y-fast hacen que el espacio dependa más de n, a costa de hashing, aleatoriedad o complejidad de implementación.
Un árbol balanceado ordinario proporciona operaciones en O(log n), espacio O(n) y una semántica de iteradores más simple. Un arreglo ordenado es adecuado para conjuntos estáticos y consultas por lotes. En una entrevista, elige en función del dominio de claves, la tasa de actualizaciones, el presupuesto de memoria y la mantenibilidad en lugar de reportar únicamente el límite asintótico más rápido.
Comienza con U igual a 2, 4 y 16, además de un universo que no sea potencia de dos, para probar la descomposición en los límites. Genera secuencias aleatorias de inserción, eliminación y consulta, y compara mínimo, máximo, pertenencia, predecesor y sucesor con el conjunto ordenado del lenguaje. Cubre también la inserción duplicada, la eliminación de una clave inexistente, la eliminación de la última clave y la eliminación repetida del mínimo o máximo.
Referencias
- MIT OpenCourseWare van Emde Boas Trees lecture: clústeres recursivos, summary y derivaciones de operaciones.
- Carnegie Mellon Graduate Algorithms Lecture 7: análisis de recurrencia O(log log U) y detalles de implementación.
- Springer’s predecessor-search survey: el trabajo original de van Emde Boas y el contexto del problema de predecesor.
Preguntas de seguimiento
¿Por qué es necesaria una estructura summary?
Cuando el clúster actual no tiene ningún elemento mayor, el árbol debe encontrar rápidamente el siguiente clúster no vacío. Summary convierte "cuáles clústeres no están vacíos" en otro problema de predecesor o sucesor en lugar de escanear los clústeres linealmente.
¿Por qué min y max pueden residir fuera de los clústeres?
Mantener min y max por separado hace que las operaciones de árbol vacío y singleton sean de tiempo constante y reduce la recursión. La inserción intercambia un valor menor en min; la eliminación encuentra un extremo de reemplazo a través de summary y restablece los invariantes.
¿Qué sucede si U no es una potencia de dos?
Redondea hacia arriba a un universo que sea potencia de dos y que cubra todas las claves válidas, y rechaza las claves fuera del rango original. Alternativamente, implementa límites de clúster redondeados, pero demuestra que high, low e index siguen siendo inversas y que la complejidad se mantiene.
¿Cómo se puede reducir el espacio O(U)?
Utiliza clústeres dispersos, x-fast tries o y-fast tries. Explica las colisiones de hash, la aleatoriedad, la semántica de iteradores y los factores constantes en lugar de comparar únicamente la notación Big-O.
¿Cuándo deberías evitar vEB?
Usa un árbol balanceado o un árbol B cuando el dominio de claves sea enorme y disperso, el universo no pueda fijarse, se requiera un comparador general o el comportamiento maduro de iteradores importe más que el límite teórico.