Van Emde Boas Tree | Set 4 | Deletion - Never Open Always Closed

It is highly recommended to read the previous articles on Van Emde Boas Tree first.

Procedure for Delete:
Here we are assuming that the key is already present in the tree.

First we check if only one key is present, then assign the maximum and minimum of the tree to null value to delete the key.
Base Case: If the universe size of the tree is two then, after the above condition of only one key is present is false, exactly two key is present in the tree (after the above condition turns out to false), So delete the query key by assigning maximum and minimum of the tree to another key present in the tree.
Recursive Case:
- If the key is the minimum of the tree then find the next minimum of the tree and assign it as the minimum of the tree and delete query key.
- Now the query key is not present in the tree. We will have to change the rest of the structure in the tree to eliminate the key completely:
  1. If the minimum of the cluster of the query key is null then we will delete it from summary as well. Also, if the key is the maximum of the tree then we will find new maximum and assign it as the maximum of the tree.
  2. Otherwise, if the key is maximum of the tree then find the new maximum and assign it as the maximum of the tree.

Below is the series of images representing ‘delete key-0 query’ over the VEB Tree with 0, 1, 2 keys are present:

Step 1: As 0 is the minimum of the tree, it will satisfy the first condition of the else part of the algorithm.

First, it finds the next maximum which is 1 and set it as a minimum.

Step 2: Now it will delete key 1 from the cluster[0].

Step 3: Next condition, cluster[0] has no key, is true, so it will clear the key from the summary as well.

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 than 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);
            }
        }
    }
}
 
// Function to delete a key from the tree
// assuming that the key is present
void VEB_delete(Van_Emde_Boas* helper, int key)
{
 
    // If only one key is present, it means
    // that it is the key we want to delete
    // Same condition as key == max && key == min
    if (helper->maximum == helper->minimum) {
 
        helper->minimum = -1;
        helper->maximum = -1;
    }
 
    // Base case: If the above condition is not true
    // i.e. the tree has more than two keys
    // and if its size is two than a tree has exactly two
    // keys. We simply delete it by assigning it to another
    // present key value
    else if (helper->universe_size == 2) {
 
        if (key == 0) {
            helper->minimum = 1;
        }
        else {
            helper->minimum = 0;
        }
        helper->maximum = helper->minimum;
    }
    else {
 
        // As we are doing something similar to lazy
        // propagation we will basically find next bigger
        // key and assign it as minimum
        if (key == helper->minimum) {
 
            int first_cluster
                = VEB_minimum(helper->summary);
 
            key = helper->generate_index(
                first_cluster,
                VEB_minimum(
                    helper->clusters[first_cluster]));
 
            helper->minimum = key;
        }
 
        // Now we delete the key
        VEB_delete(helper->clusters[helper->high(key)],
                   helper->low(key));
 
        // After deleting the key, rest of the improvements
 
        // If the minimum in the cluster of the key is -1
        // then we have to delete it from the summary to
        // eliminate the key completely
        if (VEB_minimum(helper->clusters[helper->high(key)])
            == -1) {
 
            VEB_delete(helper->summary, helper->high(key));
 
            // After the above condition, if the key
            // is maximum of the tree then...
            if (key == helper->maximum) {
                int max_insummary
                    = VEB_maximum(helper->summary);
 
                // If the max value of the summary is null
                // then only one key is present so
                // assign min. to max.
                if (max_insummary == -1) {
 
                    helper->maximum = helper->minimum;
                }
                else {
 
                    // Assign global maximum of the tree,
                    // after deleting our query-key
                    helper->maximum
                        = helper->generate_index(
                            max_insummary,
                            VEB_maximum(
                                helper->clusters
                                    [max_insummary]));
                }
            }
        }
 
        // Simply find the new maximum key and
        // set the maximum of the tree
        // to the new maximum
        else if (key == helper->maximum) {
 
            helper->maximum = helper->generate_index(
                helper->high(key),
                VEB_maximum(
                    helper->clusters[helper->high(key)]));
        }
    }
}
 
// Driver code
int main()
{
    Van_Emde_Boas* end = new Van_Emde_Boas(8);
 
    // Inserting Keys
    insert(end, 1);
    insert(end, 0);
    insert(end, 2);
    insert(end, 4);
 
    // Before deletion
    cout << isMember(end, 2) << endl;
    cout << VEB_predecessor(end, 4) << " "
         << VEB_successor(end, 1) << endl;
 
    // Delete only if the key is present
    if (isMember(end, 2))
        VEB_delete(end, 2);
 
    // After deletion
    cout << isMember(end, 2) << endl;
    cout << VEB_predecessor(end, 4) << " "
         << VEB_successor(end, 1) << endl;
}

Java

import java.util.*;
 
class Van_Emde_Boas {
 
    public int universe_size;
    public int minimum;
    public int maximum;
    public Van_Emde_Boas summary;
    public ArrayList<Van_Emde_Boas> clusters;
 
    public Van_Emde_Boas(int size)
    {
        universe_size = size;
        minimum = -1;
        maximum = -1;
 
        // Base case
        if (size <= 2) {
            summary = null;
            clusters = new ArrayList<Van_Emde_Boas>(0);
        }
        else {
            int no_clusters
                = (int)Math.ceil(Math.sqrt(size));
            summary = new Van_Emde_Boas(no_clusters);
 
            clusters
                = new ArrayList<Van_Emde_Boas>(no_clusters);
 
            for (int i = 0; i < no_clusters; i++) {
                clusters.add(new Van_Emde_Boas(
                    (int)Math.ceil(Math.sqrt(size))));
            }
        }
    }
 
    // Function to return cluster numbers
    // in which key is present
    public int high(int x)
    {
        int div = (int)Math.ceil(Math.sqrt(universe_size));
        return x / div;
    }
    // Function to return position of x in cluster
    public int low(int x)
    {
        int mod = (int)Math.ceil(Math.sqrt(universe_size));
        return x % mod;
    }
 
    // Function to return position of x in cluster
    public int generate_index(int x, int y)
    {
        int ru = (int)Math.ceil(Math.sqrt(universe_size));
        return x * ru + y;
    }
}
 
class Main {
 
    // Function to return the minimum value
    // from the tree if it exists
    public static 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
    public static int VEB_maximum(Van_Emde_Boas helper)
    {
        return (helper.maximum == -1 ? -1 : helper.maximum);
    }
 
    // Function to insert a key in the tree
    static 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 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
            if (key < helper.minimum) {
                int temp = helper.minimum;
                helper.minimum = key;
                key = temp;
            }
 
            // 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.get(
                        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
                    helper.clusters.get(helper.high(key))
                        .minimum
                        = helper.low(key);
                    helper.clusters.get(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.get(
                               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
    public static boolean isMember(Van_Emde_Boas helper,
                                   int key)
    {
        if (helper.universe_size < key) {
            return false;
        }
 
        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 (helper.universe_size == 2) {
                return false;
            }
            else {
                return isMember(
                    helper.clusters.get(helper.high(key)),
                    helper.low(key));
            }
        }
    }
 
    // Function to find the successor of the given key
    public static int VEB_successor(Van_Emde_Boas helper,
                                    int key)
    {
        if (helper.universe_size == 2) {
            if (key == 0 && helper.maximum == 1) {
                return 1;
            }
            else {
                return -1;
            }
        }
        // If key is less than 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.get(helper.high(key)));
            int offset = 0;
            int 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.get(helper.high(key)),
                    helper.low(key));
                return helper.generate_index(
                    helper.high(key), offset);
            }
            else {
                succ_cluster = VEB_successor(
                    helper.summary, helper.high(key));
                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.get(succ_cluster));
                    return helper.generate_index(
                        succ_cluster, offset);
                }
            }
        }
    }
 
    // Function to find the predecessor of the given key
    public static int VEB_predecessor(Van_Emde_Boas helper,
                                      int key)
    {
        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.get(helper.high(key)));
            int offset = 0;
            int 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.get(helper.high(key)),
                    helper.low(key));
                return helper.generate_index(
                    helper.high(key), offset);
            }
            else {
                // returns the index of predecessor cluster
                // with any key present
                pred_cluster = VEB_predecessor(
                    helper.summary, helper.high(key));
                // If no predecessor cluster then...
                if (pred_cluster == -1) {
                    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.get(pred_cluster));
                    return helper.generate_index(
                        pred_cluster, offset);
                }
            }
        }
    }
    public static void VEB_delete(Van_Emde_Boas helper,
                                  int key)
    {
        // If only one key is present, it means
        // that it is the key we want to delete
        if (helper.maximum == helper.minimum) {
 
            helper.minimum = -1;
            helper.maximum = -1;
        }
        // Base case: If the above condition is not true
        // i.e. the tree has more than two keys
        // and if its size is two than a tree has exactly
        // two keys.
        else if (helper.universe_size == 2) {
 
            if (key == 0) {
                helper.minimum = 1;
            }
            else {
                helper.minimum = 0;
            }
            helper.maximum = helper.minimum;
        }
        else {
            // As we are doing something similar to lazy
            // propagation we will basically find next
            // bigger key and assign it as minimum
            if (key == helper.minimum) {
 
                int first_cluster
                    = VEB_minimum(helper.summary);
 
                key = helper.generate_index(
                    first_cluster,
                    VEB_minimum(helper.clusters.get(
                        first_cluster)));
 
                helper.minimum = key;
            }
 
            // Now we delete the key
            VEB_delete(
                helper.clusters.get(helper.high(key)),
                helper.low(key));
 
            // After deleting the key, rest of the
            // improvements
 
            // If the minimum in the cluster of the key is
            // -1 then we have to delete it from the summary
            // to eliminate the key completely
            if (VEB_minimum(
                    helper.clusters.get(helper.high(key)))
                == -1) {
 
                VEB_delete(helper.summary,
                           helper.high(key));
 
                // After the above condition, if the key
                // is maximum of the tree then.
                if (key == helper.maximum) {
                    int max_insummary
                        = VEB_maximum(helper.summary);
 
                    if (max_insummary == -1) {
 
                        helper.maximum = helper.minimum;
                    }
                    else {
                        // Assign global maximum of the
                        // tree, after deleting our
                        // query-key
                        helper.maximum
                            = helper.generate_index(
                                max_insummary,
                                VEB_maximum(
                                    helper.clusters.get(
                                        max_insummary)));
                    }
                }
            }
 
            // Simply find the new maximum key and
            // set the maximum of the tree
            // to the new maximum
            else if (key == helper.maximum) {
                helper.maximum = helper.generate_index(
                    helper.high(key),
                    VEB_maximum(helper.clusters.get(
                        helper.high(key))));
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        Van_Emde_Boas end = new Van_Emde_Boas(8);
 
        insert(end, 1);
        insert(end, 0);
        insert(end, 2);
        insert(end, 4);
 
        // Before deletion
        System.out.println(isMember(end, 2));
        System.out.println(VEB_predecessor(end, 4));
        System.out.println(VEB_successor(end, 1));
 
        // Delete only if the key is present
        if (isMember(end, 2))
            VEB_delete(end, 2);
 
        // After deletion
        System.out.println(isMember(end, 2));
        System.out.println(VEB_predecessor(end, 4));
        System.out.println(VEB_successor(end, 1));
    }
}

Python3

import math
 
 
class Van_Emde_Boas:
    # Constructor
    def __init__(self, size):
        self.universe_size = size
        self.minimum = None
        self.maximum = None
        if size <= 2:
            self.summary = None
            self.clusters = [None] * 0
        else:
            no_clusters = math.ceil(math.sqrt(size))
            self.summary = Van_Emde_Boas(no_clusters)
            self.clusters = [Van_Emde_Boas(
                math.ceil(math.sqrt(size))) for i in range(no_clusters)]
 
    #  Function to return cluster numbers
    # in which key is present
    def high(self, x):
        div = math.ceil(math.sqrt(self.universe_size))
        return x // div
 
    def low(self, x):
        mod = math.ceil(math.sqrt(self.universe_size))
        return x % mod
 
    # Function to return the index from
   # cluster number and position
    def generate_index(self, x, y):
        ru = math.ceil(math.sqrt(self.universe_size))
        return (x or 0) * ru + (y or 0)
 
# Function to return the minimum value
#  from the tree if it exists
 
 
def VEB_minimum(helper):
    return helper.minimum
 
# Function to return the maximum value
# from the tree if it exists
 
 
def VEB_maximum(helper):
    return helper.maximum
 
# Function to check member
 
 
def isMember(helper, key):
    if helper.universe_size < key:
        return False
    if helper.minimum == key or helper.maximum == key:
        return True
    if helper.universe_size == 2:
        return False
    return isMember(helper.clusters[helper.high(key)], helper.low(key))
 
 
#  Function to insert a key in the tree
def insert(helper, 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 is None:
        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"
            helper.minimum, key = key, helper.minimum
        if helper.universe_size > 2:
            if VEB_minimum(helper.clusters[helper.high(key)]) is None:
                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))
        if key > helper.maximum:
            helper.maximum = key
 
# Function to find the successor of the given key
 
 
def VEB_successor(helper, x):
 
        # Base case: If key is 0 and its successor
        # is present then return 1 else return null
    if helper.universe_size == 2:
        if x == 0 and helper.maximum == 1:
            return 1
        else:
            return None
 
    # If key is less than minimum then return minimum
        # because it will be successor of the key
    elif helper.minimum is not None and x < helper.minimum:
        return helper.minimum
    else:
 
        # Find successor inside the cluster of the key
                # First find the maximum in the cluster
        max_in_cluster = VEB_maximum(helper.clusters[helper.high(x)])
 
        # If there is any key( maximum!=-1 ) present in the cluster then find
        # the successor inside of the cluster
        if max_in_cluster is not None and helper.low(x) < max_in_cluster:
            offset = VEB_successor(
                helper.clusters[helper.high(x)], helper.low(x))
            return helper.generate_index(helper.high(x), offset)
 
            # Otherwise look for the next cluster with at least one key present
        else:
            succ_cluster = VEB_successor(helper.summary, helper.high(x))
 
            # If there is no cluster with any key present
            # in summary then return null
            if succ_cluster is None:
                return None
 
                # 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
 
 
def VEB_predecessor(helper, x):
 
        # 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 x == 1 and helper.minimum == 0:
            return 0
        else:
            return None
 
        # If the key is greater than maximum of the tree then
        # return key as it will be the predecessor of the key
    elif helper.maximum is not None and x > 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
        min_in_cluster = VEB_minimum(helper.clusters[helper.high(x)])
 
        # If any key is present in the cluster then find predecessor in
        # the cluster
        if min_in_cluster is not None and helper.low(x) > min_in_cluster:
            offset = VEB_predecessor(
                helper.clusters[helper.high(x)], helper.low(x))
            return helper.generate_index(helper.high(x), 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(x))
 
            # If no predecessor cluster then...
            if pred_cluster is None:
 
                        # Special case which is due to lazy propagation
                if helper.minimum is not None and x > helper.minimum:
                    return helper.minimum
                else:
                    return None
          # Otherwise find maximum in the predecessor cluster
            else:
                offset = VEB_maximum(helper.clusters[pred_cluster])
                return helper.generate_index(pred_cluster, offset)
 
 
def VEB_delete(helper, key):
 
    # If only one key is present, it means
    # that it is the key we want to delete
    # Same condition as key == max && key == min
    if helper.maximum == helper.minimum:
        helper.minimum = -1
        helper.maximum = -1
 
    # Base case: If the above condition is not true
    # i.e. the tree has more than two keys
    # and if its size is two than a tree has exactly two keys.
    # We simply delete it by assigning it to another
    # present key value
 
    elif helper.universe_size == 2:
        if key == 0:
            helper.minimum = 1
        else:
            helper.minimum = 0
        helper.maximum = helper.minimum
    else:
 
        # As we are doing something similar to lazy propagation
        # we will basically find next bigger key
        # and assign it as minimum
        if key == helper.minimum:
            first_cluster = VEB_minimum(helper.summary)
 
            key = helper.generate_index(
                first_cluster, VEB_minimum(helper.clusters[first_cluster]))
 
            helper.minimum = key
 
        VEB_delete(helper.clusters[helper.high(key)], helper.low(key))
 
        # After deleting the key, rest of the improvements
 
        # If the minimum in the cluster of the key is -1
        # then we have to delete it from the summary to
        # eliminate the key completely
        if VEB_minimum(helper.clusters[helper.high(key)]) == -1:
            VEB_delete(helper.summary, helper.high(key))
 
            # After the above condition, if the key
            # is maximum of the tree then...
            if key == helper.maximum:
                max_insummary = VEB_maximum(helper.summary)
 
                # If the max value of the summary is null
                # then only one key is present so
                # assign min. to max.
                if max_insummary == -1:
                    helper.maximum = helper.minimum
                else:
 
                    # Assign global maximum of the tree, after deleting
                    # our query-key
                    helper.maximum = helper.generate_index(
                        max_insummary, VEB_maximum(helper.clusters[max_insummary]))
 
        # Simply find the new maximum key and
        # set the maximum of the tree
        # to the new maximum
        elif key == helper.maximum:
            helper.maximum = helper.generate_index(helper.high(
                key), VEB_maximum(helper.clusters[helper.high(key)]))
 
 
# Driver code
veb = Van_Emde_Boas(8)
# Inserting keys
insert(veb, 1)
insert(veb, 0)
insert(veb, 2)
insert(veb, 4)
 
print(isMember(veb, 2))
print(VEB_predecessor(veb, 4), VEB_successor(veb, 1))
 
if isMember(veb, 2):
    VEB_delete(veb, 2)
 
print(isMember(veb, 2))
print(VEB_predecessor(veb, 4), VEB_successor(veb, 1))

C#

using System;
using System.Collections.Generic;
 
public class Van_Emde_Boas {
 
    public int universe_size;
    public int minimum;
    public int maximum;
    public Van_Emde_Boas summary;
    public List<Van_Emde_Boas> clusters;
 
    public Van_Emde_Boas(int size)
    {
        universe_size = size;
        minimum = -1;
        maximum = -1;
 
        // Base case
        if (size <= 2) {
            summary = null;
            clusters = new List<Van_Emde_Boas>(0);
        }
        else {
            int no_clusters
                = (int)Math.Ceiling(Math.Sqrt(size));
            summary = new Van_Emde_Boas(no_clusters);
 
            clusters
                = new List<Van_Emde_Boas>(no_clusters);
 
            for (int i = 0; i < no_clusters; i++) {
                clusters.Add(new Van_Emde_Boas(
                    (int)Math.Ceiling(Math.Sqrt(size))));
            }
        }
    }
 
    // Function to return cluster numbers
    // in which key is present
    public int high(int x)
    {
        int div = (int)Math.Ceiling(Math.Sqrt(universe_size));
        return x / div;
    }
    // Function to return position of x in cluster
    public int low(int x)
    {
        int mod = (int)Math.Ceiling(Math.Sqrt(universe_size));
        return x % mod;
    }
 
    // Function to return position of x in cluster
    public int generate_index(int x, int y)
    {
        int ru = (int)Math.Ceiling(Math.Sqrt(universe_size));
        return x * ru + y;
    }
}
 
public class Main_Program {
  
  
    // Function to return the minimum value
    // from the tree if it exists
    public static 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
    public static int VEB_maximum(Van_Emde_Boas helper)
    {
        return (helper.maximum == -1 ? -1 : helper.maximum);
    }
 
 
    // Function to insert a key in the tree
    static 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 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
            if (key < helper.minimum) {
                int temp = helper.minimum;
                helper.minimum = key;
                key = temp;
            }
 
            // 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
                    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 to find the successor of the given key
public static int VEB_successor(Van_Emde_Boas helper, int key)
{
    if (helper.universe_size == 2)
    {
        if (key == 0 && helper.maximum == 1)
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }
        // If key is less than 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;
        int 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);
        }
        else
        {
            succ_cluster = VEB_successor(helper.summary, helper.high(key));
            if (succ_cluster == -1)
            {
                return -1;
            }
            else
            {
                // Find minimum in successor cluster which
                // will be the successor of the key
                offset = VEB_minimum(helper.clusters[succ_cluster]);
                return helper.generate_index(succ_cluster, offset);
            }
        }
    }
}
 
    // Function to find the predecessor of the given key
 public static int VEB_predecessor(Van_Emde_Boas helper, int key) {
        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;
            int 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);
            }
            else {
                        // returns the index of predecessor cluster
                // with any key present
                pred_cluster = VEB_predecessor(
                    helper.summary, helper.high(key));
 
                if (pred_cluster == -1) {
                    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);
                }
            }
        }
    }
     
    public static void VEB_delete(Van_Emde_Boas helper, int key)
{
        // If only one key is present, it means
        // that it is the key we want to delete
    if (helper.maximum == helper.minimum) {
        helper.minimum = -1;
        helper.maximum = -1;
    }
     
    // Base case: If the above condition is not true
        // i.e. the tree has more than two keys
        // and if its size is two than a tree has exactly
        // two keys.
    else if (helper.universe_size == 2) {
        if (key == 0) {
            helper.minimum = 1;
        }
        else {
            helper.minimum = 0;
        }
        helper.maximum = helper.minimum;
    }
    else {
         
        // As we are doing something similar to lazy
            // propagation we will basically find next
            // bigger key and assign it as minimum
        if (key == helper.minimum) {
            int first_cluster = VEB_minimum(helper.summary);
            key = helper.generate_index(first_cluster, VEB_minimum(helper.clusters[first_cluster]));
            helper.minimum = key;
        }
        // Now we delete the key
        VEB_delete(helper.clusters[helper.high(key)], helper.low(key));
         
            // After deleting the key, rest of the
            // improvements
 
            // If the minimum in the cluster of the key is
            // -1 then we have to delete it from the summary
            // to eliminate the key completely
        if (VEB_minimum(helper.clusters[helper.high(key)]) == -1) {
            VEB_delete(helper.summary, helper.high(key));
            if (key == helper.maximum) {
                int max_insummary = VEB_maximum(helper.summary);
                if (max_insummary == -1) {
                    helper.maximum = helper.minimum;
                }
                else {
                        // Assign global maximum of the
                        // tree, after deleting our
                        // query-key
                    helper.maximum = helper.generate_index(max_insummary, VEB_maximum(helper.clusters[max_insummary]));
                }
            }
        }
            // Simply find the new maximum key and
            // set the maximum of the tree
            // to the new maximum
        else if (key == helper.maximum) {
            helper.maximum = helper.generate_index(helper.high(key), VEB_maximum(helper.clusters[helper.high(key)]));
        }
    }
}
 
    // Function that returns true if the
    // key is present in the tree
public static bool isMember(Van_Emde_Boas helper, int key)
{
    if (helper.universe_size < key)
    {
        return false;
    }
    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 (helper.universe_size == 2)
        {
            return false;
        }
        else
        {
            return isMember(helper.clusters[helper.high(key)], helper.low(key));
        }
    }
}
 
        // Driver code
     public static void Main() {
        Van_Emde_Boas end = new Van_Emde_Boas(8);
        // Inserting Keys
       insert(end, 1);
       insert(end, 0);
       insert(end, 2);
       insert(end, 4);
        
       // Before deletion
       Console.WriteLine(isMember(end,2));
       Console.WriteLine(VEB_predecessor(end, 4)+" "+VEB_successor(end, 1));
          
         // Delete only if the key is present
        if (isMember(end, 2))
         VEB_delete(end, 2);
           
       // After deletion
       Console.WriteLine(isMember(end,2));
       Console.WriteLine(VEB_predecessor(end, 4)+" "+VEB_successor(end, 1));
    }
}

Javascript

class Van_Emde_Boas {
  constructor(size) {
    this.universe_size = size;
    this.minimum = -1;
    this.maximum = -1;
    this.summary = null;
    this.clusters = [];
 
    // Function to return cluster numbers
    this.high = function (x) {
      const div = Math.ceil(Math.sqrt(this.universe_size));
      return Math.floor(x / div);
    };
 
    // Function to return position of x in cluster
    this.low = function (x) {
      const mod = Math.ceil(Math.sqrt(this.universe_size));
      return x % mod;
    };
 
    // Function to return the index from cluster number and position
    this.generate_index = function (x, y) {
      const ru = Math.ceil(Math.sqrt(this.universe_size));
      return x * ru + y;
    };
 
    // Base case
    if (size <= 2) {
      this.summary = null;
      this.clusters = [];
    } else {
      const no_clusters = Math.ceil(Math.sqrt(size));
 
      // Assigning VEB(sqrt(u)) to summary
      this.summary = new Van_Emde_Boas(no_clusters);
 
      // Creating an array of VEB Tree pointers of size sqrt(u)
      for (let i = 0; i < no_clusters; i++) {
        this.clusters[i] = new Van_Emde_Boas(Math.ceil(Math.sqrt(size)));
      }
    }
  }
}
 
// Function to return the minimum value from the tree if it exists
function VEB_minimum(helper) {
  return helper.minimum === -1 ? -1 : helper.minimum;
}
 
// Function to return the maximum value from the tree if it exists
function VEB_maximum(helper) {
  return helper.maximum === -1 ? -1 : helper.maximum;
}
 
// Function to insert a key in the tree
function insert(helper, key) {
  // If no key is present in the tree then set both minimum and maximum to the key
  if (helper.minimum === -1) {
    helper.minimum = key;
    helper.maximum = key;
  } else {
    if (key < helper.minimum) {
      // Swap the values of key and minimum
      const temp = key;
      key = helper.minimum;
      helper.minimum = temp;
    }
 
    if (helper.universe_size > 2) {
      if (VEB_minimum(helper.clusters[helper.high(key)]) === -1) {
        insert(helper.summary, helper.high(key));
        helper.clusters[helper.high(key)].minimum = helper.low(key);
        helper.clusters[helper.high(key)].maximum = helper.low(key);
      } else {
        insert(helper.clusters[helper.high(key)], helper.low(key));
      }
    }
 
    if (key > helper.maximum) {
      helper.maximum = key;
    }
  }
}
 
// Function that returns true if the key is present in the tree
function isMember(helper, key) {
  if (helper.universe_size < key) {
    return false;
  }
 
  if (helper.minimum === key || helper.maximum === key) {
    return true;
  } else {
    if (helper.universe_size === 2) {
      return false;
    } else {
      return isMember(helper.clusters[helper.high(key)], helper.low(key));
    }
  }
}
 
// Function to find the successor of the given key
function VEB_successor(helper, key) {
  if (helper.universe_size === 2) {
    if (key === 0 && helper.maximum === 1) {
      return 1;
    } else {
      return -1;
    }
  }
 
  if (helper.minimum !== -1 && key < helper.minimum) {
    return helper.minimum;
  } else {
    const max_incluster = VEB_maximum(helper.clusters[helper.high(key)]);
    let offset = 0;
    let succ_cluster = 0;
 
    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);
    } else {
      succ_cluster = VEB_successor(helper.summary, helper.high(key));
      if (succ_cluster === -1) {
        return -1;
      } else {
        offset = VEB_minimum(helper.clusters[succ_cluster]);
        return helper.generate_index(succ_cluster, offset);
      }
    }
  }
}
 
// Function to find the predecessor of the given key
function VEB_predecessor(helper, key) {
  if (helper.universe_size === 2) {
    if (key === 1 && helper.minimum === 0) {
      return 0;
    } else {
      return -1;
    }
  }
 
  if (helper.maximum !== -1 && key > helper.maximum) {
    return helper.maximum;
  } else {
    const min_incluster = VEB_minimum(helper.clusters[helper.high(key)]);
    let offset = 0;
    let pred_cluster = 0;
 
    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);
    } else {
      pred_cluster = VEB_predecessor(helper.summary, helper.high(key));
      if (pred_cluster === -1) {
        if (helper.minimum !== -1 && key > helper.minimum) {
          return helper.minimum;
        } else {
          return -1;
        }
      } else {
        offset = VEB_maximum(helper.clusters[pred_cluster]);
        return helper.generate_index(pred_cluster, offset);
      }
    }
  }
}
 
// Function to delete a key from the tree
function VEB_delete(helper, key) {
  if (helper.maximum === helper.minimum) {
    helper.minimum = -1;
    helper.maximum = -1;
  } else if (helper.universe_size === 2) {
    if (key === 0) {
      helper.minimum = 1;
    } else {
      helper.minimum = 0;
    }
    helper.maximum = helper.minimum;
  } else {
    if (key === helper.minimum) {
      const first_cluster = VEB_minimum(helper.summary);
      key = helper.generate_index(first_cluster, VEB_minimum(helper.clusters[first_cluster]));
      helper.minimum = key;
    }
    VEB_delete(helper.clusters[helper.high(key)], helper.low(key));
    if (VEB_minimum(helper.clusters[helper.high(key)]) === -1) {
      VEB_delete(helper.summary, helper.high(key));
      if (key === helper.maximum) {
        const max_insummary = VEB_maximum(helper.summary);
        if (max_insummary === -1) {
          helper.maximum = helper.minimum;
        } else {
          helper.maximum = helper.generate_index(max_insummary, 
          VEB_maximum(helper.clusters[max_insummary]));
        }
      }
    } else if (key === helper.maximum) {
      helper.maximum = helper.generate_index(helper.high(key),
      VEB_maximum(helper.clusters[helper.high(key)]));
    }
  }
}
 
// Driver code
const end = new Van_Emde_Boas(8);
 
// Inserting Keys
insert(end, 1);
insert(end, 0);
insert(end, 2);
insert(end, 4);
 
// Before deletion
console.log(isMember(end, 2));
console.log(VEB_predecessor(end, 4), VEB_successor(end, 1));
 
// Delete only if the key is present
if (isMember(end, 2)) VEB_delete(end, 2);
 
// After deletion
console.log(isMember(end, 2));
console.log(VEB_predecessor(end, 4), VEB_successor(end, 1));

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Van Emde Boas Tree | Set 4 | Deletion

C++

Java

Python3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

Verizon will basically pay you to buy the new, awesome Barbie phone

8 Best VPNs for Apple TV in 2024: Fast & Secure by Penka Hristovska

Samsung offers free screen replacements for users still suffering green line issues

7 Best Free Antiviruses for Mac in 2024: Are They Any Good? by Katarina Glamoslija

Recent Comments

EDITOR PICKS

Verizon will basically pay you to buy the new, awesome Barbie phone

8 Best VPNs for Apple TV in 2024: Fast & Secure by Penka Hristovska

Samsung offers free screen replacements for users still suffering green line issues

POPULAR POSTS

Verizon will basically pay you to buy the new, awesome Barbie phone

8 Best VPNs for Apple TV in 2024: Fast & Secure by Penka Hristovska

Samsung offers free screen replacements for users still suffering green line issues

POPULAR CATEGORY

ABOUT US

FOLLOW US