CODEWITHSUNDEEP
searchdata-structures
Bi Rico
Bi Rico

Reputation: 25813

What data structure supports fast insertion, deletion and search

I feel like this has to exist, but I just can't think of it. Is there a data structure that can one hold a sorted list of values and be searched quickly (maybe log(N) time like an array), and also supports insertion and removal of elements in log(N) or constant time?

Upvotes: 1

Views: 3125

Answers (1)

templatetypedef
templatetypedef

Reputation: 372694

This is pretty much the description of a balanced binary search tree, which stores elements in sorted order, allows for O(log n) insertions, deletions, and lookups, and allows for O(n) traversal of all elements.

There are many ways to build a balanced BST - there are red/black trees, AVL trees, scapegoat trees, splay trees, AA trees, treaps, (a, b)-trees, etc. Any of these would solve your problem. Of them, splay trees are probably the easiest to code up, followed by AA-trees and AVL trees.

Hope this helps!

Upvotes: 3

Related Questions