markh@csd4.csd.uwm.edu (Mark William Hopkins) (12/31/89)
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.
Is there a structure with such worst-case complexity? There are hardware
implementations of arrays with the desired Insert/Delete behavior, but can the
structure be implemented other kinds of hardware?svante@dna.lth.se (Svante Carlsson) (01/04/90)
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)