Skip to main content

/

Docs

Nightly

v25.1

Log in

Mojo module

interval

A self-balancing interval tree is a specialized binary search tree designed to efficiently store and query intervals.

It maintains intervals sorted by their low endpoints and augments each node with a max_high attribute, representing the maximum high endpoint in its subtree. This max_high value enables efficient overlap searching by pruning the search space. Self-balancing mechanisms, such as Red-Black or AVL trees, ensure logarithmic time complexity for operations.

Key Features:

  • Stores intervals (low, high).
  • Nodes ordered by low endpoints.
  • max_high attribute at each node for efficient overlap search.
  • Self-balancing (e.g., using Red-Black tree logic) for O(log n) operations.

Operations:

  • Insertion: O(log n) - Adds a new interval, maintaining balance and updating max_high.
  • Overlap Search: O(log n) - Finds intervals overlapping a query interval using max_high for pruning.
  • Deletion: O(log n) - Removes an interval, maintaining balance and updating max_high.

Space Complexity: O(n), where n is the number of intervals.

Use Cases:

  • Calendar scheduling
  • Computational geometry
  • Genomics
  • Database indexing
  • Resource allocation

In essence, this data structure provides a fast and efficient way to manage and query interval data, particularly for finding overlaps.

Structs​

  • ​Interval: A half-open interval [start, end) that represents a range of values.
  • ​IntervalTree: An interval tree data structure for efficient range queries.

Traits​

  • ​IntervalElement: The trait denotes a trait composition of the CollectionElement, Writable, Intable, and Comparable traits. Which is also subtractable.
  • ​IntervalPayload: The trait denotes a trait composition of the CollectionElement, Stringable, and Comparable traits.