-
Binary Trees?
They are being talked about lately, and i know this is a noobish question but what are they used for? I am somewhat familiar with what they look like:
1
/ \
0 1
/ \ / \
0 1 0 1
That example probably isnt right but what are they? Why are they useful? And how are they implemented? If there is a good tutorial or website or something just let me know. Thanks!
-
-
-
>but what are they used for?
A lot of things. That's probably not helpful, so consider a canonical example of trees: a directory structure. Chances are very good that the computer you're using has directories structured as a tree. You have a root directory, / or C:/, and then nested within the root directory are files (which could be considered leaf nodes), and other directories (non-leaf nodes). That's not only a tree, but a tree that clearly displays the recursive nature of trees. But it's not a binary tree, or a binary search tree, which is likely what you mean when you say binary tree.
A binary search tree can be used for any number of things, but most commonly it's used to store data in a way that it can be found quickly. That means simple in-core databases, symbol tables, etc. You can also take advantage of certain easy to implement properties, such as ignoring duplicate items to make a frequency table/histogram. Binary search trees can be used as cache's (and often are in the form of splay trees), a quick way to sort large amounts of data, and of course, any divide and conquer algorithm is easier to analyze if you use a binary or m-ary tree to represent the recursion.
-
Here's another useful site about binary trees.
http://www.cs.usask.ca/resources/tut...ree_index.html
There's not much actual code but this is made up by the site's use of interactive applets. If you know what is going on visually, then in theory the coding should be easier.