Árbol de boas de Van Emde | Conjunto 1 | Fundamentos y Construcción

Es muy recomendable comprender completamente Proto Van Emde Boas Tree .

Van Emde Boas Tree admite operaciones de búsqueda, sucesor, predecesor, inserción y eliminación en tiempo O (lglgN), que es más rápido que cualquiera de las estructuras de datos relacionadas, como cola de prioridad, árbol de búsqueda binaria, etc. Van Emde Boas Tree funciona con O (1) tiempo-complejidad para consulta mínima y máxima. Aquí N es el tamaño del universo sobre el que se define el árbol y lg es la base logarítmica 2.

Nota: El conjunto de claves de la estructura de datos de Van Emde Boas debe definirse en un rango de 0 a n (n es un número entero positivo de la forma 2 ^k ) y funciona cuando no se permiten claves duplicadas.

Abreviaturas:

1. VEB es una abreviatura del árbol Van Emde Boas.
2. VEB( ) es una abreviatura de VEB que contiene u número de claves.

Estructura del árbol de boas de Van Emde:

Van Emde Boas Tree es una estructura definida recursivamente.

1. u : Número de claves presentes en el Árbol VEB.
2. Mínimo: Contiene la clave mínima presente en el Árbol VEB.
3. Máximo: contiene la clave máxima presente en el árbol VEB.
4. Resumen: apunta al nuevo árbol VEB( ) que contiene una descripción general de las claves presentes en la array de clústeres.
5. Clústeres: una array de tamaño en la que cada lugar de la array apunta a un nuevo árbol VEB( ).

Vea la imagen a continuación para comprender los conceptos básicos de Van Emde Boas Tree, aunque no representa la estructura real de Van Emde Boas Tree:

Comprensión básica del árbol de boas de Van Emde:

1. Van Emde Boas Tree es una estructura definida recursivamente similar a Proto Van Emde Boas Tree.
2. En Van Emde Boas Tree, las consultas mínimas y máximas funcionan en tiempo O(1) ya que Van Emde Boas Tree almacena claves mínimas y máximas presentes en la estructura de árbol.
3. Ventajas de agregar atributos Máximo y Mínimo, que ayudan a disminuir la complejidad del tiempo:
   • Si alguno de los valores Mínimo y Máximo del Árbol VEB está vacío (NIL o -1 en el código), entonces no hay ningún elemento presente en el Árbol.
   • Si tanto Mínimo como Máximo son iguales, entonces solo hay un valor presente en la estructura.
   • Si ambos están presentes y son distintos, entonces dos o más elementos están presentes en el Árbol.
   • Podemos insertar y eliminar claves simplemente configurando valores máximos y mínimos según las condiciones en tiempo constante (O (1)), lo que ayuda a disminuir la string de llamadas recursivas: si solo hay una clave presente en el VEB, para eliminar esa clave simplemente configuramos min y max al valor cero. De manera similar, si no hay claves presentes, podemos insertar simplemente configurando min y max en la clave que queremos insertar. Estas son operaciones O(1).
   • En las consultas sucesor y antecesor, podemos tomar decisiones a partir de valores mínimos y máximos de VEB, lo que facilitará nuestro trabajo.

En Proto Van Emde Boas Tree, el tamaño del universo está restringido a ser del tipo 2 ^{2 k} , pero en Van Emde Boas Tree, permite que el tamaño del universo sea una potencia exacta de dos. Por lo tanto, debemos modificar las funciones auxiliares High(x), low(x), generate_index() utilizadas en Proto Van Emde Boas Tree como se muestra a continuación.

1. High(x): Devolverá floor( x/ceil( ) ), que es básicamente el índice del grupo en el que está presente la clave x.

   High(x) = floor(x/ceil())

2. Low(x): Devolverá x mod ceil( ), que es su posición en el clúster.

   Low(x) = x % ceil( )

3. generar_índice (a, b): devolverá la posición de la clave desde su posición en el clúster b y su índice de clúster a.

   generate_index(a, b) = a * ceil() + b

Construcción de Van Emde Boas Tree: La construcción de Van Emde Boas Tree es muy similar a Proto Van Emde Boas Tree. La diferencia aquí es que estamos permitiendo que el tamaño del universo sea cualquier potencia de dos, por lo que alto(), bajo(), generar_índice() serán diferentes.

Para construir, VEB vacío: El procedimiento es el mismo que Proto VEB, solo se agregarán dos cosas mínimo y máximo en cada VEB. Para representar que mínimo y máximo es nulo lo representaremos como -1.

Nota: En el caso base, solo necesitamos valores mínimos y máximos porque agregar un clúster de tamaño 2 será redundante después de agregar los valores mínimo y máximo.



A continuación se muestra la implementación:

// C++ implementation of the approach #include <bits/stdc++.h> using namespace std;    class Van_Emde_Boas {    public:     int universe_size;     int minimum;     int maximum;     Van_Emde_Boas* summary;     vector<Van_Emde_Boas*> clusters;        // Function to return cluster numbers     // in which key is present     int high(int x)     {         int div = ceil(sqrt(universe_size));         return x / div;     }        // Function to return position of x in cluster     int low(int x)     {         int mod = ceil(sqrt(universe_size));         return x % mod;     }        // Function to return the index from     // cluster number and position     int generate_index(int x, int y)     {         int ru = ceil(sqrt(universe_size));         return x * ru + y;     }        // Constructor     Van_Emde_Boas(int size)     {         universe_size = size;         minimum = -1;         maximum = -1;            // Base case         if (size <= 2) {             summary = nullptr;             clusters = vector<Van_Emde_Boas*>(0, nullptr);         }         else {             int no_clusters = ceil(sqrt(size));                // Assigning VEB(sqrt(u)) to summary             summary = new Van_Emde_Boas(no_clusters);                // Creating array of VEB Tree pointers of size sqrt(u)             clusters = vector<Van_Emde_Boas*>(no_clusters, nullptr);                // Assigning VEB(sqrt(u)) to all of its clusters             for (int i = 0; i < no_clusters; i++) {                 clusters[i] = new Van_Emde_Boas(ceil(sqrt(size)));             }         }     } };    // Driver code int main() {     // New Van_Emde_Boas tree with u = 16     Van_Emde_Boas* akp = new Van_Emde_Boas(4); }