CODEWITHSUNDEEP
arraysbinary-search-tree
user3195395
user3195395

Reputation:

Why Binary search tree?

Why do people use binary search trees? Why not simply do a binary search on the array sorted from lowest to highest? To me, an insertion / deletion cost seems to be the same, why complicate life with processes such as max/min heapify etc?

Is it just because of random access required within a data structure?

Upvotes: 0

Views: 84

Answers (1)

pentadecagon
pentadecagon

Reputation: 4847

The cost of insertion is not the same. If you want to insert an item in the middle of an array, you have to move all elements to the right of the inserted element by one position, the effort for that is proportional to the size of the array: O(N). With a self-balancing binary tree the complexity of insertion is much lower: O(ln(N)).

Upvotes: 3

Related Questions