0

Is there a data structure that has the following properties?

  1. every element has a natural ordering as well as a key (arbitrary string or int).

  2. Maintains ordering of elements according to their natural ordering. For example, after I insert the integers in this order: 0, 2, 3, 1, I must be able to traverse it in this order: 0, 1, 2, 3 (natural ordering).

  3. Fast retrieval of an element according to its key, which can be arbitrary.

Insertion and retrieval should have sublinear time complexity.

You could say it is a combination of a tree and hashmap, or a tree sorted in 2 ways concurrently.

It doesn't really matter what the programming language of the code or library you're pointing me to is, I can do the necessary translation.

Improve this question
1
  • To clarify: you want the ability to traverse in order 0, 2, 3, 1, and also in the order 0, 1, 2, 3? Commented Apr 17, 2014 at 19:10

3 Answers 3

Reset to default
2

Red-black trees have O(log n) search, insertion, and removal. They are a type of balanced binary search tree. They also support in-order traversals. A quick google will turn up more information.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

There are several possibilities. The simplest example is a self balancing binary search tree. Look also at AVL tree, B-tree, B+ tree, red black tree, skip list, and many others. All of those (and their variants) meet your complexity requirements, although some are more efficient than others.

See List of data structures for more.

There are reference implementations of many of those data structures available for multiple languages.

That said, you should check your runtime library to see if it already has an implementation that does what you're asking. That will save you a lot of time, and will likely perform very well.

If you implement your own data structure, you can easily make the nodes contain pointers for both orderings. For example, a binary tree node would contain left and right pointers for the children, and also next and prev pointers for a doubly-linked list. The tree pointers would be for the comparison ordering, and the linked list would be the insertion order. The data structure would of course contain a root node pointer as well as a head and tail for the linked list.

Improve this answer

2 Comments

With all of these data structures, what you'd do is keep a linear list of the actual items for iteration by insertion order. The tree or whatever maintains references to the items in the linear list. Additions to the list are O(1)--just append.
@LucasTan: See my update regarding maintaining a linked list in the nodes.
0

If lexicographic sorting is acceptable, then you can use a prefix tree to avoid comparison based sorting and thus make the lookups O(1)* in the number of elements as well as provide O(N)* sorting in the number of elements.

It's not difficult to modify a prefix tree to store a value. Although, it may be easier to just use a separate map for that purpose.

*Note that the complexity of a prefix tree is generally measured based on the average size of the elements themselves, which is O(m). However, most other data structures use the number of elements in the data structure, and thus the complexities change a bit when the size of each element is considered. By this measure, a hashtable lookup is O(m) and a binary search tree lookup is O(m log N).

Improve this answer

2 Comments

What does "O(1) in the number of elements" supposed to mean? Lookup in a prefix tree is typically a function of the key's length.
@JimMischel: It's a difference in how the time complexity's are calculated. Most of the time the key's length is considered a constant and thus ignored, so I was trying to be consistent. However, I've now added clarification on the differences.