Reputation: 7143

Useful data structure for the following case

Which can be the beste data structures for the following case.

1.Should have operations like search, insert and delete. Mostly searching activities will be there.Around 90% of the operations will be search and rest are delete and insert.

2 Insertion,deletion and searching will be based on the key of the objects. Each key will point to a object. The keys will be sorted.

Any suggestion for optimal data structure will be highly appreciated.

Upvotes: 0

Answers (5)

ninjagecko

Reputation: 91094

You want a tree-backed Map; basically you just want a tree where the nodes are dynamically sorted ("self-balanced") by key, with your objects hanging off of each node with corresponding key.

If you would like an "optimal" data structure, that completely depends on the distribution of patterns of inputs you expect. The nice thing about a self-balancing tree is you don't really need to care too much about the pattern of inputs. If you really want the best-guess as-close-to-optimal as possible we know of, and you don't know much about the specific sequences of queries, you can use a http://en.wikipedia.org/wiki/Tango_tree which is O(log(log(N))-competitive. This grows so slowly that, for all practical purposes, you have something which performs no worse than effectively a constant factor from the best possible data structure you could have chosen.

However it's somewhat grungy to implement, you may just be better using a library for a self-balancing tree.

Python: https://github.com/pgrafov/python-avl-tree/

Java: If you're just Java, just use a TreeMap (red-black tree based) and ignore the implementation details. Most languages have similar data structures in their standard libraries.

Upvotes: 1

KeithS

Reputation: 71565

My guess is that you want to optimize time. Overall, a red-black tree will have logarithmic-time performance in all three operations. It will probably be your best overall bet on execution time; however, red-black trees are complex to implement and require a node structure meaning they will be stored using more memory than the contained data itself requires.

Upvotes: 1