What is difference between Array and Binary search tree in efficiency?

Question

I want know what is the best : Array OR Binary search tree in ( insert , delete , find max and min ) and how can I Improve both of them ?

Solution 1

An array allows random access to each element in it. so you get insert, delete and look for a specific element in O(1), and max/min, delete in O(n). [you can also make max/min O(1) and delete O(n) instead]. If you are keeping your array sorted, it will cause insert/delete to be O(n), but you will gain O(logn) find, and O(1) min/max.

A BST is sorted by definition, and for a regular [unbalanced] BST, you get O(n) worst case behavior. For balanced BST, you get O(logn) insert/delete/find. You can get O(1) min/max any how for both.

Arrays are also usually faster to iterate [assuming order of iteration is not important] since you gain better cache performance. Also, unlike BST - which has unbounded size by nature, an array requires reallocation and copying the data when your array is full.

Improving a BST can be done by making it balanced - like AVL or red-black-trees.

Which is better? it depends on the application. Usually when you are planning to insert data and keep it sorted, BST will be prefered. If random access or iteration is the main purpose: you usually use an array.

Solution 2

Performance comparison of Arrays and Binary search trees:

                 Array                     Binary search tree
          Unsorted   Sorted           Average            Worst case
Space      O(n)       O(n)             O(n)               O(n)
Search     O(n)       O(log n) *       O(log n)           O(n)
Max/Min    O(n)       O(1)             O(1) **            O(1) **
Insert     O(1)       O(n)             O(log n)           O(n)
Delete     O(1)       O(n)             O(log n)           O(n)

* assuming binary search

** requires extra pointers to min and max, otherwise it's O(log n)