CODEWITHSUNDEEP
javaarraylistbinary-search-tree
Meet
Meet

Reputation: 15

Which one is more fast in searching "ordered arraylist" or "BST"?

When BST ordered it works fine, but in some cases it can be unbalanced. What happens in these cases, is BST still efficient? We can directly access the nth element in the ArrayList, so is it more efficient than BST or not?

Upvotes: 0

Views: 775

Answers (2)

Daan van der Kallen
Daan van der Kallen

Reputation: 533

Searching for a value in a sorted array is a bit faster although it has the same asymptotic bound. If you're searching for a the nth element sorted arrays are way faster though. In Java things like TreeSet and TreeMap are based on Red-Black trees which are self balancing without affecting the running time. (They have a maximum depth of 2log(n) instead of log(n) as a perfectly balanced tree.)

Upvotes: 0

Timmy Brolin
Timmy Brolin

Reputation: 1181

Sorted arrays are always fastest for searching. Binary search trees consume more memory and may require more levels of indirection, which hurts performance and increases the chance of cache misses.

Upvotes: 1

Related Questions