Collection Kit

VanEmdeBoasTree

Advanced

A VanEmdeBoasTree is a tree data structure that supports fast operations on integers within a bounded universe. It provides O(1) time complexity for operations like insert, delete, and member queries, making it very efficient for certain applications.

Import Statement

import { VanEmdeBoasTree } from "collection-kit";

Key Features

Fast Operations: Supports O(1) time complexity for basic operations.
Bounded Universe: Works efficiently for integers within a specific range.

Common Operations

Insert

Add an integer to the tree.

Delete

Remove an integer from the tree.

Member

Check if an integer is present in the tree.

Successor

Find the smallest integer greater than a given integer.

Example Code

import { VanEmdeBoasTree } from "collection-kit";

const tree = new VanEmdeBoasTree(16); // universe size
tree.insert(5);
tree.insert(10);
tree.insert(15);

console.log("Member 10:", tree.member(10));     // true
console.log("Successor of 5:", tree.successor(5)); // 10