Why Binary Search Trees?

Question

I was reading binary search tree and was thinking that why do we need BST at all? All the things as far as I know can also be achieve using simple sorted arrays. For e.g. - In order to build a BST having n elements, we requires n*O(log n) time i.e. O(nlog n) and lookup time is O(log n). But this thing can also be achieve using array. We can have a sorted array(requires O(nlog n) time), and lookup time in that is also O(log n) i.e. binary search algo. Then why do we need another data structure at all? Are there any other use/application of BST which make them so special?

--Ravi

Answer 1

Arrays are great if you're talking about write once, read many times type of interactions. It's when you get down to inserting, swapping, and deletion in which BST really start to shine compared to an array. Since they're node based, rather than based on a contiguous chunk of memory, the cost of moving an element either into the collection or out of the collection is fast while still maintaining the sorted nature of the collection.

Think of it as you would the difference in insertion between linked lists versus arrays. This is an oversimplification but it highlights an aspect of the advantage I've noted above.