Consulte los artículos anteriores sobre Proto Van Emde Boas Tree para comprenderlos correctamente.
Procedimiento para Insertar:
- Caso base: si el tamaño de Proto-VEB es 2, entonces asigne verdadero a la array de bits (aquí, en el código, asignamos Proto-VEB (1) debido a la estructura recursiva, por lo que ahora no es nullptr y actúa como verdadero) en la posición de la llave.
- Hasta que lleguemos al caso base, llamaremos recursivamente a insertar en el clúster que contiene la clave y ahora también usaremos la clave como la posición de la clave en ese clúster en lugar de la clave de consulta.
Ejemplo: insertemos 2 en Proto-VEB (u = 4): desde el procedimiento de inserción, comenzaremos la recursividad ya que el tamaño de Proto-VEB es mayor que 2, por lo que recursivamente llamamos insert() en el grupo número 2/ 
que es 1 y es la posición 2% , que es 0, por lo que la llamada recursiva se insertará (cluster [1], 0).
Y el clúster[1] es Proto-VEB de tamaño 2, llegamos al caso base, por lo que asignará verdadero en (en el código Proto-VEB(1) como verdadero) clúster[1] 0º lugar.
Asimismo, haremos el mismo procedimiento sobre el resumen.
Vea la imagen a continuación para mayor claridad:
siga las instrucciones escritas cerca de los cuadros de arriba a abajo.
Procedimiento isMember: este procedimiento devuelve un valor booleano según si la clave está presente en Proto-VEB o no. Es bastante trivial entender ver la imagen de arriba para tener una idea al respecto.
- Caso base: si el tamaño de Proto-VEB es 2, verifique si el valor de la array de bits en la posición clave es verdadero o no y devuelva el valor en consecuencia. (En el código, verificamos si el puntero en la posición clave es nullptr o no).
- Recursión: hacemos una llamada recursiva sobre el clúster que contiene la clave hasta llegar al caso base.
Implementación del algoritmo anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
class Proto_Van_Emde_Boas {
public:
// Total number of keys
int universe_size;
// Summary
Proto_Van_Emde_Boas* summary;
// Clusters array of Proto-VEB pointers
vector<Proto_Van_Emde_Boas*> clusters;
int root(int u)
{
return int(sqrt(u));
}
// Function to return cluster numbers
// in which key is present
int high(int x)
{
return x / root(universe_size);
}
// Function to return position of x in cluster
int low(int x)
{
return x % root(universe_size);
}
// Function to return the index from
// cluster number and position
int generate_index(int cluster, int position)
{
return cluster * root(universe_size) + position;
}
// Constructor
Proto_Van_Emde_Boas(int size)
{
universe_size = size;
// Base case
if (size <= 2) {
// Set summary to nullptr as there is no
// more summary for size 2
summary = nullptr;
// Vector of two pointers
// nullptr in starting
clusters = vector<Proto_Van_Emde_Boas*>(size, nullptr);
}
else {
// Assigning Proto-VEB(sqrt(u)) to summary
summary = new Proto_Van_Emde_Boas(root(size));
// Creating array of Proto-VEB Tree pointers of size sqrt(u)
// first all nullptrs are going to assign
clusters = vector<Proto_Van_Emde_Boas*>(root(size), nullptr);
// Assigning Proto-VEB(sqrt(u)) to all its clusters
for (int i = 0; i < root(size); i++) {
clusters[i] = new Proto_Van_Emde_Boas(root(size));
}
}
}
};
// Function that returns true if the
// key is present in the tree
bool isMember(Proto_Van_Emde_Boas* helper, int key)
{
// If key is greater then universe_size then
// returns false
if (key >= helper->universe_size)
return false;
// If we reach at base case
// the just return whether
// pointer is nullptr then false
// else return true
if (helper->universe_size == 2) {
return helper->clusters[key];
}
else {
// Recursively go deep into the
// level of Proto-VEB tree using its
// cluster index and its position
return isMember(helper->clusters[helper->high(key)],
helper->low(key));
}
}
// Function to insert a key in the tree
void insert(Proto_Van_Emde_Boas*& helper, int key)
{
// If we reach at base case
// then assign Proto-VEB(1) in place
// of nullptr
if (helper->universe_size == 2) {
helper->clusters[key] = new Proto_Van_Emde_Boas(1);
}
else {
// Recursively using index of cluster and its
// position in cluster
insert(helper->clusters[helper->high(key)],
helper->low(key));
// Also do the same recursion in summary VEB
insert(helper->summary, helper->high(key));
}
}
// Driver code
int main()
{
Proto_Van_Emde_Boas* hello = new Proto_Van_Emde_Boas(4);
cout << isMember(hello, 3);
insert(hello, 3);
cout << isMember(hello, 3);
}
Insertar recurrencia de complejidad de algoritmo:
T(u) = 2T() + O(1)
Este algoritmo se ejecuta en el peor de los casos O(log2(u)).
Recurrencia de la complejidad del algoritmo isMember:
T(u) = T(
Este algoritmo se ejecuta en el peor de los casos O(log2(log2(u))).
Publicación traducida automáticamente
Artículo escrito por Aakash_Panchal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA