Useful data structure for the following case

Which can be the be开发者_JAVA百科ste 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.

AVL tree, or at least BST.

If you want to acces often the same elements you might want to consider splay trees too.

(Should I explain why?)

Not sure by what you mean with "data structures"

I would suggest MySQL. Read more here: WikiPedia

Self-balancing tree of sorts (AVL, RB), or a hash table.

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.

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.