interval_tree

v0.1.0

interval_tree v0.1.0 Interval.Tree

Module stores interval data in a tree structure called an interval tree

The underlying tree implements a self-balancing AVL tree ensuring all insert operations are O(log n) and that tree height is always O(log n)

The tree node contains the interval data which contains the start and finish times

We also keep track of the max time for that node’s subtree. This is helpful when we compute the overlap search

The left and right child nodes of the current node are stored in the left and right fields respectively

Thanks to geeksforgeeks.org and the CLR algorithms textbook for Interval and AVL Tree descriptions and implementations

http://www.geeksforgeeks.org/interval-tree/ http://www.geeksforgeeks.org/avl-tree-set-1-insertion/ https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree

Implemented operations are traverse, search, and insert

Link to this section Summary

Functions

do_search(arg1, t2, acc)
info(tree)

Provides dump of tree info to be used in Inspect protocol implementation

insert(tree, value)

Public insert method, inserts interval value into the interval key using the low interval node value to maintain sorted order

new()
search(tree, key)

Search whether a given interval key overlaps with any interval nodes, returns ALL overlaps

traverse(tree)

Traverse implements an inorder traversal

Link to this section Functions

Link to this function do_search(arg1, t2, acc)
Link to this function info(tree)

Provides dump of tree info to be used in Inspect protocol implementation

Link to this function insert(tree, value)

Public insert method, inserts interval value into the interval key using the low interval node value to maintain sorted order

Link to this function search(tree, key)

Search whether a given interval key overlaps with any interval nodes, returns ALL overlaps

Link to this function traverse(tree)

Traverse implements an inorder traversal