Interval TreesDefinitionSlide 3ExamplePropertiesSelection of v.ptSlide 7Slide 8Need For Empty NodesWhy Upto 2n Nodes PermissibleLL RotationRemaining RotationsFind All Overlapping IntervalsSlide 14Slide 15Slide 16A VariantSlide 18Slide 19A Variant—SearchA Variant—LL RotationSlide 22Interval Trees•Store intervals of the form [li,ri], li <= ri.• Answer queries of the form: which intervals intersect/overlap a given interval [l,r].Definition•A binary tree.•Each node v has a point v.pt and two lists v.left and v.right.•Intervals with ri < v.pt are stored in the left subtree of v.•Intervals with li > v.pt are stored in the right subtree of v.•u.pt < v.pt for nodes u in left subtree of v.•u.pt > v.pt for nodes u in right subtree of v.Definition•Intervals with li <= v.pt <= ri are stored in v.v.left has these intervals sorted by li.v.right has these intervals sorted by ri.Example•v.pt = 4•L = {a, e}•R = {d}1e1 3a2 4c4 6b3 6f5 7d24L Rv•v.left = {c, f, b}•v.right = {c,b,f}Properties•Each interval is stored in exactly one node.•Each node stores between 1 and n intervals.•Number of nodes is O(n).•Sum of sizes of left and right lists is O(n).•Tree height depends on how you choose the points v.pt.Selection of v.pt•v is the median of the end points of the intervals stored in the subtree rooted at v.1e1 3a2 4c4 6b3 6f5 7d2•End points = {1, 2, 3, 4, 5, 6}•Use either 3 or 4 as v.pt.Selection of v.pt•With median selection, tree height is O(log n).•Median selection is possible only for static interval set.Selection of v.pt•Select v.pt arbitrarily.•Use a red-black tree.•Each node stores between 0 and n intervals.•At most 2n nodes permissible.•So, at most n empty nodes.•Tree height is O(log n).Need For Empty Nodes•Deletion from a degree 2 node.201062 815403025 35718Why Upto 2n Nodes Permissible•When number of nodes > 2n, at least 1 degree 0 or degree 1 node must be empty.•Empty degree 0 and 1 nodes are easily removed.•So, no need to keep them around.•2n suffices to avoid having to handle empty degree 2 nodes.LL Rotation•Intervals change only for A and B.•Those intervals of A that include B.pt need to be moved into B.ABB’LBRARAfter insertion.BAAfter rotation.BRARB’LRemaining Rotations•All insert/delete rotations require relocating intervals from O(1) nodes.•O(1) rotations per insert/delete.•Complexity of insert/delete is O(f(n)log n), where f(n) is time needed to relocate O(n) intervals from one node to another.Find All Overlapping Intervals•Query interval is [l,r].•v.pt [l,r] All intervals in v overlap.Search L and R for additional overlapping intervals.4L RvlrFind All Overlapping Intervals•v.pt lIntervals in v with ri >= l overlap.No interval in L overlaps.Search R for additional overlapping intervals.4L RvlrFind All Overlapping Intervals•v.pt rIntervals in v with li <= r overlap.No interval in R overlaps.Search L for additional overlapping intervals.4L RvlrFind All Overlapping Intervals•ComplexityO(log n) nodes encounteredAll intervals in v overlap.Intervals in v with ri >= l overlap.Intervals in v with li <= r overlap.•O(log n + |output|) when v.left and v.right are sorted arrays.4L RvlrA Variant•i and j are two intervals.•i < j iff li < lj or (li = lj and ri > rj)ijijijA Variant•Red-black tree.•Each node has exactly one interval.•v.max = max (right) end point of intervals in subtree rooted at v.A Variant1e1 3a2 4c4 6b3 6f5 7d2f,7e,4a,3 c,4d,7b,6A Variant—Search •Search for an interval that has an overlap with Q = [l,r]If v.interval and Q overlap, done.Otherwise, if v.leftChild.max >= l search v.leftChild.Otherwise search v.rightChild.f,7e,4a,3 c,4d,7b,6A Variant—LL Rotation•Max values changes only for A and B.A.max = max{BR.max, AR.max}.B.max = max{B’L.max, A.max}.ABB’LBRARAfter insertion.BAAfter rotation.BRARB’LRemaining Rotations•All insert/delete rotations require computing max for O(1) nodes.•O(1) rotations per insert/delete.•Complexity of insert/delete is O(log