CODEWITHSUNDEEP
c++vectorbinary-search-tree
Kushagra Aggarwal
Kushagra Aggarwal

Reputation: 131

Advantage of Binary Search Tree over vector in C++

What is the use of data structure Binary Search Tree, if vector (in sorted order) can support insert,delete and search in log(n) time (using binary search)??

Upvotes: 7

Views: 2957

Answers (3)

DU Jiaen
DU Jiaen

Reputation: 962

Theoretically there's impossible to do insert or delete in a sorted vector in O(log(n)). But if you really want the advantage of searching in BST vs vector, here's somethings I can think about:

BST and other tree structures take bulk of small memory allocations of "node", and each node is a fixed small memory chunk. While vector uses a big continuous memory block to hold all the items, and it double (or even triple) the memory usage while re-sizing. So in the system with very limited memory, or in the system where fragmentation happens frequently, it's possible that BST will successfully allocate enough memory chunks for all the nodes, while vector failed to allocate the memory.

Upvotes: 0

Martin Bonner supports Monica
Martin Bonner supports Monica

Reputation: 29007

The basic advantage of a tree is that insert and delete in a vector are not O(log(n)) - they are O(n). (They take log(n) comparisons, but n moves.)

The advantage of a vector is that the constant factor can be hugely in their favour (because they tend to be much more cache friendly, and cache misses can cost you a factor of 100 in performance).

Sorted vectors win when

  • Mostly searching.
  • Frequent updates but only a few elements in the container.
  • Objects have efficient move semantics

Trees win when

  • Lots of updates with many elements in the container.
  • Object move is expensive.

... and don't forget hashed containers which are O(1) search, and unordered vectors+linear search (which are O(n) for everything, but if small enough are actually fastest).

Upvotes: 7

ravi
ravi

Reputation: 10733

There won't be much difference in performance between a sorted vector and BST if there are only search operations after some initial insertions/deletions. As binary search over vector will cost you same as searching a key in BST. In fact I would go for sorted vector in this case as it's more cache friendly.

However, if there are frequent insertions/deletions involved along with searching, then a sorted vector won't be good option as elements need to move back and forth after every insertion and deletion to keep vector sorted.

Upvotes: 3

Related Questions