Árbol de Van Emde Boas

La operación FindNext(T, x) que busca el sucesor de un elemento x en un árbol vEB procede de la siguiente manera: Si x < T.min , la búsqueda ha finalizado y la respuesta es T.min . Si x ≥ T.max , el siguiente elemento no existe; devuelve M. En caso contrario,${\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor }$Si x < T.children[i].max , entonces el valor buscado está contenido en T.children[i] , por lo que la búsqueda procede recursivamente en T.children[i] . De lo contrario, buscamos el sucesor del valor i en T.aux . Esto nos da el índice j del primer subárbol que contiene un elemento mayor que x . El algoritmo devuelve entonces T.children[j].min . El elemento encontrado en el nivel de hijos debe combinarse con los bits más significativos para formar un elemento siguiente completo.

función FindNext(T, x) si x < T.min entonces devolver T.min si x ≥ T.max entonces // no hay siguiente elemento devolver M i = piso(x/${\displaystyle {\sqrt {M}}}$) lo = x mod${\displaystyle {\sqrt {M}}}$Si lo < T.children[i].max entonces devolver (${\displaystyle {\sqrt {M}}}$i) + FindNext(T.children[i], lo) j = FindNext(T.aux, i) devolver (${\displaystyle {\sqrt {M}}}$j) + T.children[j].min fin

Tenga en cuenta que, en cualquier caso, el algoritmo realiza${\displaystyle O(1)}$trabajo y luego posiblemente recursión en un subárbol sobre un universo de tamaño${\displaystyle M^{1/2}}$(un${\displaystyle m/2}$universo de bits). Esto proporciona una recurrencia para el tiempo de ejecución de${\displaystyle T(m)=T(m/2)+O(1)}$, que se resuelve en${\displaystyle O(\log m)=O(\log \log M)}$.

La llamada insert(T, x) que inserta un valor x en un árbol vEB T funciona de la siguiente manera:

1. Si T está vacío, entonces establecemos T.min = T.max = x y hemos terminado.
2. De lo contrario, si x < T.min , insertamos T.min en el subárbol i responsable de T.min y luego establecemos T.min = x . Si T.children[i] estaba previamente vacío, también insertamos i en T.aux.
3. De lo contrario, si x > T.max , insertamos x en el subárbol i responsable de x y luego establecemos T.max = x . Si T.children[i] estaba previamente vacío, también insertamos i en T.aux.
4. De lo contrario, T.min < x < T.max , por lo que insertamos x en el subárbol i responsable de x . Si T.children[i] estaba previamente vacío, entonces también insertamos i en T.aux .

En código:

función Insertar(T, x) si T.min == x || T.max == x entonces // x ya está insertado devolver si T.min > T.max entonces // T está vacío T.mín = T.máx = x; devolver si x < T.min entonces intercambio(x, T.min) si x > T.max entonces T.máx = x i = piso(x /${\displaystyle {\sqrt {M}}}$) lo = x mod${\displaystyle {\sqrt {M}}}$ Insertar(T.children[i], lo) Si T.children[i].min == T.children[i].max entonces Insertar(T.aux, i) fin

La clave de la eficiencia de este procedimiento es que insertar un elemento en un árbol vEB vacío requiere un tiempo O (1) . Por lo tanto, aunque el algoritmo a veces realiza dos llamadas recursivas, esto solo ocurre cuando la primera llamada recursiva fue en un subárbol vacío. Esto da el mismo tiempo de ejecución de recurrencia de ⁠${\displaystyle T(m)=T(m/2)+O(1)}$Como antes.

La eliminación de árboles vEB es la más compleja de las operaciones. La llamada Delete(T, x) que elimina un valor x de un árbol vEB T funciona de la siguiente manera:

1. Si T.min = T.max = x , entonces x es el único elemento almacenado en el árbol y establecemos T.min = M y T.max = −1 para indicar que el árbol está vacío.
2. De lo contrario, si x == T.min, entonces necesitamos encontrar el segundo valor más pequeño y en el árbol vEB, eliminarlo de su ubicación actual y establecer T.min=y . El segundo valor más pequeño y es T.children[T.aux.min].min , por lo que se puede encontrar en tiempo O (1) . Eliminamos y del subárbol que lo contiene.
3. Si x≠T.min y x≠T.max , entonces eliminamos x del subárbol T.children[i] que contiene x .
4. Si x == T.max, entonces necesitaremos encontrar el segundo valor más grande y en el árbol vEB y establecer T.max=y . Comenzamos eliminando x como en el caso anterior. Entonces el valor y es T.min o T.children[T.aux.max].max , por lo que se puede encontrar en tiempo O (1) .
5. En cualquiera de los casos anteriores, si eliminamos el último elemento x o y de cualquier subárbol T.children[i], también eliminamos i de T.aux .

En código:

función Eliminar(T, x) si T.min == T.max == x entonces T.min = M T.max = −1 Si x == T.min , entonces hi = T.aux.min *${\displaystyle {\sqrt {M}}}$ j = T.aux.min T.min = x = hi + T.children[j].min i = piso(x /${\displaystyle {\sqrt {M}}}$) lo = x mod${\displaystyle {\sqrt {M}}}$ Eliminar(T.children[i], lo) si T.children[i] está vacío entonces Eliminar(T.aux, i) si x == T.max entonces si T.aux está vacío entonces T.máx = T.mín de lo contrario hola = T.aux.max *${\displaystyle {\sqrt {M}}}$ j = T.aux.max T.max = hi + T.children[j].max fin

Nuevamente, la eficiencia de este procedimiento depende del hecho de que eliminar un elemento de un árbol vEB que contiene un solo elemento requiere un tiempo constante. En particular, la segunda llamada a Delete solo se ejecuta si x era el único elemento en T.children[i] antes de la eliminación.

La suposición de que log m es un número entero es innecesaria. Las operaciones${\displaystyle x{\sqrt {M}}}$y${\displaystyle x{\bmod {\sqrt {M}}}}$se puede reemplazar tomando solo los bits de orden superior ⌈ m /2⌉ y los bits de orden inferior ⌊ m /2⌋ de x , respectivamente. En cualquier máquina existente, esto es más eficiente que los cálculos de división o resto.

En implementaciones prácticas, especialmente en máquinas con instrucciones de desplazamiento de bits (shift-by-k) y búsqueda del primer cero , el rendimiento puede mejorarse aún más cambiando a una matriz de bits una vez que m sea igual al tamaño de la palabra (o un múltiplo pequeño de este). Dado que todas las operaciones en una sola palabra son de tiempo constante, esto no afecta el rendimiento asintótico, pero evita la mayor parte del almacenamiento de punteros y varias desreferenciaciones de punteros, logrando un ahorro práctico significativo en tiempo y espacio con este truco.

Una optimización de los árboles vEB consiste en descartar los subárboles vacíos. Esto hace que los árboles vEB sean bastante compactos cuando contienen muchos elementos, ya que no se crean subárboles hasta que sea necesario añadirles algo. Inicialmente, cada elemento añadido crea aproximadamente log( m ) nuevos árboles que contienen en total unos m /2 punteros. A medida que el árbol crece, se reutilizan cada vez más subárboles, especialmente los más grandes.

La implementación descrita anteriormente utiliza punteros y ocupa un espacio total de O ( M ) = O (2m ⁾ , proporcional al tamaño del universo de claves. Esto se puede ver de la siguiente manera. La recurrencia es${\displaystyle S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})}$. Se puede demostrar que S ( M ) = O ( M ) por inducción. ^{[ 4 ]}