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

How about sorted insertion time?

Answer 2

In graphics programming if you have extended object(i.e. which represent an interval in each dimension and not just a point) you can add them to the smallest level of a binary tree(typically an octree) where they fit in entirely.

And if you don't pre-calculate the tree/sortedlist the O(n) random insertion time in a list can be prohibitively slow. Insertion time in a tree on the other hand is only O(log(n)).

Answer 3

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.

Answer 4

Imagine you have an array with a million elements.

You want to insert an element at location 5.

So you insert at the end of the array and then sort.

Let's say the array is full; that's O(nlog n), which is 1,000,000 * 6 = 6,000,000 operations.

Imagine you have a balanced tree.

That's O(log n), plus a bit for balancing = 6 + a bit, call it 10 operations.

So, you've just spent 6,000,000 ops sorting your array. You then want to find that element. What do you do? binary search - O(log n) - which is exactly the same as what you're going to do when you search in the tree!

Now imagine you want to allocate -another- element.

Your array is full! what do you do? re-allocate the array with n extra elements and memcpy the lot? you really want to memcpy 4mbytes?

In a tree, you just add another element...