#### Archived

This topic is now archived and is closed to further replies.

# Binary tree's vs. linked lists

This topic is 6264 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok so I was reading http://www.allegro.cc/pixelate/issues/4/articles/binary_trees/trees.html about binary tree''s.. my question is, what advantage, if any, does this give over linked lists? It seems to me that if each binary tree thingy has 2 pointers (left and right) that that is double the memory of a single linked list.. and the functions to sort through it are all recursive, so that means that that eats up way more memory too. Am I missing something? Mindwarp

##### Share on other sites
A binary tree is MUCH more efficient than a linked list for finding a specific element (assuming your binary tree is sorted). A binary tree can be easily used for a priority queue. If you are unfamiliar with what a priority queue is, as items are added to the queue, they are sorted by some ''priority'' or value. When you ''pop'' an element from the queue, you get the one with the highest value.

You are also forgetting that the number of elements doubles at each ''level'' of the tree. For instance, in a balanced tree, roughly half the elements are down the left branch from the root and the other half are down the right branch. Even going as few as 30 levels down into a balanced tree (not really many recursive steps with today''s computers) you have billions of elements.

Linked lists beat out binary trees in the efficiency of adding and removing elements from the ends. I suggest you find a website or book on data structures, since they will be able to point out advantages and disadvantages better than I can.

##### Share on other sites
Actually it is quicker to delete from a binary tree (I''m assuming a search-tree here, of course) than from a linked list (order log(n) with a binary tree, and order n with a linked list). Insertion is somewhat slower (order log(n) in a b-tree, and order 1 in a linked list). The really big advantage of a tree over a linked list is searching. Assuming a balanced tree (which your are not all that likely to have unless using some sort of balancing-mechanism (AVL-tree, 2-4-tree, treap, etc.)) searching through a tree is order log(n), rather than order (n) with a linked list.
So, basically, if you are going to do a lot of searching for specific elements, using a b-tree is likely to pay for itself.
If you''re not going to do searches stick with lists.

-Neophyte

- Death awaits you all with nasty, big, pointy teeth. -

##### Share on other sites
Neophyte: A B-tree is not the same as a binary tree. A B-tree is defined as a multiway(could be more than 2 children pr node) tree with the following properties:

• Root has at least two children
• All internal nodes other than the root have at least m/2 children(m being the order of the tree)
• All external nodes are at the same level

B-tree''s are typically used in databases and other places where nodes are kept on disk, and where it would be impractical to keep the entire tree in memory. The NT file system, NTFS, uses a B+ tree to maintain the directory structure.

  if ( value == 0 ) return value;else return 0;

##### Share on other sites
the binary tree is not necessarily a recursive function either..

you can still use the ever handy GOTO statement to curb those stack unfriendly recursive functions..

##### Share on other sites
oops..i meant the binary tree''s search function is not necesarily a recursive one..

##### Share on other sites
quote:
Original post by Neophyte
Actually it is quicker to delete from a binary tree (I''m assuming a search-tree here, of course) than from a linked list (order log(n) with a binary tree, and order n with a linked list). Insertion is somewhat slower (order log(n) in a b-tree, and order 1 in a linked list). The really big advantage of a tree over a linked list is searching. Assuming a balanced tree (which your are not all that likely to have unless using some sort of balancing-mechanism (AVL-tree, 2-4-tree, treap, etc.)) searching through a tree is order log(n), rather than order (n) with a linked list.
So, basically, if you are going to do a lot of searching for specific elements, using a b-tree is likely to pay for itself.
If you''re not going to do searches stick with lists.

-Neophyte

- Death awaits you all with nasty, big, pointy teeth. -

Actually, I said it was faster to delete from the ENDS of a linked list than from the ''end'' of a binary tree. Deletion from the front or back of a list is O(1) assuming you have head and tail pointers while every deletion and insertion is more expensive in a binary tree. Also, insertion to a list is only O(1) on the ends. If you need to insert the element in the middle somewhere, it is O(n).

##### Share on other sites
- insertion into any point of a linked list is O(1)
- deletion from any point of a linked list is O(1)
- inserting a range of elements (a.k.a. splice) into a linked list is O(1)
- deleting a range of elements from a linked list is O(1)
- TRAVERSING a linked list is O(N)--this is where the expense comes in
- Random access in a linked list is not possible--you must traverse in order to find the Nth element.

On the other hand, trees have these properties:
- insertion is O(logN)
- deletion is O(logN)
- searching for an element in a binary tree is O(logN)
- There isn''t any range insertion or deletion in trees (not as far as I''m aware).
- Random access is also not possible in a tree. You''ll need to "walk the tree" or have a value you''re searching for.

O(logN) is faster than O(N), so if you''re needing to search a lot, you should be using a tree. If you''re needing to insert/delete a lot without having to search the container, you should be using a list.

If you need random access, you should probably be using an array.

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633388
• Total Posts
3011625
• ### Who's Online (See full list)

There are no registered users currently online

×