PDA

View Full Version : Binary trees in real life?



audinue
11-12-2008, 04:40 AM
I'm just a little bit curious...
Is there any "binary tree" in real-life other than a simple family structure?

... Food cooking? ... Or something else?

matsp
11-12-2008, 04:59 AM
Actually, a family tree is not strictly a binary tree, as it's possible to have more than two siblings to a parent node.

Telephone exchanges used a tree hierarchy to find the actual target phone when dialing a phone number, for example. It is again not a binary tree, but a "decimal" tree with 10 nodes coming off each individual node. Of course, modern telephone exchanges are computerized, and the actual structure is not strictly a tree any longer.

And of course the structure of taxonomy (scientific names of species) is a tree - again not a binary tree.

--
Mats

CornedBee
11-12-2008, 11:36 AM
A family tree isn't even a tree, because branches can merge again.

brewbuck
11-12-2008, 11:53 AM
A family tree isn't even a tree, because branches can merge again.

Making it a "dag" (directed acyclic graph).

Perspective
11-12-2008, 12:02 PM
Making it a "dag" (directed acyclic graph).

In some places they allow cycles :eek:

CornedBee
11-12-2008, 12:06 PM
Wow, I'd like to see the time machine that makes this possible.

SlyMaelstrom
11-12-2008, 12:57 PM
Wow, I'd like to see the time machine that makes this possible.Enough inbreeding will make anything seem possible.

http://www.metacafe.com/watch/54702/im_my_own_grandpa/

Note: This video or song contains nor condones any form of inbreeding. It's just cute.

brewbuck
11-12-2008, 01:16 PM
I'm just a little bit curious...
Is there any "binary tree" in real-life other than a simple family structure?

... Food cooking? ... Or something else?

Most decision-making processes can be represented as a binary tree. At each node of the tree a yes/no decision is made on some issue. Depending on which decision is made, another decision must be made, or some course of action is followed. So a path from root to leaf in this tree represents a chain of decisions which were made to arrive at that course of action.

Decisions with more than two choices can still be represented as binary decisions. It just makes the tree deeper.

audinue
11-12-2008, 03:16 PM
At each node of the tree a yes/no decision is made on some issue. Depending on which decision is made, another decision must be made, or some course of action is followed. So a path from root to leaf in this tree represents a chain of decisions which were made to arrive at that course of action.

Nice explanation brewbuck... Thanks.
Btw, any example of cases in real-life about binary tree anyone?

matsp
11-12-2008, 03:48 PM
Nice explanation brewbuck... Thanks.
Btw, any example of cases in real-life about binary tree anyone?

I thought brewbucks example IS that.

Usually, at the back of your power-tools or such user's guide, there is a trouble-shooting guide:
Machine doesn't start:
Step 1.
Is the power-plugged in?
No - Plug it in,
Yes - Go to step 2.
2. Has the fuse blown?
Yes - replace fuse.
No - go to step 3.
... etc, etc.

That's exactly a binary tree.

Another form is "keys" for identifying species of animals, e.g. this one:
http://www.auburn.edu/academic/science_math/res_area/loricariid/fish_key/key.html

--
Mats

Mario F.
11-12-2008, 06:26 PM
Another area where binary trees can be observed is in the language rules and are often used to build database dictionaries.

Which is quite a fascinating area, that of expressing hierarchies and trees in RDBMs. I wholeheartedly advise one of the most fascinating SQL books ever written: Morgan Kaufamann Publishers - Trees and Hierarchies in SQL for Smarties, by Joe Celko. I stumbled upon this book on a bookshop in Glenelg (Australia) while hunting for something completely unrelated. I ended up leaving the shop with it and not what I went there for.

matsp
11-13-2008, 03:08 AM
Mario,

I think Audinue is asking for examples OUTSIDE of computers.

--
Mats

abachler
11-13-2008, 04:34 AM
I'm just a little bit curious...
Is there any "binary tree" in real-life other than a simple family structure?

... Food cooking? ... Or something else?

The genetic material an offspring receives from its parents coudl be represented as a binar tree, since for each gene the child recieves either one copy or the other from a particular parent.

audinue
11-13-2008, 05:33 AM
Yeah! I found it!

http://www.greenteapress.com/thinkpython/thinkCSpy/html/chap20.html

Section 7 The animal tree

This is a simplest implementation of binary tree (which I can tell to my students *giggle*)...
It's often called "Animal Guess"

I hope there is another example that simple to understand for kids between 12 and 15 years old...

Cool... Thanks everyone for replying!

matsp
11-13-2008, 05:41 AM
The animal tree is really just a different variant of the troubleshooting tree that I described earlier.

--
Mats