Real world examples of tree structures

Question

I'm looking for some examples of tree structures that are used in commercial/free software projects, modern or old. I can see examples on wikipedia, but I am looking for more concrete examples and how they're used. For example primary keys in databases are (from what I've read) stored in BST structure or a variation of the BST (feel free to correct me on this)

My question isn't limited Binary Search Trees (BSTs), it can include any variation such as red-black, AVL and so on.

Answer 1

Is it okay if the examples are a tad bit generic i.e. relate to graphs and not necessarily to trees? If it is, read on.

• Needless to say most XML/Markup parsers use trees. See Apache Xerces for example. Or, the Xalan XSLT parser. Thanks mathewsdave26 for reminding me!

• PDF is a tree based format. It has a root node followed by a catalog node(these are often the same) followed by a pages node which has several child page nodes. Producers/consumers often use a balanced tree implementation to store a document in memory.

• Computer chess games build a huge tree (training) which they prune at runtime using heuristics to reach an optimal move.

• Flare is a visualization library written in AS. You may want to check out how the data objects are mapped. In particular the flare.analytics package heavily uses a graph structure, spanning trees etc.

• Social networking is the current buzzword in CS research. It goes without saying that connections/relations are very naturally modeled using graphs. Often, trees are used to represent/identify more interesting phenomena. How do you answer questions like "Does Harry and Sally have any common friend(s)?"

• Some very successful physics/games engines build trees to accurately simulate human movement. A tree in this case will typically correspond to a set of actions; The context will determine which path is taken to render a particular response.

• Decision Tree based Learning actually forms a formidable area of data mining research. Numerous famous methods exist like bagging, boosting, and modifications thereof which work on trees. Such work is often used to generate a predictive model.

• A common problem in bioinformatics is to search huge databases to find matches for a given query string. Tries are a common occurrence there.

• Quite a few successful (stock) traders use decision trees in their day to day trading -- to choose a trade, to exit one. Often times these are not codified in a computer program, but written down somewhere on the back of their notebook.

Dupe. See this and this.