Binary Tree's usage

Can someone give me a real life example ( in programming, C#) of needing to use a Binary Tree or even just an ordinary tree?

I understand the principle of a Binary Tree 开发者_Python百科and how they work, but I'm trying to find some real life example's of their usage?

Tony

In C#, Java, Python, C++ (using the STL) and other high-level languages, most of the time you will use one of the built-in/library-included types to store your data, at least the data you work on at the moment, so most of the time you won't be using a binary tree or another kind of tree explicitly.

This being said, some of these built-in types are implemented as trees of one kind or another "in the backstage", and in some situations you will have to implement one yourself.

Also, a related thing you HAVE to know is binary search. This is mostly done in binary trees (binary search trees :P) but the idea can be extrapolated to a lot of problems, even without trees involved, so try understand it well.

Edit: Real life classical example:

Imagine that you want to search for the phone number of a particular person in the phone guide of a big city. All things being equal, you will open it roughly at the middle, look for the guys in that page, and see if your "target" is before or after it, thus cutting the data by half. Then you repeat the operation in the half where you know your "target" is, and again and again until you found your "target". As each time you are looking into half the data you had before, you require a total of log(base 2) n operations to reach your "target", where n is the total size of the data.

So in a 1 million phone book, you find your target in log(base 2) 1 million = 20 comparisons, instead of comparing one by one as in a linear search (that's 1 million comparisons in the worst case).

Note that this only work in already sorted data.

Balanced binary trees, storing data maintained in sorted order, are used to achieve O(log(n)) lookup, delete, and insert times. "Balanced" just means there is a bounded limit between the depth of the shallowest and deepest leaves, counting empty left/right nodes as leaves. (optimally the depth of left and right subtrees differs at most by one, some implementations relax this to make the algorithms simpler)

You can use an array, rather than a tree, in sorted order with binary search to achieve O(log(n)) lookup time, but then the insert/delete times are O(n).

Some trees (notably B-trees for databases) use more than 2 branches per node, to widen the tree and reduce the maximum depth (which determines search times).

I can't think of a reason to use binary trees that are not maintained in sorted order (a point that has not been mentioned in most of the answers here), but maybe there's some application for this. Besides the sorted binary balanced tree, anything with hierarchy (as other answerers have mentioned, XML or directory structures) is a good application for trees, whether binary or not.

edit: re: unsorted binary trees: I just remembered that LISP and Scheme both make heavy use of unbalanced binary trees. The cons function takes two arguments (e.g. (define c (cons a b)) ) and returns a tree node whose branches are the two arguments. The car function takes such a tree node and returns the first argument given to cons. The cdr function is similar but returns the second argument to cons. Finally nil represents a null object. These are the primitives used to make all data structures in LISP and Scheme. Lists are implemented using an extreme unbalanced binary tree. The list containing literal elements 'Alabama, 'Alaska, 'Arizona, and 'Arkansas can be constructed explicitly as

(cons 'Alabama (cons 'Alaska (cons 'Arizona (cons 'Arkansas nil))))

and can be traversed using car and cdr (where car is used to get the head of the list and cdr is used to get the sublist excluding the list head). This is how Scheme works, I think LISP is the same or very similar. More complicated data structures, like binary trees (which need 3 members per node: two to hold the left and right nodes, and a third to hold the node value) or trees containing more than two branches per node can be constructed using a list to implement each node.

How about the directory structure in Unix. For instance the du command i.e. the disk usage command does a post order traversal (traversal order:: left child -> right child -> root node) of a tree representing the directory structure in order to fetch the disk space used by that directory.

The following slides should help.

http://www.cse.unt.edu/~rada/CSCE3110/Lectures/Trees.ppt

cheers

In Java, trees are used to implement certain sorted data structures, such as the TreeSet:

http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeSet.html

They are used for data structures where you want the order to be based on some property of the elements, rather than on insertion order.

Here are some examples:

• The in-memory representation of a parsed program or expression is a tree. In the case of expressions (excluding ternary operators) the tree will be binary.

• The components of a GUI are organized as a tree.

• Any "containment" hierarchy can be represented as a tree. (HTML, XML and SGML are examples.

And of course, binary (and n-ary) trees can be used to represent indexes, maps, sets and other "generic" data structures.

An easy example is searching. If you store your list data in a tree, for example, you get O(log(n)) lookup times. A standard array implementation of a list would achieve O(n) lookup time.

XML, HTML (and SGML) documents are trees.