What is the difference between an array and a binary search tree in efficiency?

Question

I want to know which is better: Array OR Binary search tree in (insert, delete, find max and min) and how can I improve both of them?

Answer 1

Array Allows random access to each element in it. therefore, you get the insertion, deletion, and search for a specific element in O(1) and max / min, delete in O(n) . [you can also do max / min O(1) and remove O(n) instead]. If you keep your array sorted, this will cause insert / delete to be O(n) , but you will get O(logn) find and O(1) min / max.

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

Arrays are also usually faster than iterate [assuming the iteration order is not important], as you improve cache . Also, unlike BST - which is unlimited in nature, an array requires redistributing and copying data when your array is full.

An improvement in BST can be made by balancing - for example, AVL or red-black trees .

Which is better ? it depends on the application. Usually, when you plan to embed and sort data, BST will be preferable. If the main goal is random access or iteration, you usually use an array.

Answer 2

Comparison of performance 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 additional pointers to min and max, otherwise O (log n)