Se recomienda encarecidamente leer primero los artículos anteriores sobre Van Emde Boas Tree.
Procedimiento para el sucesor:
- Caso base: si el tamaño del árbol es 2, entonces si la clave de consulta es 0 y la clave – 1 está presente en el árbol, devuelva 1, ya que será el sucesor. De lo contrario, devuelve nulo.
- Si la clave es menor que el mínimo, podemos decir fácilmente que el mínimo será el sucesor de la clave de consulta.
- Caso recursivo:
- Primero buscamos el sucesor en el clúster en el que está presente la clave.
- Si encontramos algún sucesor en el clúster, genere su índice y devuélvalo.
- De lo contrario, busque el siguiente clúster, con al menos una clave presente, en resumen, y devuelva el índice mínimo de ese clúster.
Consulte la consulta para el sucesor de 0 en la siguiente imagen:
La siguiente imagen representa el sucesor de 1 consulta sobre el árbol VEB que contiene las claves 1 y 2:
Procedimiento para el predecesor:
- Caso base: si el tamaño del árbol es 2, entonces si la clave de consulta es 1 y la clave 0 está presente en el árbol, devuelva 0, ya que será el predecesor. De lo contrario, devuelve nulo.
- Si la clave es mayor que el máximo, podemos decir fácilmente que el máximo será el predecesor de la clave de consulta.
- Caso recursivo:
- Primero buscamos el predecesor en el clúster en el que está presente la clave.
- Si encontramos algún predecesor en el clúster, genere su índice y devuélvalo.
- De lo contrario, busque el clúster anterior, con al menos una clave presente, en resumen. Si hay algún clúster presente, devuelva el índice del máximo de ese clúster.
- Si no hay un clúster con esa propiedad, vea si debido a la propagación perezosa, el mínimo del árbol (en el que está presente el clúster) es menor que la clave, si es así, devuelva el mínimo; de lo contrario, devuelva nulo.
La imagen de abajo representa el predecesor de la consulta de la tecla 2:
C++
#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 its clusters
for (int i = 0; i < no_clusters; i++) {
clusters[i] = new Van_Emde_Boas(ceil(sqrt(size)));
}
}
}
};
// Function to return the minimum value
// from the tree if it exists
int VEB_minimum(Van_Emde_Boas* helper)
{
return (helper->minimum == -1 ? -1 : helper->minimum);
}
// Function to return the maximum value
// from the tree if it exists
int VEB_maximum(Van_Emde_Boas* helper)
{
return (helper->maximum == -1 ? -1 : helper->maximum);
}
// Function to insert a key in the tree
void insert(Van_Emde_Boas* helper, int key)
{
// If no key is present in the tree
// then set both minimum and maximum
// to the key (Read the previous article
// for more understanding about it)
if (helper->minimum == -1) {
helper->minimum = key;
helper->maximum = key;
}
else {
if (key < helper->minimum) {
// If the key is less than the current minimum
// then swap it with the current minimum
// because this minimum is actually
// minimum of one of the internal cluster
// so as we go deeper into the Van Emde Boas
// we need to take that minimum to its real position
// This concept is similar to "Lazy Propagation"
swap(helper->minimum, key);
}
// Not base case then...
if (helper->universe_size > 2) {
// If no key is present in the cluster then insert key into
// both cluster and summary
if (VEB_minimum(helper->clusters[helper->high(key)]) == -1) {
insert(helper->summary, helper->high(key));
// Sets the minimum and maximum of cluster to the key
// as no other keys are present we will stop at this level
// we are not going deeper into the structure like
// Lazy Propagation
helper->clusters[helper->high(key)]->minimum = helper->low(key);
helper->clusters[helper->high(key)]->maximum = helper->low(key);
}
else {
// If there are other elements in the tree then recursively
// go deeper into the structure to set attributes accordingly
insert(helper->clusters[helper->high(key)], helper->low(key));
}
}
// Sets the key as maximum it is greater than current maximum
if (key > helper->maximum) {
helper->maximum = key;
}
}
}
// Function that returns true if the
// key is present in the tree
bool isMember(Van_Emde_Boas* helper, int key)
{
// If universe_size is less than the key
// then we can not search the key so returns
// false
if (helper->universe_size < key) {
return false;
}
// If at any point of our traversal
// of the tree if the key is the minimum
// or the maximum of the subtree, then
// the key is present so returns true
if (helper->minimum == key || helper->maximum == key) {
return true;
}
else {
// If after attending above condition,
// if the size of the tree is 2 then
// the present key must be
// maximum or minimum of the tree if it
// is not then it returns false because key
// can not be present in the sub tree
if (helper->universe_size == 2) {
return false;
}
else {
// Recursive call over the cluster
// in which the key can be present
// and also pass the new position of the key
// i.e., low(key)
return isMember(helper->clusters[helper->high(key)],
helper->low(key));
}
}
}
// Function to find the successor of the given key
int VEB_successor(Van_Emde_Boas* helper, int key)
{
// Base case: If key is 0 and its successor
// is present then return 1 else return null
if (helper->universe_size == 2) {
if (key == 0 && helper->maximum == 1) {
return 1;
}
else {
return -1;
}
}
// If key is less then minimum then return minimum
// because it will be successor of the key
else if (helper->minimum != -1 && key < helper->minimum) {
return helper->minimum;
}
else {
// Find successor inside the cluster of the key
// First find the maximum in the cluster
int max_incluster = VEB_maximum(helper->clusters[helper->high(key)]);
int offset{ 0 }, succ_cluster{ 0 };
// If there is any key( maximum!=-1 ) present in the cluster then find
// the successor inside of the cluster
if (max_incluster != -1 && helper->low(key) < max_incluster) {
offset = VEB_successor(helper->clusters[helper->high(key)],
helper->low(key));
return helper->generate_index(helper->high(key), offset);
}
// Otherwise look for the next cluster with at least one key present
else {
succ_cluster = VEB_successor(helper->summary, helper->high(key));
// If there is no cluster with any key present
// in summary then return null
if (succ_cluster == -1) {
return -1;
}
// Find minimum in successor cluster which will
// be the successor of the key
else {
offset = VEB_minimum(helper->clusters[succ_cluster]);
return helper->generate_index(succ_cluster, offset);
}
}
}
}
// Function to find the predecessor of the given key
int VEB_predecessor(Van_Emde_Boas* helper, int key)
{
// Base case: If the key is 1 and it's predecessor
// is present then return 0 else return null
if (helper->universe_size == 2) {
if (key == 1 && helper->minimum == 0) {
return 0;
}
else
return -1;
}
// If the key is greater than maximum of the tree then
// return key as it will be the predecessor of the key
else if (helper->maximum != -1 && key > helper->maximum) {
return helper->maximum;
}
else {
// Find predecessor in the cluster of the key
// First find minimum in the key to check whether any key
// is present in the cluster
int min_incluster = VEB_minimum(helper->clusters[helper->high(key)]);
int offset{ 0 }, pred_cluster{ 0 };
// If any key is present in the cluster then find predecessor in
// the cluster
if (min_incluster != -1 && helper->low(key) > min_incluster) {
offset = VEB_predecessor(helper->clusters[helper->high(key)],
helper->low(key));
return helper->generate_index(helper->high(key), offset);
}
// Otherwise look for predecessor in the summary which
// returns the index of predecessor cluster with any key present
else {
pred_cluster = VEB_predecessor(helper->summary, helper->high(key));
// If no predecessor cluster then...
if (pred_cluster == -1) {
// Special case which is due to lazy propagation
if (helper->minimum != -1 && key > helper->minimum) {
return helper->minimum;
}
else
return -1;
}
// Otherwise find maximum in the predecessor cluster
else {
offset = VEB_maximum(helper->clusters[pred_cluster]);
return helper->generate_index(pred_cluster, offset);
}
}
}
}
// Driver code
int main()
{
Van_Emde_Boas* veb = new Van_Emde_Boas(8);
// Inserting Keys
insert(veb, 2);
insert(veb, 3);
insert(veb, 4);
insert(veb, 6);
// Queries
cout << VEB_successor(veb, 2) << endl;
cout << VEB_predecessor(veb, 6) << endl;
cout << VEB_successor(veb, 4) << endl;
return 0;
}
Producción:
3 4 6
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