🚀 go-pugleaf

In article <1708@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
>
>     I have in mind what might be aptly called the Universal Data Structure.
>It is an ordered list with the following properties:
>
>IT HAS ARRAY-LIKE FEATURES:
>* Shift-by-K is a log(N) operation (where N is the list's size)
>e.g.
>  With arrays, one could perform a shift-by-K by adding K to the array index.
>
>* Index Subtraction (finding the difference between 2 elements' indices)
>  is log(N).
>
>IT HAS LINKED-LIST-LIKE FEATURES:
>* Insertion, and Deletion are log(N) operations.  With arrays, inserting or
>deleting an element after the K'th element would require moving all the
>remaining elements (k+1, k+2, ..., N) over by one.

This could easily be implemented by any balanced search tree (an AVL-tree
is one choise). You just have to add an extra counter to each node 
telling the number of elements in its left subtree.

You can easily find the rank of an element during the search for it.
When you go right during a search you add the size of the subtree at the
left sibling (+1).

If you have the rank of an element you can easily see which way you should
go at each node in the tree, starting from the root. You could also walk 
up in the tree if you have stacked the ancestors of the first node. It 
would be slightly more efficient.

Index subtraction is trivial.

Insertion (and deletion) is also easy do. You add (subtract) one to 
the counter if you insert (delete) the new element in its left subtree, 
otherwise you don't.

All operations take O(log n) time. Maybe you have to be a bit careful
when you do rotations, but it is fairly simple.

Svante Carlsson
Lund University
Lund, Sweden
(email: Svante@dna.lth.se)