skiplist

Overview ¶

Package skiplist implements an n-dimensional rangetree based on a skip list. This should be faster than a straight slice implementation as memcopy is avoided.

Time complexities revolve around the ability to quickly find items in the n-dimensional skiplist. That time can be defined by the number of items in any dimension. Let N1, N2,... Nn define the number of dimensions.

Performance characteristics: Space: O(n) Search: O(log N1 + log N2 + ...log Nn) = O(log N1*N2*...Nn) Insert: O(log N1 + log N2 + ...log Nn) = O(log N1*N2*...Nn) Delete: O(log N1 + log N2 + ...log Nn) = O(log N1*N2*...Nn)