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.

Solution 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.

Solution 2

The B in database index B* trees stands for Balanced, not Binary. The tree is kept at a uniform depth to ensure even access times.

Solution 3

• Your filesystem is a tree structure. So check out the source to any free filesystem.

• Your compiler generates an AST from your source code, as an intermediate stage. So check out the source to any free compiler.

Solution 4

Binary Trees have been used for Space Paritioning and Hidden Surface removal on 3D games of old, I believe that one was used in the game Doom.

Solution 5

• Write a simple recursive-descent parser, and have it generate a parse tree.

• Bill-Of-Materials structure used in manufacturing (like an automobile consists of subassemblies, recursively, down to the nuts and bolts).

• Symbol table (as used in a compiler).

• Chart Of Accounts as used in project management. An overall project has subprojects, to which charges can be applied.

• Company organizational structure: divisions, departments, etc.

• Table of Contents for a document.

• Descendents of a person, ancestors of a person.

• Any Lisp s-expression, including any Lisp program.

View more solutions