van-Emde-Boas-tree

The van Emde Boas (vEB) tree is a data structure designed to perform efficient operations on non-negative integer sets within a limited range. The vEB tree can execute search, insertion, deletion, predecessor, and successor operations in O(log log U) time, where U is the universe size.

History

The van Emde Boas tree was first introduced by Peter van Emde Boas in 1975. It was designed to improve the performance of priority queues used in event-driven simulations. Since its introduction, the vEB tree has been used in various applications where efficient operations on ordered sets are required.

Space Complexity

The space complexity of a van Emde Boas tree is O(U), where U is the universe size. The space complexity can be improved to O(n log U), where n is the number of elements in the tree, using a variant called the van Emde Boas tree with a satellite.

Class structure

class van_Emde_Boas {
private:
    int universe;
    int min;
    int max;
    vector<van_Emde_Boas*> cluster;
    van_Emde_Boas* summary;
    
    // Private helper methods
    int high(int x);
    int low(int x);
    int index(int x, int y);
    void empty_insert(van_Emde_Boas* V, int x);
    void swap(int &a, int &b);

public:
    // Constructor
    van_Emde_Boas(int size);
    
    // Public methods
    int minimum(van_Emde_Boas* V);
    int maximum(van_Emde_Boas* V);
    bool isMember(van_Emde_Boas* V, int x);
    int successor(van_Emde_Boas* V, int x);
    int predecessor(van_Emde_Boas* V, int x);
    void insert(van_Emde_Boas* V, int x);
    void canc(van_Emde_Boas* V, int x);
};

Method Descriptions

• Constructor: van_Emde_Boas(int size)
  • Initializes a vEB tree with a universe size equal to the specified 'size'.
  • The universe size must be a power of 2.
• int minimum(van_Emde_Boas* V):
  • Returns the minimum element in the vEB tree V.
  • If the tree is empty, the behavior is undefined.
• int maximum(van_Emde_Boas* V):
  • Returns the maximum element in the vEB tree V.
  • If the tree is empty, the behavior is undefined.
• bool isMember(van_Emde_Boas* V, int x):
  • Returns true if x is an element of the vEB tree V, otherwise false.
• int successor(van_Emde_Boas* V, int x):
  • Returns the smallest element in the vEB tree V that is strictly greater than x.
  • If no such element exists, the behavior is undefined.
• int predecessor(van_Emde_Boas* V, int x):
  • Returns the largest element in the vEB tree V that is strictly smaller than x.
  • If no such element exists, the behavior is undefined.
• void insert(van_Emde_Boas* V, int x):
  • Inserts the element x into the vEB tree V.
• void canc(van_Emde_Boas* V, int x):
  • Removes the element x from the vEB tree V.