Consulte primero todos los artículos anteriores sobre Proto Van Emde Boas Tree.
Procedimiento de consulta sucesor:
- Caso base: para Proto-VEB de tamaño 2, la única posibilidad es que la clave sea 0 y si la siguiente clave está presente, entonces es su sucesora o no hay sucesora. Entonces se aplica el mismo procedimiento.
- Recursividad:
- Primero, buscaremos en el clúster actual (es decir, el clúster en el que está presente la clave de consulta) si hay alguna clave mayor que la clave de consulta, entonces seremos el sucesor, por lo que la devolveremos.
- Si lo anterior no es el caso, llamaremos recursivamente al procedimiento sucesor sobre el resumen para encontrar el siguiente valor verdadero en resumen. Si no hay el siguiente valor verdadero en resumen, devolveremos -1 como una señal de que no hay una clave más grande presente.
- En la operación anterior, si encontramos el siguiente valor verdadero, encontraremos la clave mínima presente en ese grupo que será el sucesor de la clave de consulta.
Consulte la imagen a continuación para obtener una comprensión básica del funcionamiento de la consulta Sucesor:
El procedimiento para el predecesor es el mismo que el del sucesor con algunos cambios menores, debe intentar comprenderlo a partir de la descripción anterior para la consulta del sucesor. Vea la imagen a continuación para una comprensión básica:
A continuación se muestra la implementación:
C++
// 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)); } } // Function to return the minimum key from the tree int minimum(Proto_Van_Emde_Boas* helper) { // Base case chooses the least key // present in the cluster if (helper->universe_size == 2) { if (helper->clusters[0]) { return 0; } else if (helper->clusters[1]) { return 1; } // No keys present then return -1 return -1; } else { // Recursively find in summary for // first 1 present in Proto-VEB int minimum_cluster = minimum(helper->summary); int offset; // If no key is present in // the cluster then return -1 if (minimum_cluster == -1) { return -1; } else { // Recursively find the position of the key // in the minimum_cluster offset = minimum(helper->clusters[minimum_cluster]); // Returns overall index of minimum key return helper->generate_index(minimum_cluster, offset); } } } // Function to return the maximum key from the tree int maximum(Proto_Van_Emde_Boas* helper) { // Return the maximum key present in // the cluster if (helper->universe_size == 2) { if (helper->clusters[1]) { return 1; } else if (helper->clusters[0]) { return 0; } // Return -1 if no keys present in the // cluster return -1; } else { // Recursively find the last 1 present // in the summary int maximum_cluster = maximum(helper->summary); int offset; // If no key is present in // the cluster then return -1 if (maximum_cluster == -1) { return -1; } else { // Recursively find the position of the key // in the maximum_cluster offset = maximum(helper->clusters[maximum_cluster]); return helper->generate_index(maximum_cluster, offset); } } } // Function to return the successor of key in the tree int successor(Proto_Van_Emde_Boas* helper, int key) { // Base case, returns key greater than // our query key in the cluster if present // else returns -1 if (helper->universe_size == 2) { if (key == 0 && helper->clusters[1]) return 1; else return -1; } else { // Check if any key is greater than query key in the cluster int offset = successor(helper->clusters[helper->high(key)], helper->low(key)); // If it is present then return its index if (offset != -1) return helper->generate_index(helper->high(key), offset); else { // If no successor is present within the cluster then // go to the summary and find the next summary with // key present(1) named successor_cluster int successor_cluster = successor(helper->summary, helper->high(key)); // If no next 1 in the summary then return -1 if (successor_cluster == -1) return -1; else { // Find the minimum key in the successor_cluster offset = minimum(helper->clusters[successor_cluster]); // Generate its index and return return helper->generate_index(successor_cluster, offset); } } } } // Function to return the predecessor of key in the tree int predecessor(Proto_Van_Emde_Boas* helper, int key) { // Base case, find smaller key present in // the cluster // If present else return -1 if (helper->universe_size == 2) { if (key == 1 && helper->clusters[0]) return 0; else return -1; } else { // Check if any key is lower than query key in the cluster int offset = predecessor(helper->clusters[helper->high(key)], helper->low(key)); // If it is present then return its index if (offset != -1) return helper->generate_index(helper->high(key), offset); else { // If no predecessor is present within the cluster then // go to the summary and find the next summary with // key present(1) named predecessor_cluster int predecessor_cluster = predecessor(helper->summary, helper->high(key)); // If no next 1 in the summary then return -1 if (predecessor_cluster == -1) return -1; else { // Find the maximum key in the predecessor_cluster offset = maximum(helper->clusters[predecessor_cluster]); // Generate its index and return return helper->generate_index(predecessor_cluster, offset); } } } } // Function to delete a key from the tree void pveb_delete(Proto_Van_Emde_Boas*& helper, int key) { // Base case: If the key is present // then make it nullptr if (helper->universe_size == 2) { if (helper->clusters[key]) { delete helper->clusters[key]; helper->clusters[key] = nullptr; } } else { // Recursive delete to reach at the base case pveb_delete(helper->clusters[helper->high(key)], helper->low(key)); bool isanyinCluster = false; // Iterate over the cluster of keys to check whether // any other key is present within that cluster // If yes then we should not update summary to 0 // else update summary to 0 for (int i = helper->high(key) * helper->root(helper->universe_size); i < (helper->high(key) + 1) * helper->root(helper->universe_size); i++) { // If member is present then break the loop if (isMember(helper->clusters[helper->high(key)], i)) { isanyinCluster = true; break; } } // If no member is present then // update summary to zero if (isanyinCluster == false) { pveb_delete(helper->summary, helper->high(key)); } } } // Driver code int main() { Proto_Van_Emde_Boas* hello = new Proto_Van_Emde_Boas(16); cout << boolalpha; insert(hello, 2); insert(hello, 13); insert(hello, 3); cout << successor(hello, 3) << endl; cout << predecessor(hello, 13) << endl; }
Relación de recurrencia para consultas de sucesor y predecesor:
T(u) = T(u) = 2T()) + O(log2())
Complejidad de tiempo: O(log2(u)*log2(log2(u))) por consulta
Espacio auxiliar : O(N).
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