File: rtree.el.html

A "range tree" is a binary tree that stores ranges. They are similar to interval trees, but do not allow overlapping intervals.

A range is an ordered list of number intervals, like this:

((10 . 25) 56 78 (98 . 201))

Common operations, like lookup, deletion and insertion are O(n) in a range, but an rtree is O(log n) in all these operations. Transformation between a range and an rtree is O(n).

The rtrees are quite simple. The structure of each node is

(cons (cons low high) (cons left right))

That is, they are three cons cells, where the car of the top cell is the actual range, and the cdr has the left and right child. The rtrees aren't automatically balanced, but are balanced when created, and can be rebalanced when deemed necessary.

Defined variables (0)

Defined functions (19)

Defined faces (0)