CODEWITHSUNDEEP
algorithmdata-structures
user1724763
user1724763

Reputation:

Sorted data structure allowing access by key

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.

Upvotes: 0

Views: 315

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 134125

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.

Upvotes: 2

Nuclearman
Nuclearman

Reputation: 5314

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).

Upvotes: 0

Josh
Josh

Reputation: 1774

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.

Upvotes: 2

Related Questions