CODEWITHSUNDEEP
algorithmbinary-search-treecomplexity-theory
p0lAris
p0lAris

Reputation: 4820

Binary Search Tree vs Array for ordered elements

Consider the scenario where data to be inserted in an array is always in order, i.e. (1, 5, 12, 20, ...)/A[i] >= A[i-1] or (1000, 900, 20, 1, -2, ...)/A[i] <= A[i-1].

To support such a dataset, is it more efficient to have a binary search tree or an array.

(Side note: I am just trying to run some naive analysis for a timed hash map of type (K, T, V) and the time is always in order. I am debating using Map<K, BST<T,V>> vs Map<K, Array<T,V>>.)

As I understand, the following costs (worst case) apply—

          Array            BST

Space     O(n)             O(n)
Search    O(log n)         O(n)
Max/Min   O(1)             O(1) *
Insert    O(1) **          O(n)
Delete    O(n)             O(n)

*: Max/Min pointers
**: Amortized time complexity

Q: I want to be more clear about the question. What kind of data structure should I be using for such a scenario between these two? Please feel free to discuss other data structures like self balancing BSTs, etc.

EDIT:

  1. Please note I didn't consider the complexity for a balanced binary search tree (RBTree, etc). As mentioned, a naive analysis using a binary search tree.

  2. Deletion has been updated to O(n) (didn't consider time to search the node).

  3. Max/Min for skewed BST will cost O(n). But it's also possible to store pointers for Max & Min so overall time complexity will be O(1).

Upvotes: 0

Views: 1107

Answers (1)

Tejash Desai
Tejash Desai

Reputation: 466

See below the table which will help you choose. Note that I am assuming 2 things:

1) data will always come in sorted order - you mentioned this i.e. if 1000 is the last data inserted, new data will always be more than 1000 - if data does not come in sorted order, insertion can take O(log n), but deletion will not change

2) your "array" is actually similar to java.util.ArrayList. In short, its length is mutable. (it is actually unfair compare a mutable and an immutable data structure) However, if it is a normal array, your deletion will take amortized O(log n) {O(log n) to search and O(1) to delete, amortized if you need to create new array} and insertion will take amortized O(1) {you need to create new array} 

          ArrayList         BST

 Space     O(n)             O(n)
 Search    O(log n)         O(log n) {optimized from O(n)}
 Max/Min   O(1)             O(log n) {instead of O(1) - you need to traverse till the leaf}
 Insert    O(1)             O(log n) {optimized from O(n)}
 Delete    O(log n)         O(log n)

So, based on this, ArrayList seems better

Upvotes: 0

Related Questions