Implementing an Interval Tree in JavaScript

Interval trees are powerful data structures used to efficiently store and query intervals. They allow you to quickly find all intervals that overlap with a given interval, making them useful in applications like scheduling, collision detection, and range searching. This challenge asks you to implement an interval tree in JavaScript, focusing on core functionality and efficiency.

Problem Description

You are tasked with implementing an Interval Tree data structure in JavaScript. The tree should support the following operations:

1. insert(interval): Inserts a new interval into the tree. An interval is represented as an object with start and end properties (numbers).
2. overlapSearch(interval): Searches the tree for all intervals that overlap with the given interval. Overlap is defined as intervals having a common point (i.e., interval.start <= otherInterval.end && interval.end >= otherInterval.start). Returns an array of overlapping intervals.
3. delete(interval): Deletes an interval from the tree.
4. isEmpty(): Returns true if the tree is empty, false otherwise.

The tree should be self-balancing to ensure efficient search and insertion operations. While a full self-balancing implementation (like AVL or Red-Black) is not strictly required for this challenge, you should strive for a reasonably balanced structure to avoid worst-case O(n) search times. A simple binary search tree approach is acceptable as a starting point, but consider how to maintain balance as you add more intervals.

Key Requirements:

• The start and end properties of intervals must be numbers.
• The overlapSearch function must return an array of intervals that overlap, sorted by their start property in ascending order.
• The delete function should correctly remove the interval from the tree and maintain the tree's structure.
• The isEmpty function should return the correct boolean value.

Examples

Example 1:

Input:
  tree = new IntervalTree();
  tree.insert({start: 1, end: 3});
  tree.insert({start: 2, end: 4});
  tree.insert({start: 5, end: 7});
  interval = {start: 1.5, end: 2.5};
Output:
  [{start: 1, end: 3}, {start: 2, end: 4}]
Explanation:
  The intervals {start: 1, end: 3} and {start: 2, end: 4} overlap with {start: 1.5, end: 2.5}.  They are returned in ascending order of their start values.

Example 2:

Input:
  tree = new IntervalTree();
  tree.insert({start: 1, end: 3});
  tree.insert({start: 2, end: 4});
  tree.insert({start: 5, end: 7});
  interval = {start: 8, end: 10};
Output:
  []
Explanation:
  No intervals in the tree overlap with {start: 8, end: 10}.

Example 3: (Edge Case - Deletion)

Input:
  tree = new IntervalTree();
  tree.insert({start: 1, end: 3});
  tree.insert({start: 2, end: 4});
  tree.delete({start: 2, end: 4});
  interval = {start: 1.5, end: 2.5};
Output:
  [{start: 1, end: 3}]
Explanation:
  The interval {start: 2, end: 4} is deleted.  The overlap search now only returns {start: 1, end: 3}.

Constraints

• Interval start and end values will be numbers.
• The number of intervals to be inserted will be between 0 and 1000.
• The overlapSearch function should return results in O(log n) time on average (where n is the number of intervals). While a perfectly balanced tree is not required, avoid structures that lead to O(n) search times.
• The delete function should maintain the tree's integrity and have an average time complexity of O(log n).

Notes

• Consider using a binary search tree structure as a foundation for your interval tree.
• The max property of each node can store the maximum end value of any interval in the subtree rooted at that node. This is crucial for efficient overlap searching.
• Think about how to handle duplicate intervals. The problem description doesn't explicitly address this, so you can choose to either allow duplicates or prevent them. Document your choice.
• Focus on clarity and readability of your code. Well-commented code is appreciated.
• You can assume that the input intervals are valid (i.e., start is always less than or equal to end).