Java

[Helios1276]

Hey guys, Can someone tell me whats the advantage of using binary trees over arrays and linked lists?? thanks in advance

[LaRoza]

Hey guys, Can someone tell me whats the advantage of using binary trees over arrays and linked lists?? thanks in advance

Faster searching I think. A linked list is not easily searched, you have to go over the entire list to get to one entry.

[Npl]

it has as much advantages as disadvantages.

Use Trees if you search for elements often and need to add remove elements.

use lists is you add/remove elements often.

use arrays if you read/search often, but write rarely. (Or if you have small amounts of entries)

[xtal]

Most of the advantage of binary trees over linked lists and arrays is in its search. Search of an element in arrays / lists takes O(n) while in binary trees its take O(Log N)! (if you dont know math, its MUCH better).

u can find more information about binary trees and binary search trees in the following links:

http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Binary_search_trees

[CptPicard]

Use Trees if you search for elements often and need to add remove elements.

The benefit of using a tree is exactly the ability to get to the element in question faster than in the case of a list where you would have to search through the entire list from the beginning... so a search and a deletion from tree is O(log n) instead of a list's O(n).

Whether you have anything to gain in comparison with a list when you consider additions depends on whether you have a sorted or nonsorted list. In a sorted list, you have to find the place where to add in linear time. In a nonsorted list, you can just stick the item at the beginning of the list and be done with it.

use lists is you add/remove elements often.

Untrue. Trees beat lists in deletion always, and in additions it depends on whether list is sorted or not.

use arrays if you read/search often, but write rarely.

Arrays are good for random access of elements (the "getting to the element" part) if you know the index of the item in advance. Otherwise an array is not any better than a list -- you must search from the beginning for your item.

Deletions in arrays are particularly bothersome if you must move the rest of the items in the array back by 1 so that you don't leave holes in your array. Note that this would also shift indices that you use to find stuff in the array. Additions can be difficult for the same reason, if you must add into some specific place in the array -- and even the simple case of adding to the end of the array can force you to resize your array by reallocating and copying everything over.

(Or if you have small amounts of entries)

Small lists perform similarly to small arrays...

[mike_g]

Arrays are good for random access of elements (the "getting to the element" part) if you know the index of the item in advance. Otherwise an array is not any better than a list -- you must search from the beginning for your item.

Well you could write a binary search for an array, but only if its sorted.

One point that has not been mentioned is that arrays also use less memory; especially compared to multiple indexed trees or lists. One annoying thing with arrays is that they cant be resized in java unless you use array slicing (AFAIK you cant reallocate it like in C).

[LaRoza]

Speaking of Java, the title of this thread is a little misleading...

[Npl]

...

Untrue. Trees beat lists in deletion always, and in additions it depends on whether list is sorted or not.

Always?? You mean if I delete the first/last n elements of a List it will be faster than traversing&fixing up up the Tree n times? What if youre dealing with a degenerated tree thats basically a list?
You are silently assuming I dont want to delete based on position. I dont know what use the OP had in mind.

Arrays are good for random access of elements (the "getting to the element" part) if you know the index of the item in advance. Otherwise an array is not any better than a list -- you must search from the beginning for your item.

google up binary search. Also accessing them is more efficient than Lists (or trees if they are sorted - no pointer-chasing).

[CptPicard]

Always?? You mean if I delete the first/last n elements of a List it will be faster than traversing&fixing up up the Tree n times?

That's a strange special case that falls outside of what you usually analyze for... you just get "any" n items, and in data structures you generally assume you're after some particular item in the structure.

What if youre dealing with a degenerated tree thats basically a list?

I'm assuming a proper balanced tree structure there of course, the degenerate corner case is not something you ever want to see when you've got a tree

google up binary search.

Now that is a fair point, and mike_g got a thanks for it already

[Npl]

That's a strange special case that falls outside of what you usually analyze for... you just get "any" n items, and in data structures you generally assume you're after some particular item in the structure.

I wouldnt call a Stack/Queue/Deque a strange special case

I'm assuming a proper balanced tree structure there of course, the degenerate corner case is not something you ever want to see when you've got a tree

Nor do you want to search within lists often if you did your homework. I certainly dint said I`d use them if searching is required, maybe you addressed the OP more than me in your post - but you quoted me.