[Sugar-devel] I'm looking for a tree...

[Benjamin M. Schwartz]

I am looking for a fast data structure with the following properties:

Maintains an indexed list of arbitrary, non-ordered objects (like a python
List or C array)
Allows fast:
Insertion at any location
Deletion at any location
Lookup of an object by its index
Reverse lookup, to determine the index of an object

Python's List has O(1) lookup, but O(N) insert, delete, and
reverse-lookup.  To make reverse lookup O(1) I could maintain a separate
Dict mapping objects to indices, but this would cost an additional O(N) on
every insertion and deletion.

A linked list has O(1) insertion and deletion, but O(N) lookup and O(N)
reverse lookup.  I could maintain a separate Dict for the forward and
reverse mappings, but this would cost O(N) on every insertion and deletion.

A standard self-balancing tree cannot be used because the objects are not
ordered, and self-balancing trees require ordered keys.  I could use the
index of an object as the sort key, but then insertion and deletion are
O(N) because all subsequent keys must be altered.  I could fabricate new
sort keys to ensure that insertions occur at the desired location, but
then the length of the keys will grow like O(N), making all operations at
least O(N).

I feel like there should be some kind of standard tree-like data structure
that meets my requirements, but I can't find one.  Do you know of one?  Am
I on a unicorn hunt?

--Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
Url : http://lists.sugarlabs.org/archive/sugar-devel/attachments/20090606/27ed1252/attachment.pgp