Binary search vs binary search tree

35
votes

What is the benefit of a binary search tree over a sorted array with binary search? Just with mathematical analysis I do not see a difference, so I assume there must be a difference in the low-level implementation overhead. Analysis of average case run time is shown below.

Sorted array with binary search
search: O(log(n))
insertion: O(log(n)) (we run binary search to find where to insert the element)
deletion: O(log(n)) (we run binary search to find the element to delete)

Binary search tree
search: O(log(n))
insertion: O(log(n))
deletion: O(log(n))

Binary search trees have a worst case of O(n) for operations listed above (if tree is not balanced), so this seems like it would actually be worse than sorted array with binary search.

Also, I am not assuming that we have to sort the array beforehand (which would cost O(nlog(n)), we would insert elements one by one into the array, just as we would do for the binary tree. The only benefit of BST I can see is that it supports other types of traversals like inorder, preorder, postorder.

4
arraysalgorithmdata-structuresbinary-treetime-complexity
insertion and deletion from binary search array is O(n) and only finding is O(log(n)). – Mihran Hovsepyan
If it was, say, a linked list instead of an array then insertion/deletion will take O(log n). But not so for an array. – Bhaskar
@Bhaskar, another wrong comment, any kind of lookup on a linked list is O(n). – Blindy
@Blindy You are right. Sorry @john2011. Not sure how I missed it. – Bhaskar
@Blindy: Just for completeness' sake: Bhaskar is referring to insertion/deletion on a linked list, which is O(1). Lookup is O(n) as you correctly state. – quaylar

4 Answers

35
votes

Your analysis is wrong, both insertion and deletion is O(n) for a sorted array, because you have to physically move the data to make space for the insertion or compress it to cover up the deleted item.

Oh and the worst case for completely unbalanced binary search trees is O(n), not O(logn).

7
votes

There's not much of a benefit in querying either one.

But constructing a sorted tree is a lot faster than constructing a sorted array, when you're adding elements one at a time. So there's no point in converting it to an array when you're done.

3
votes

Note also that there are standard algorithms for maintaining balanced binary search trees. They get rid of the deficiencies in binary trees and maintain all of the other strengths. They are complicated, though, so you should learn about binary trees first.

Beyond that, the big-O may be the same, but the constants aren't always. With binary trees if you store the data correctly, you can get very good use of caching at multiple levels. The result is that if you are doing a lot of querying, most of your work stays inside of CPU cache which greatly speeds things up. This is particularly true if you are careful in how you structure your tree. See http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx for an example of how clever layout of the tree can improve performance greatly. An array that you do a binary search of does not permit any such tricks to be used.

0
votes

Adding to @Blindy , I would say the insertion in sorted array takes more of memory operation O(n) std::rotate() than CPU instruction O(logn), refer to insertion sort.

    std::vector<MYINTTYPE> sorted_array;

    // ... ...

    // insert x at the end
    sorted_array.push_back(x);

    auto& begin = sorted_array.begin();

    // O(log n) CPU operation
    auto& insertion_point = std::lower_bound(begin()
             , begin()+sorted_array().size()-1, x); 
    
    // O(n) memory operation
    std::rotate(begin, insertion_point, sorted_array.end());

I guess Left child right sibling tree combines the essence of binary tree and sorted array.

data structure operation CPU cost Memory operation cost
sorted array insert O(logn) (benefits from pipelining) O(n) memory operation, refer to insertion-sort using std::rotate()
search O(logn) benefits from inline implementation
delete O(logn) (when pipelining with memory operation) O(n) memory operation, refer to std::vector::erase()
balanced binary tree insert O(logn) (drawback of branch-prediction affecting pipelining, also added cost of tree rotation) Additional cost of pointers that exhaust the cache.
search O(logn)
delete O(logn) (same as insert)
Left child right sibling tree (combines sorted array and binary tree) insert O(logn) on average No need std::rotate() when inserting on left child if kept unbalanced
search O(logn) (in worst case O(n) when unbalanced) takes advantage of cache locality in right sibling search , refer to std::vector::lower_bound()
delete O(logn) (when hyperthreading/pipelining) O(n) memory operation refer to std::vector::erase()