Jump to content
  • Advertisement

Archived

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

Mindwarp

Binary tree's vs. linked lists

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
oops..i meant the binary tree''s search function is not necesarily a recursive one..

Share this post


Link to post
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 this post


Link to post
Share on other sites
There''s some incorrect information about linked lists here:
- 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.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!