Implementing interval search tree. It has two API's to add anAn interval and tois a data structure that represents a range overlap ie(start & end, from & to check for overlap, or min & max, etc. To summarize algorithm). An -Interval Tree stores these intervals are added toin a binarysorted tree withstructure that makes searching for range intersections much faster. Interval trees help answer questions like: "find all stored intervals that at least partially overlap with the range a to b"
Typical interval trees store the intervals using the start of intervalthe range as indexthe key to sort ona binary search tree. To check for overlap it
This code implements the interval tree and has two methods:
add(start, end) - inserts an interval to the treeoverlap(start, end) - identifies if any interval in the tree overlaps with the input values.
The implemented algorithm follows 3 rules, which are a partan Augmented Interval Tree approach where each node maintains the maximum value contained in any of my algorithm and also commentedits child nodes. This maximum value is kept in sync by the add(start,end) method. Other details of the algorithm are:
intervals are added to a binary tree with the start of interval as index to sort on.
when intervals are added the maximum values of all parent nodes are updated to ensure they are in sync.
to check for overlap it performs a descending scan of the tree using iteration, not recursion. It checks each node it descends to, and if the node:
- intersects the input arguments, it returns true.
if (leftsubtree != null && leftsubtree.max > low) search left- else search right
Despite of a brief stint in explaining my problem, more details can be obtained on this link here.
I'm looking for code review, best practices, optimizations etc. Also verifying complexity to be
O(logn) O(log(n)) to add and O(logn)O(log(n)) to look for overlap. Do correct me if wrong.
