6

I'm looking for a data structure with the functionality of eg. the OrderedDictionary in .NET, that is to say an associative collection (i.e. one that associates a key with a value) that maintains element order (just like a normal List does).

It must have fast lookup by both index and key. It should also have a fast "append" operation (inserting a new item at the end), and fast removal of items with any index (based on either index or key).

The OrderedDictionary in .NET uses both a hash table and an array to store its items if I'm not mistaken. Retreiving an index based on a key (or vice versa) is therefore O(n), and of course removal of an item from the middle of an array is O(n) to start with, plus the added lookup of the index from the key if removing by key.

My question is if there exists a more efficient data structure that satisfies my conditions, or if this is indeed my best option here?

Upendra Chaudhari
  • 6,473
  • 5
  • 25
  • 42
DeCaf
  • 6,026
  • 1
  • 29
  • 51

4 Answers4

4

I think you can do this with two red-black trees: A key-lookup tree to store the keys ordered by a compare function, and an index-lookup tree, with the keys in arbitrary ordering, as in a list. Each index-lookup node must have a 'size' field - a Red-Black tree can do lookup by index if a 'size' field is included in each node. See for example the RedBlackTreeSet implementation in the C5 Generic Collection Library.

Each entry in the key-lookup tree needs a pointer across to its corresponding entry in the index-lookup tree.As well as left- and right-node pointers, the index-lookup tree will require a parent pointer field to allow bottom-to-top navigation as well as top-to-bottom.

In all, six pointers are required for each key: the usual left and right pointers in both nodes, plus the pointer from the key-lookup-node to the index-lookup-node, plus the parent pointer in each of the index-lookup-nodes. You would also need a pointer in each node to point to the stored value.

Operations:

Append - An append operation would insert the key into both trees - once in the key-lookup tree, at a position determined by the compare function, and again in the rightmost position of the index-lookup tree. Insertion into a red-black tree is a logarithmic time operation.

Lookup by key - this is done on the key-lookup tree, using the compare function to find the correct position - O(log(n))

Lookup by index - this can be done on the index-lookup field, as mentioned above - O(log(n))

Get index from key - first lookup the key in the key-lookup tree O(log(n)). Follow the pointer across to the index-lookup tree. Follow the parent pointers up to the root node, (O(log(n)) for a balanced tree). Use the 'size' fields on the way up to determine the index of the key. - O(log(n)) overall.

Delete by index - lookup the item in the index-lookup tree. Delete from index-lookup tree. Lookup the located key in the key-lookup tree. Delete from the key-lookup tree. All operations are O(log(n)) , so delete is O(log(n)) overall.

Delete by key - use 'Get index from key' to get the index of the key. Delete by index from the index-lookup tree. Delete by key from the key-lookup tree. O(log(n)) overall.

This structure also supports O(log(n)) insertion at any arbitrary position, not just at the end.

Storage overhead is obviously considerable, but remains O(n). Time complexity meets all the requirements.

Unfortunately I am not aware of any implementation of this structure.

Update: It occurs to me you can combine a tree with a hash table to get O(1) by-key lookup. Instead of having two trees, as I suggest above, use a hash table for the by-key lookup, and a balanced order-statistics tree for the by-position lookup, as above, but have the slots of the hash table contain pointers to the nodes of the balanced tree for doing the get-list-position-by-key lookup. By-key lookups are now O(1), with everything else staying O(ln(n)) on average. Of course, you now get the occasional O(n) re-hash penalty, as with any hash-table.

Crosbie
  • 1,805
  • 2
  • 16
  • 22
  • I actually did an implementation of an RB-tree that did lookup by index in O(log n) time in C++ a few years ago, had forgotten about that one. Only drawback of course is that we still need two trees instead of just one. But your suggestion does fulfil the requirements I gave. Wonder if there's a better way still... ;) – DeCaf Oct 19 '11 at 18:30
  • Instead of two trees you can use a hash and a tree to get O(1) lookup by key. Everything else remains O(ln(n)). I just added an update to that effect. Is it even theoretically possible to do better than O(ln(n)) lookup for an ordered structure supporting fast insertion? – Crosbie Dec 18 '11 at 09:50
3

OrderedDictionary meats your requirements actually.

Your analysis of the OrderedDictionary is incorrect. It is actually O(1) for key based look up and O(1) for index according to this.

Even simple analysis gives you O(1) lookup either by key or index. Arrays provide O(1) access and hash tables provide effectively O(1) access.

Insert/ Delete is a litte more complicated, but given amortized analysis is still O(1)

The article claims that it is O(n) for insert and delete. This at least does not hold for insert since amortized analysis allows you to simply up the "cost" of inserting a given element from 1 to 2. When inserting an element that requires an array resize, the second half of the cost is used to pay the cost of copying. The final insert will take longer, but its still O(1) amortized and the discrepancy only shows up if you cause an array resize which is unlikely.

imichaelmiers
  • 3,449
  • 2
  • 19
  • 25
  • Yes, inserts are amortized O(1) but worst case O(n). But how about delete by key? – DeCaf Oct 20 '11 at 04:15
  • Actually if this solution is array based, the best case would only happend when inserting at the end of the list. When inserting or deleting arbitrarily, you will incur a linear scan through the remainder of the list when shifting elements out (on an insert) or in (on a delete). – allingeek Oct 21 '11 at 08:24
2

Maybe you'll find something interesting here in The C5 Generic Collection Library for C# (from page 233)

Wojteq
  • 1,173
  • 9
  • 23
1

You can use Balanced binary search tree like the link, just for in definition of TreeNode you should add your keys, but the problem is finding element is not O(1), it's O(log(n)) both by keys and index (in fact index is not part of TreeNode, relatively can be found) but all operations are O(log(n)) and is fastest known way based on comparison methods.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • How would you get an item by index in a BST? Also, isn't the BST sorted by key, meaning it does not preserve item indices? – DeCaf Oct 16 '11 at 06:59
  • @DeCaf, You can sort it by key not value in one bst, and sort it with value in another bst, so when calling by key, you will find it in O(log(n)) and when you want to find it by index (value base) you can do it in O(log(n)) also removal takes same time for both. – Saeed Amiri Oct 16 '11 at 07:12
  • For index, when you say I'th element, means i'th greatest element which can be done in O(log(n)) in bst. – Saeed Amiri Oct 16 '11 at 07:18
  • Perhaps I was a bit vague in my formulation. With index I actually meant something like the insertion order, i.e. the same way that a normal `List` works. Meaning appending 3, 1, 2, should give 3 index 0, 1 index 1 and 2 index 2. But out of curiosity, how do you find the i:th greatest element in a BST? – DeCaf Oct 16 '11 at 07:22
  • @DeCaf, you can see O(log n) amortized algorithm here: http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way – Saeed Amiri Oct 16 '11 at 08:59